Summation of Double Exponential Series

Question

Is there any known closed form or tight bound analysis (big-O or big-$\Theta$) for $\sum_{i = 0}^{n} 2^{2^i}$?

Answer 1

It is true that $$ 2^{2^n}\le \sum_{i=0}^n 2^{2^i}\le 2^{2^{n}}+\sum_{k=0}^{2^{n-1}}2^k=2^{2^n}+2^{2^{n-1}+1}-1\le 2^{2^n}+2\cdot 2^{2^{n-1}}=2^{2^n}(1+2\cdot 2^{-2^{n-1}}) $$ This shows that your sum is eventually between $2^{2^n}$ and $(1+\epsilon)2^{2^n}$ for any $\epsilon>0$.

Answer 2

If within constants is fine, then here's an easy proof that it is $\Theta(2^{2^n})$. The idea is that $2^{2^i}$ grows faster than exponential, so it should be that the largest term in the sum dominates the sum itself up to a constant.

The lower bound is obvious. For the upper bound, we show that $\sum_{i=1}^n 2^{2^i}\leq 2\cdot 2^{2^n}$ by induction. Start with the inductive hypothesis. Then, \begin{align*} \sum_{i=1}^n 2^{2^i} &\leq 2\cdot 2^{2^n}\leq 2^{2^n}\cdot 2^{2^n} = 2^{2^{n+1}}. \end{align*} Now adding $2^{2^{n+1}}$ on both sides allows us to conclude as desired.