# Closed form for $\sum_{k=1}^K \binom{K}{k}2^{k(K-k)}$

Is there a closed form expression for $\displaystyle\sum_{k=1}^K \binom{K}{k}2^{k(K-k)}$?

Any idea?

• This looks very close to the binomial theorem for $(a+b)^K$ where $a = b = 2$. – Mark Jan 5 '17 at 5:58
• @Mark except that this is $2^{kK-k^2}$, not $2^{k}\cdot 2^{K-k}=2^{k+K-k}$ – JMoravitz Jan 5 '17 at 5:58
• Close only counts in horseshoes and hand grenades. – Gerry Myerson Jan 5 '17 at 6:16
• Well, $1,5,25,\dots$ are the first few powers of five... thats a rather special pattern – JMoravitz Jan 5 '17 at 6:31
• @GerryMyerson, I have noted the expression, thanks! – Andreas Caranti Jan 5 '17 at 10:16

This is not an answer but it is too long for a comment.

The first terms are $$\{1,5,25,161,1441,18305,330625,8488961,309465601,16011372545\}$$ and the on-line encyclopedia of integer sequences ($OEIS$) does not recognize this pattern.

A quick and dirty plot of the results (for $1 \leq K \leq 1000$) seems to show that, if $$a_K=\sum_{k=1}^K \binom{K}{k}2^{k(K-k)}$$ $\log(a_K)$ varies almost as a quadratic function of $K$.

Edit

For $10 \leq K \leq 1000$ (step of $10$), a linear regression $a_K=a+b K + c K^2$ gives
$$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -1.37425 & 0.03376 & \{-1.44125,-1.30724\} \\ b & +0.68959 & 0.00015 & \{+0.68929,+0.68990\} \\ c & +0.17329 & \approx 0 & \{+0.17329,+0.17329\} \\ \end{array}$$

Edit

One could notice that, in the regression, $b\approx \log(2)$ and $c=\frac 14 \log(2)$ as we could deduce from JimmyK4542's very interesting comment.

Using the bounds given by JimmyK4542 in his comment, a rather good approximation could be $$a_K\approx \frac{2^{\frac{K^2}4+K+\frac 32}}{\sqrt{\pi K}}$$ For $K=1000$, the exact result is $\approx 1.81\times 10^{75557}$ while the above approximation gives $\approx 1.71\times 10^{75557}$.

Back to regression, using $$\log(a_K)=a+b K+c K^2-d\log(K)$$ avery good fit can be obtained $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & 0.30589 & 0.00717 & \{0.29165,0.32014\} \\ b & 0.69292 & 0.00002 & \{0.69289,0.69295\} \\ c & 0.17329 & \approx 0 & \{0.17329,0.17329\} \\ d & 0.45106 & 0.00189 & \{0.44731,0.45481\} \\ \end{array}$$

Update

After reading Gerry Myerson's so interesting comment, looking at sequence $A000683$ in $OEIS$, the given asymptotics write $$a_K=1+\vartheta _3\left(0,\frac{1}{2}\right)\frac{2^{\frac{K^2}{4}+K+\frac{1}{2}} }{\sqrt{\pi K} }\qquad \qquad (K \, \,\text{even})$$ $$a_K=1+\vartheta _2\left(0,\frac{1}{2}\right)\frac{2^{\frac{K^2}{4}+K+\frac{1}{2}} }{\sqrt{\pi K} }\ \qquad \qquad (K \,\text{odd})$$

• For even $K$, the largest term is the $K/2$-term which behaves like $\binom{K}{K/2}2^{K^2/4} \sim \sqrt{\tfrac{2}{\pi K}}2^{K^2/4+K}$. Hence the sum is asymptotically between $\sqrt{\tfrac{2}{\pi K}}2^{K^2/4+K}$ and $\sqrt{\tfrac{2K}{\pi}}2^{K^2/4+K}$. So $\log(a_k)$ does infact grow quadratically :). – JimmyK4542 Jan 5 '17 at 6:56
• @JimmyK4542. This is a very nice comment for sure ! – Claude Leibovici Jan 5 '17 at 10:17
• @Jimmy, if you subtract 1 and divide by 4, you get oeis.org/A000683. If you don't divide by 4, you get oeis.org/A213441 Number of 2-colored graphs on $n$ labeled nodes. But oeis doesn't give the asymptotics so maybe someone should tell them. – Gerry Myerson Jan 5 '17 at 12:00
• And if you add 1, you get eis.org/A047863: Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa. (and I thought of searching for the sequence produced by having the sum from 0 to K, instead of 1 to K) – ypercubeᵀᴹ Jan 5 '17 at 14:17
• @TypoCubeᵀᴹ. Amazing, isn't it ? Thanks for the link. Cheers. – Claude Leibovici Jan 5 '17 at 14:27