Can this sum be simplified: $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$

Or at least is there a simple fairly tight upperbound?

EDIT So I think this sum is more easily bounded than I previously thought: Clearly, $$\sum_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}} \cdot \leq 2^{\sqrt{n}} \sum_{k=0}^{n} \binom{n}{k} = 2^{n+\sqrt{n}} .$$

Also, along the same lines as Shai Covo's answer, $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}} \geq \binom{n}{n/2} 2^{\sqrt{n/2}}$. The central binomial coefficient: $\binom{n}{n/2}$ is at least $\frac{2^n}{\sqrt{2n}}$, hence $$\sum_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}} \geq 2^{\sqrt{n/2}} \cdot \frac{2^n}{\sqrt{2n}} = \frac{2^{n + \sqrt{n/2}}}{2n}$$

So $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$ is $O(2^{n + \sqrt{n}})$ and $\Omega(\frac{2^{n+\sqrt{n/2}}}{n})$

What about expressions of the form: $\sum \limits_{k=0}^{n} \binom{n}{k} a^{\sqrt{k}} b^{\sqrt{n-k}}$?

  • $\begingroup$ Do you want the floor of sqrt(k) or the full irrational value? It's just that binomials have an "integer" flavor and square roots don't. $\endgroup$ – Ross Millikan Dec 15 '10 at 15:46
  • $\begingroup$ I care more about asymptotic bounds so the floor or the full irrational value is fine with me $\endgroup$ – Travis Service Dec 16 '10 at 3:19
  • $\begingroup$ For the more general question at the end, may we assume $a,b \geq 1$? $\endgroup$ – Shai Covo Dec 16 '10 at 12:52
  • $\begingroup$ @Shai Covo yes assume $a,b \geq 1$. In fact I am also interested in the case were $a=b \geq 1$ $\endgroup$ – Travis Service Dec 16 '10 at 12:55
  • $\begingroup$ I think I'll have a solution soon. $\endgroup$ – Shai Covo Dec 16 '10 at 13:22

For the more general question at the end, let's first consider the weighted inner product and weighted norm on $\mathbb{R}^n$, which are defined by $$ \langle u,v\rangle = \sum\limits_{i = 1}^n {c_i u_i v_i }, \;\; \|u\| = \sqrt {\langle u,u\rangle } = \sqrt {\sum\limits_{i = 1}^n {c_i u_i^2 } }, $$ where $c_1,\ldots,c_n$ are positive constants (called weights). By Cauchy-Schwarz inequality, $|\langle u,v\rangle | \le \|u\| \; \|v\|$. Hence, letting ${n \choose k}$ play the role of weights (and using the symmetry of binomial coefficients), we have $$ \sum\limits_{k = 0}^n {{n \choose k}a^{\sqrt k } b^{\sqrt {n - k} } } \le \sqrt {\sum\limits_{k = 0}^n {{n \choose k}(a^2 )^{\sqrt k } } } \sqrt {\sum\limits_{k = 0}^n {{n \choose k}(b^2 )^{\sqrt k } } } . $$ So, if we assume that $a,b \geq 1$, the problem essentially reduces to the original one (as far as an upper-bound is concerned). In particular, when $a=b$, we get $$ \sum\limits_{k = 0}^n {{n \choose k} a^{\sqrt k } a^{\sqrt {n - k} } } \le \sum\limits_{k = 0}^n {{n \choose k} a^{2\sqrt k } }. $$


I will only give some simple and useful estimate (confirmed by numerical results, based on some mathematical idea). It is essentially a lower bound, but can probably be easily modified to be an upper bound. Moreover, it might give you further ideas.

