First, recall a formula from algebra |
1 + 2 + 3 + ... + k = k(k+1)/2 |
and so |
1 + 2 + 3 + ... + 2n = 2n(2n + 1)/2 |
From this we see |
Log(N((1/2)n)) =
Log(2n(2n + 1)/2) =
Log(2n) + Log(2n + 1) - Log(2) |
For large n, |
2n + 1 ≈ 2n, |
so we might replace |
Log(2n + 1) |
by |
Log(2n). |
Then |
db | = limn→∞Log(N((1/2)n))/Log(2n) |
| = limn→∞(2 Log(2n) - Log(2)) / Log(2n) | |
| = limn→∞(2n Log(2) - Log(2)) / n Log(2) | |
| = 2 | |
|
  |
A more rigorous approach, which we shall need for later calculations, is to note |
2n + 1 =
2n(1 + 1/2n), |
and so |
Log(2n + 1) |
= Log(2n(1 + 1/2n)) |
| = Log(2n) + Log(1 + 1/2n). |
|
Putting all this together, we have |
Log(N((1/2)n)) |
= Log(2n) + Log(2n) + Log(1 + 1/2n) - Log(2) |
| = 2Log(2n) + Log(1 + 1/2n) - Log(2), |
|
and so |
Log(N((1/2)n)) / Log(1/(1/2)n) |
= Log(N((1/2)n)) / Log(2n) |
| = (2Log(2n) / Log(2n)) +
(Log(1 + 1/2n) / Log(2n)) - (Log(2) / Log(2n)) |
|
As n gets larger (so (1/2)n gets smaller), we see |
Log(1 + 1/2n) / Log(2n) → Log(1) / Log(∞) = 0 |
Log(2) / Log(2n) → Log(2) / Log(∞) = 0 |
|
That gives |
db = limn→∞2Log(2n) / Log(2n) = 2, |
as expected. |