# How to prove that $\frac1{n\cdot 2^n}\sum\limits_{k=0}^{n}k^m\binom{n}{k}\to\frac{1}{2^m}$ when $n\to\infty$

I have solve following sum
$$\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}\Longrightarrow \dfrac{\displaystyle\sum_{k=0}^{n}k\binom{n}{k}}{n\cdot 2^n}\to\dfrac{1}{2},n\to\infty$$
$$\sum_{k=0}^{n}k^2\binom{n}{k}=n(n+1)2^{n-2}\Longrightarrow \dfrac{\displaystyle\sum_{k=0}^{n}k^2\binom{n}{k}}{n\cdot 2^n}\to\dfrac{1}{2^2},n\to\infty$$
$$\sum_{k=0}^{n}k^3\binom{n}{k}=2^{n-3}n^2(n+3)\Longrightarrow \dfrac{\displaystyle\sum_{k=0}^{n}k^3\binom{n}{k}}{n\cdot 2^n}\to\dfrac{1}{2^3},n\to\infty$$
so I conjecture the following:
$$\dfrac{\displaystyle\sum_{k=0}^{n}k^m\binom{n}{k}}{n\cdot 2^n}\to\dfrac{1}{2^m},n\to\infty$$
$$\cdots\cdots$$
so I conjecture for $m$ be positive real number also hold.

#### Solutions Collecting From Web of "How to prove that $\frac1{n\cdot 2^n}\sum\limits_{k=0}^{n}k^m\binom{n}{k}\to\frac{1}{2^m}$ when $n\to\infty$"

Let $(Z_i)$ be i.i.d. Bernoulli(1/2) random variables, and set $\bar Z_n={1\over n}\sum_{i=1}^n Z_i$ be the sample average. Then $\bar Z_n\to 1/2$ almost surely by the law of large numbers.

On the other hand, $X=\sum_{i=1}^n Z_i$ has a Binomial$(n,1/2)$ distribution, so
that, $\mathbb{P}(X=k)={n\choose k}(1/2)^n$ for $0\leq k\leq n$.

Therefore, for every real number $m\geq 0$
$$\mathbb{E}(\bar Z_n^m)={1\over n^m}\sum_{k=0}^n {n\choose k} k^m\left({1\over 2}\right)^n \to {1\over 2^m},$$
by the bounded convergence theorem.

You can write your expression as

$$E[\bar{X}^m]n^{m-1}$$
where $\bar{X}=\frac{X_1+\dots+X_n}{n}$ with independent Bernoulli random variables $X_i$. This shows that you are off by $n^{m-1}$. Indeed, if you divide by $n^{m-1}$ you can apply the strong Law of Large Numbers to conclude
$$E[\bar{X}^m]\to E[X_1]^m=(1/2)^m.$$

(*) Justification of the convergence: The SLLN gives pointwise convergence of $\bar{X}^m$ to 1/2. Furthermore, $|\bar{X}|^m$ is always bounded by $1$. Therefore we can apply the dominated convergence theorem.

Another proof (for integer $m$) with elementary algebra: let us define $P_m(n)$ such that
$$\sum_{k=0}^{n}(2k)^m\binom{n}{k}=2^nP_m(n)$$then it can be seen by induction that $P_m(n)$ is a polynomial function of $n$, of order $m$, with $1$ as highest order coefficient.

$P_m(0)=0$ except for $m=0$ where $P_0(0)=1=P_0(n)$

From $\sum_{k=0}^{n+1}(2k)^m\binom{n+1}{k}=2^{n+1}P_m(n+1)$ it is easily derived that

$2^nP_m(n)+2^m\sum_{k=0}^{n}\sum_{j=0}^{m}k^j\binom{m}{j}\binom{n}{k}=2^{n+1}P_m(n+1)$

or $P_m(n+1)=P_m(n)+\sum_{j=0}^{m-1}2^{m-j-1}\binom{m}{j}P_j(n)$

hence, by summing the above over $n$ from $o$ to $n-1$

$$P_m(n)=\sum_{j=0}^{m-1}2^{m-j-1}\binom{m}{j}\sum_{k=0}^{n-1}P_j(k)$$
then the induction hypothesis is: for $0\le j\le m-1$ $P_j(k)$ is polynomial of order $j$ with 1 as coefficient for $k^j$,

then $\sum_{k=0}^{n-1}P_j(k)$ is polynomial in $n$ with same order $j+1$ and same coefficient $\frac{1}{j+1}$ for $n^{j+1}$ as the sum of powers $\sum_{k=0}^{n-1}k^j$

then $P_m(n)=\sum_{j=0}^{m-1}2^{m-j-1}\binom{m}{j}\sum_{k=0}^{n-1}P_j(k)$ is polynomial of order $m$ with $\frac{1}{m}\binom{m}{m-1}=1$ as coefficient for $n^m$.

$P_4(n)=n(n+1)(-2+5n+n^2)$

$P_5(n)=n^2(-10+15n+10n^2+n^3)$

It seems that $P_m(n)$ has integer coefficients.