Denote your expression by $\varphi_n$, and consider a random variable $X$ with binomial$(n,1/2)$ distribution. Then $$ {\rm E}\big[2^{\sqrt X } \big] = \sum\limits_{k = 0}^n {2^{\sqrt k } {n \choose k}\frac{1}{{2^n }}} = \frac{1}{{2^n }}\varphi _n. $$ The left-hand side is actually the moment-generating function $M(t)$ of $\sqrt{X}$ at $t=\ln2$, but we will not use this fact. I have plotted the function $2^{\sqrt{x}}$, $x > 0$, and it seems that this function is typically convex (it is not convex near $0$). So, heuristically, Jensen's inequality suggests the following result: $$ {\rm E}\big[2^{\sqrt X } \big] > 2^{\sqrt {{\rm E}[X]} }, $$ for all sufficiently large $n$. (If $n$ is large, then $X$ typically takes values in a set on which $2^{\sqrt{x}}$ is convex.) Finally, ${\rm E}[X]=n/2$ leads to $2^{ - n} \varphi _n > 2^{\sqrt {n/2} }$, that is $$ \sum\limits_{k = 0}^n {{n \choose k} 2^{\sqrt k } } > 2^{n + \sqrt {n/2} }, $$ for all sufficiently large $n$. Numerical results indicate that this inequality holds for all $n \geq 6$. Moreover, the results suggest that the (lower-)bound is quite tight (I checked for $n \leq 150$). So, a tight upper-bound is likely to be something not far from $2^{n + \sqrt {n/2}}$.

EDIT: We can also employ the strong law of large numbers (SLLN) to show that $\varphi_n$ may be expected to behave something like $2^{n + \sqrt {n/2}}$ for large $n$. Indeed, writing $X$ as $Y_1 + \cdots + Y_n$, where $Y_i$ are i.i.d. rv's with ${\rm P}(Y_i = 0) = {\rm P}(Y_i = 1) = 1/2$, we have $$ \varphi _n = 2^n {\rm E}\bigg[2^{\sqrt n \sqrt {\frac{{Y_1 + \cdots + Y_n }}{n}} } \bigg]. $$ By SLLN, $\frac{{\sum\nolimits_{i = 1}^n {Y_i } }}{n}$ converges to $1/2 \,(= {\rm E}[Y_1])$ almost surely, and the conclusion follows.


The mass in the sum is approximately proportional to a (shifted) Gaussian centered at $k = n/2 + C\sqrt{n}$ and with standard deviation $A \sqrt{n}$ for explicitly calculable constants $C$ and $A$. This implies asymptotics of the form $(M + o(1))2^{n + \sqrt{n/2}}$ where $M$ is another computable constant.

The same is true for the $a,b$ version of the problem.

[edit: my calculations give $M = 2^{(\ln 2)/8} = 1.0618966...$.

[edit-2: similar calculations give $M=(a/b)^{\ln (a/b)}/8$ and asymptotics $(M+o(1))2^n (ab)^\sqrt{n/2}$ for the $a,b$ sum.]

  • $\begingroup$ Maybe some typo in your asymptotic expression? This does not agree with my lower bound, which is much bigger, and with numerical results. $\endgroup$ – Shai Covo Dec 16 '10 at 23:28
  • $\begingroup$ @Shai: thanks, I corrected it (the 1/sqrt(n) factor is cancelled by the sqrt(n) length of intervals on which one integrates the Gaussian). The calculation of M predicts a ratio of about 1.06 between the asymptotic value and your lower bound. Is this what the numerics showed? $\endgroup$ – T.. Dec 17 '10 at 5:42
  • $\begingroup$ The numerics only indicate that this is a possibility. I don't have a powerful computation tool, and so I can't reach a conclusion. $\endgroup$ – Shai Covo Dec 17 '10 at 11:38
  • $\begingroup$ @Shai: what did the observed ratios (numerical calculation / lower bound) look like for larger $n$ such as 100 or 150? $\endgroup$ – T.. Dec 17 '10 at 17:23
  • $\begingroup$ Observed ratios for n=250,500,750,1000,1250,1500,1750 (respectively): 1.0263534544194328, 1.0275443679319596, 1.0280764334766068, 1.0283950403064948, 1.028613111317428, 1.0287744291758496, 1.0289000116360858. $\endgroup$ – Shai Covo Dec 19 '10 at 4:45

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.