Upper bound for $\sum\limits_{k=1}^{n} \binom{n}{k} 2^{2^k}$

Question

We know that $\sum\limits_{k=1}^{n} \binom{n}{k} {2^k}=3^n$, but what is a big O when considering double exponential $\sum\limits_{k=1}^{n} \binom{n}{k} 2^{2^k}$?

Answer 1

Note that $$2^{2^n}\leq \sum_{k=1}^{n} \binom{n}{k} 2^{2^k}=2^{2^n}+\sum_{k=1}^{n-1} \binom{n}{k} 2^{2^k}\leq 2^{2^n}+2^{2^{n-1}}\underbrace{\sum_{k=1}^{n-1} \binom{n}{k}}_{=2^n-2} \leq 2^{2^n}+2^{2^{n-1}+n}.$$ Moreover $$\lim_{n\to\infty}\frac{2^{2^{n-1}+n}}{2^{2^n}}=\lim_{n\to\infty}2^{2^{n-1}+n-2\cdot 2^{n-1}}=\lim_{n\to\infty}2^{-2^{n-1}+n}=0.$$ Hence, as already remarked by didgogns, $$\sum_{k=1}^{n} \binom{n}{k} 2^{2^k}=O(2^{2^n}).$$