Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone please help me simplifying this sum

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

Wolframalpha fails (see here).

Thanks in advance.

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

share|cite|improve this question
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
up vote 7 down vote accepted

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).$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.