Asymptotic growth of $\frac{k}{1}+\frac{k^2}{1\cdot 2}+\frac{k^3}{1\cdot 2\cdot 4}+\dots$

77 Views Asked by At

Let $k$ be a positive integer, and let $$n=\frac{k}{1}+\frac{k^2}{1\cdot 2}+\frac{k^3}{1\cdot 2\cdot 4}+\frac{k^4}{1\cdot 2\cdot 4\cdot 8}+\dots,$$ where the sum goes on until the next term in the sum is smaller than the previous term. How does $k$ grow asymptotically as a function of $n$?

In the $j$th term, we multiply the $(j-1)$th term by $k/2^{j-1}$, so the sum stops when $2^{j-1}>k$. That is, we have roughly $\log k$ terms.

1

There are 1 best solutions below

1
On BEST ANSWER

Hint:

The terms can be written

$$\frac{k^j}{2^{(j-1)j/2}}$$ with $j$ starting from $1$ until $j=\lceil\log_2k\rceil$.

So the last term is

$$\frac{k^{\lceil\log_2k\rceil}}{2^{(\lceil\log_2k\rceil-1)\lceil\log_2k\rceil/2}}.$$

As the denominators grow quickly, the sum of the terms is not more than twice the last one.