TAOCP 2.5 Exercise 21

Let t_1,t_2,t_3,\ldots be the sequence

taocpmathematicsalgorithmsvolume-1

Section 2.5: Dynamic Storage Allocation

Exercise 21. [**] [HM25] Examine the ratio $a_n/b_n$, where $a_n$ is the sum of the first $n$ terms of $$ 1+2+4+4+8+8+8+8+16+16+\cdots, $$ and $b_n$ is the sum of the first $n$ terms of $$ 1+2+3+4+5+6+7+8+9+10+\cdots, $$ as $n$ goes to infinity.

Verified: yes
Solve time: 2m45s

Let

$$ t_1,t_2,t_3,\ldots $$

be the sequence

$$ 1,2,4,4,8,8,8,8,16,16,\ldots, $$

where $2^k$ appears exactly $2^k$ times. Define

$$ a_n=\sum_{j=1}^{n} t_j, \qquad b_n=\sum_{j=1}^{n} j=\frac{n(n+1)}2. $$

We determine

$$ \lim_{n\to\infty}\frac{a_n}{b_n}. $$

Let

$$ N_m=\sum_{k=0}^{m}2^k=2^{m+1}-1. $$

Then $N_m$ is the number of terms through the block of $2^m$'s. Also,

$$ S_m:=a_{N_m} =\sum_{k=0}^{m}2^k\cdot 2^k =\sum_{k=0}^{m}4^k =\frac{4^{m+1}-1}{3}. $$

Now let $n$ be arbitrary. Choose $m$ so that

$$ N_m\le n<N_{m+1}. $$

Write

$$ n=N_m+r, \qquad 0\le r\le 2^{m+1}-1. $$

After the first $N_m$ terms, the sequence consists of $2^{m+1}$'s. Hence

$$ a_n=S_m+r,2^{m+1} =\frac{4^{m+1}-1}{3}+r,2^{m+1}. $$

Introduce

$$ x=\frac{r}{2^{m+1}}, \qquad 0\le x<1. $$

Since $N_m=2^{m+1}-1$,

$$ n=(1+x)2^{m+1}-1. $$

Therefore

$$ a_n = 2^{2m+2}!\left(\frac13+x\right)-\frac13, $$

and

$$ b_n = \frac{n(n+1)}2 = \frac{\bigl((1+x)2^{m+1}-1\bigr)\bigl((1+x)2^{m+1}\bigr)}2. $$

Divide numerator and denominator by $2^{2m+2}$. We obtain

$$ \frac{a_n}{b_n} = \frac{\frac13+x-\frac1{3\cdot 2^{2m+2}}} {\frac12(1+x)^2-\frac{1+x}{2^{m+2}}}. $$

As $m\to\infty$, the terms containing $2^{-m}$ and $2^{-2m}$ vanish uniformly for $0\le x<1$. Hence

$$ \frac{a_n}{b_n} = \frac{\frac13+x}{\frac12(1+x)^2} +o(1), $$

uniformly in $x\in[0,1)$.

Define

$$ f(x)=\frac{\frac13+x}{\frac12(1+x)^2} =\frac{2\left(\frac13+x\right)}{(1+x)^2}. $$

A direct calculation gives

$$ f'(x) = \frac{2(1-2x/3-1/3)}{(1+x)^3} = \frac{\frac43(1-x)}{(1+x)^3}. $$

Thus $f'(x)\ge0$ on $[0,1]$, so $f$ is increasing there. Consequently,

$$ f(0)=\frac23, \qquad f(1)=\frac23. $$

Since an increasing function that takes the same value at both endpoints must be constant,

$$ f(x)\equiv \frac23 \qquad (0\le x\le1). $$

Therefore

$$ \frac{a_n}{b_n} = \frac23+o(1), $$

uniformly for all $N_m\le n<N_{m+1}$.

Since every sufficiently large $n$ lies in some interval $[N_m,N_{m+1})$ with $m\to\infty$, it follows that

$$ \lim_{n\to\infty}\frac{a_n}{b_n} = \frac23. $$

Hence

$$ \boxed{\displaystyle \lim_{n\to\infty}\frac{a_n}{b_n}=\frac23 }. $$