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

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.

• Don't you mean $n$ as a function of $k$ ? – Yves Daoust Apr 16 at 13:57
• Actually, I mean $k$ as a function of $n$. – pi66 Apr 16 at 15:27

## 1 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.

• @pi66 If you know how $n$ grows asymptotically with $k$, then you know how $k$ grows asymptotically with $n$. – kccu Apr 16 at 16:05