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

  • 9
    $\begingroup$ I must say that the $2^{k^2}$ factor makes me pessimistic that this will resolve to something simple... OEIS knows nothing either. $\endgroup$ – J. M. is a poor mathematician Oct 25 '11 at 12:34
  • $\begingroup$ With $2^k$ everything is fine: the sum resolves to $3^n$. $\endgroup$ – Hans-Peter Stricker Oct 25 '11 at 12:36
  • $\begingroup$ 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}$. $\endgroup$ – 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).$$

  • 1
    $\begingroup$ 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}$. $\endgroup$ – robjohn Oct 25 '11 at 21:00
  • $\begingroup$ 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?) $\endgroup$ – Hans-Peter Stricker Oct 26 '11 at 6:32
  • $\begingroup$ @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. $\endgroup$ – Mike Spivey Oct 26 '11 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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