# Simplify $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$

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

-
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. –  Ross Millikan Dec 15 '10 at 15:46
I care more about asymptotic bounds so the floor or the full irrational value is fine with me –  Travis Service Dec 16 '10 at 3:19
For the more general question at the end, may we assume $a,b \geq 1$? –  Shai Covo Dec 16 '10 at 12:52
@Shai Covo yes assume $a,b \geq 1$. In fact I am also interested in the case were $a=b \geq 1$ –  Travis Service Dec 16 '10 at 12:55
I think I'll have a solution soon. –  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.]

-
Maybe some typo in your asymptotic expression? This does not agree with my lower bound, which is much bigger, and with numerical results. –  Shai Covo Dec 16 '10 at 23:28
@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? –  T.. Dec 17 '10 at 5:42
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. –  Shai Covo Dec 17 '10 at 11:38
@Shai: what did the observed ratios (numerical calculation / lower bound) look like for larger $n$ such as 100 or 150? –  T.. Dec 17 '10 at 17:23
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. –  Shai Covo Dec 19 '10 at 4:45