1
$\begingroup$

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

Any idea?

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

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

$\endgroup$
  • 1
    $\begingroup$ 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 :). $\endgroup$ – JimmyK4542 Jan 5 '17 at 6:56
  • 1
    $\begingroup$ @JimmyK4542. This is a very nice comment for sure ! $\endgroup$ – Claude Leibovici Jan 5 '17 at 10:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Gerry Myerson Jan 5 '17 at 12:00
  • 1
    $\begingroup$ 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) $\endgroup$ – ypercubeᵀᴹ Jan 5 '17 at 14:17
  • 1
    $\begingroup$ @TypoCubeᵀᴹ. Amazing, isn't it ? Thanks for the link. Cheers. $\endgroup$ – Claude Leibovici Jan 5 '17 at 14:27

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.