# Evaluating $\sum_{k=0}^n \binom{n}{k} 2^{k^2}$

$$\sum_{k=0}^n \binom{n}{k} 2^{k^2}$$

Wolframalpha fails (see here).

The sum counts the number of (labelled) digraphs (with loops) with vertex set $V \subseteq [n]$.

-
I must say that the $2^{k^2}$ factor makes me pessimistic that this will resolve to something simple... OEIS knows nothing either. – J. M. Oct 25 '11 at 12:34
With $2^k$ everything is fine: the sum resolves to $3^n$. – Hans Stricker Oct 25 '11 at 12:36
I think you entered it wrong, Wolframalpha seems to read it as the bracket $\{ k=0\}$ is missing. Then it becomes :$\sum_k=0^n \binom{n}{k} 2^{k^2}$. – N. S. Oct 25 '11 at 13:49

I agree with J.M.'s comment above that this is not going to resolve into something simple. Asymptotically, though, the last term will dominate, and maybe that will be useful. We have $$2^{n^2} \leq \sum_{k=0}^n \binom{n}{k} 2^{k^2} \leq 2^{n^2}\left(1 + \frac{2n^2}{4^n}\right).$$ The relative remainder term $R(n) = \frac{2n^2}{4^n}$ goes to $0$ fairly quickly as $n \to \infty$, and so $\sum_{k=0}^n \binom{n}{k} 2^{k^2} \approx 2^{n^2}$.

Derivation: The terms in the sum are strictly increasing. Since $n \geq k$, for $k \geq 1$ we have $$\frac{\binom{n}{k} 2^{k^2}}{\binom{n}{k-1}2^{(k-1)^2}} = 2^{2k-1}\left(\frac{n}{k}-1+\frac{1}{k}\right) \geq 2^{2k-1}\left(1-1+\frac{1}{k}\right) = \frac{2^{2k}}{2k}> 1.$$

Therefore, $$2^{n^2} \leq \sum_{k=0}^n \binom{n}{k} 2^{k^2} = 2^{n^2} + \sum_{k=0}^{n-1} \binom{n}{k} 2^{k^2} \leq 2^{n^2} + \sum_{k=0}^{n-1} \binom{n}{n-1} 2^{(n-1)^2} = 2^{n^2} + n^2 2^{n^2-2n+1}$$ $$= 2^{n^2}\left(1 + \frac{2n^2}{4^n}\right).$$

-
I like the inclusion of the derivation. (+1) Your error term is better than mine: \begin{align} \sum_{k=0}^n\binom{n}{k}2^{k^2} &=\sum_{k=0}^n\binom{n}{k}2^{(n-k)^2}\\ &=2^{n^2}\sum_{k=0}^n\binom{n}{k}2^{-k(2n-k)}\\ &\le2^{n^2}\sum_{k=0}^n\binom{n}{k}2^{-kn}\\ &=2^{n^2}\left(1+2^{-n}\right)^n \end{align} and $\left(1+2^{-n}\right)^n\to1$ pretty fast, but not as fast as $1+\frac{2n^2}{4^n}$. – robjohn Oct 25 '11 at 21:00
Thanks a lot! (BTW: Is there a connection between the fact that the error term decreases very quickly and the fact that there is no simple resolution? Is there a counter example?) – Hans Stricker Oct 26 '11 at 6:32
@Hans: You're welcome! With respect to your question, I don't know. And while I don't think there is a nice closed-form answer, I can't prove that there isn't one, either. – Mike Spivey Oct 26 '11 at 15:32