Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ This is from Polya's Problems and Theorems in Analysis, Vol. 1, Part II, Problem 40. The proof provided in the book is too simple. It says details can be found in Jordan's Cours d'Analyse, Vol.2, 3rd Ed, pp. 218-221. However, I cannot find this edition online, and what's worse, there is not any English translations. Can anyone give a proof in detail?
Analysis – Asymptotic Expression of Sum of Powers of Binomial Coefficients
analysisasymptoticsbinomial-coefficients
Related Solutions
Your sum is a special case of Dixon's well-poised sum
$$\begin{align*} \sum_{k=0}^\infty (-1)^k \binom{n}{k}^3&={}_3 F_2\left({{-n,-n,-n}\atop{1,1}}\mid 1\right)\\ &=\frac{\Gamma\left(1-\frac{n}{2}\right)\Gamma \left(\frac{3 n}{2}+1\right)}{n!\Gamma(1-n)\Gamma\left(\frac{n}{2}+1\right)^2}=\frac{\cos\left(\frac{\pi n}{2}\right)\left(\frac{3n}{2}\right)!}{\left(\left(\frac{n}{2}\right)!\right)^3} \end{align*}$$
Generally,
$$\sum_{k=0}^\infty (-1)^k \binom{n}{k}^p={}_p F_{p-1}\left({{-n,\cdots,-n}\atop{1,\cdots,1}}\mid (-1)^{p+1}\right)$$
since $\dbinom{n}{k}=\dfrac{(-1)^k (-n)_k}{k!}$, and $(1)_k=k!$ and thus
$$\sum_{k=0}^\infty (-1)^k \binom{n}{k}^p=\sum_{k=0}^\infty (-1)^k \left(\frac{(-1)^k (-n)_k}{k!}\right)^p=\sum_{k=0}^\infty ((-1)^{p+1})^k \frac{((-n)_k)^p}{((1)_k)^{p-1} k!}$$
and the hypergeometric form is now noticeable.
Note that by choosing $x=a_{n-1}$, Peano's theorem has the following immediate consequence, for any $a < b$ and $\epsilon > 0$.
Lemma 1: If $f\colon[a,b]\to\mathbb{R}$ is differentiable, then there exists $x\in[a,b)$ satisfying $$ \left\lvert\frac{f(b)-f(x)}{b-x}-f^\prime(x)\right\rvert\lt\epsilon. $$
This lemma is obviously true for continuously differentiable functions simply by taking $x$ to be close enough to $b$. For functions with non-continuous derivatives, however, things are more difficult, and the inequality can fail for $x$ arbitrarily close to $b$. Starting with this lemma, we can also go in the opposite direction, and prove Peano's theorem, which I will do now. I'll also give a proof of the Lemma, showing that Peano's theorem is indeed true.
First, the natural way to try and prove Peano's theorem is to start with $a_0$ and then inductively choose values for $a_1,a_2,\ldots$. Once $a_i$ has been chosen then, if $a_i=b$ we are done. If not then, by the definition of the derivative of $f$ at $a_i$, there does exist $a_{i+1}\in(a_i,b]$ satisfying the required inequality. In order to maximise the chance of covering the interval $[a,b]$ in a finite number of steps, it would seem to be prudent to choose $a_{i+1}$ as large as possible and $a_{i+1}=b$ if possible. Unfortunately, this approach does not always work, and it is possible that you just end up generating an infinite increasing sequence $a_i$ in the interval $[a,b)$.
A method that does succeed is to, instead, work from the right to the left. That is, start by choosing $b_0=b$ and inductive define a decreasing sequence $b_0\gt b_1\gt b_2\gt\cdots\gt b_n=a$ such that $$ \left\lvert\frac{f(b_i)-f(b_{i+1})}{b_i-b_{i+1}}-f^\prime(b_{i+1})\right\rvert\lt\epsilon. $$ Then Peano's theorem follows by taking $a_i=b_{n-i}$.
If, for any $x\in(a,b]$ we let $S_x$ be the set of $y\in[a,x)$ with $\lvert(f(x)-f(y))/(x-y)-f^\prime(y)\rvert\lt\epsilon$ then, Lemma 1 applied to the interval $[a,x]$ says that $S_x$ is nonempty. Choosing a sequence $\delta_0,\delta_1,\ldots$ of positive reals tending to zero, select $b_0,b_1,\ldots$ as follows.
- $b_0=b$.
- Once $b_i$ has been chosen, if $b_i > a$ then take $b_{i+1}\in S_{b_i}$ with $b_{i+1}\le\inf S_{b_i}+\delta_i$. If possible, choose $b_{i+1}=a$.
- If $b_i=a$ then we are done.
Note that, as Lemma 1 implies that $S_{b_i}$ is non-empty whenever $b_i > a$, then this process continues either indefinitely or until $b_i=a$.
Lemma 2: The sequence $\{b_i\}$ terminates with $b_n=a$ for some $n$.
Proof: (Note: This proof will assume Lemma 1) Using proof by contradiction, suppose that the sequence $b_0,b_1,\ldots$ does not terminate. In this case, it decreases to a limit $c\in[a,b)$. If $c=a$ then, by the definition of the derivative at $a$, we have $\lvert (f(b_i)-f(a))/(b_i-a)-f^\prime(a)\rvert\lt\epsilon$ for large $i$. By the procedure above, we would choose $b_{i+1}=a$ and the sequence terminates, contradicting the assumption.
If $c > a$ then, using Lemma 1 applied to the interval $[a,c]$, there exists an $x\in[a,c)$ with $\lvert(f(c)-f(x))/(c-x)-f^\prime(x)\rvert\lt\epsilon$. By the continuity of $f$ at $c$, we have $\lvert(f(b_i)-f(x))/(b_i-x)-f^\prime(x)\rvert\lt\epsilon$ for all large $i$, so $x\in S_{b_i}$. By the procedure above, we choose $b_{i+1}\lt x + \delta_i$. Taking $i$ large enough that $\delta_i\le c-x$ this gives $b_{i+1}\lt c$, contradicting the property that $b_i$ decreases to $c$. QED
To finish off the post:
Proof of Lemma 1: By the definition of the derivative at $b$, there exists $\delta\gt0$ such that $\lvert(f(b)-f(x))/(b-x)-f^\prime(b)\rvert\lt\epsilon/2$ whenever $x\gt b-\delta$. Choosing $y\in[a,b)$ with $y\gt b-\delta$, applying the mean value theorem gives $x\in(y,b)$ such that $f^\prime(x)=(f(b)-f(y))/(b-y)$. Then, $$ \begin{align} \left\lvert\frac{f(b)-f(x)}{b-x}-f^\prime(x)\right\rvert &= \left\lvert\frac{f(b)-f(x)}{b-x}-\frac{f(b)-f(y)}{b-y}\right\rvert\cr &\le \left\lvert\frac{f(b)-f(x)}{b-x}-f^\prime(b)\right\rvert + \left\lvert\frac{f(b)-f(y)}{b-y}-f^\prime(b)\right\rvert\cr &\lt\epsilon/2+\epsilon/2=\epsilon. \end{align} $$ QED
So, Peano's theorem is true. However, I made use of the mean value theorem in the proof of Lemma 1, so this does not give a method of proving the mean value inequality. That would be circular. The real problem is to prove Peano's theorem without making use of anything as strong as the mean value inequality. However, in my opinion, Peano's theorem is more difficult to prove than the MVT (or an approximate form of it), so does not give a useful step in proving the mean value inequality.
Best Answer
That kind of asymptotics follows from the Central Limit Theorem. If we consider the binomial random variable $X=B(n,1/2)$ as the sum of $n$ independent Bernoulli trials, we have: $$\mathbb{E}[X]=\frac{n}{4}, \qquad \operatorname{Var}[X]=\frac{n}{4}$$ from which the approximation: $$\frac{1}{2^n}\binom{n}{n/2+r}\approx \sqrt{\frac{2}{n\pi}}\exp\left(-\frac{2r^2}{n}\right).\tag{1}$$ By considering the $k$-th power of both terms and summing over $r\in[-n/2,n/2]$ (the main contribute is clearly given by the central binomial coefficient and its neighbours) we get: $$\sum_{r=-n/2}^{n/2}\binom{n}{n/2+r}^k \approx 2^{kn}\left(\frac{2}{\pi n}\right)^{\frac{k}{2}}\sum_{r=-n/2}^{n/2}\exp\left(-\frac{2kr^2}{n}\right)\tag{2}$$ and the claim follows from approximating the last sum with: $$\int_{-\infty}^{+\infty}\exp\left(-\frac{2kx^2}{n}\right)\,dx = \sqrt{\frac{\pi n}{2k}}.\tag{3}$$