Asymptotic estimate of $\binom nk$

Question

Prove: when $n\to \infty$, we have $$\sum_{k=1}^n\frac1{k^a}\binom nk\sim \frac{2^{n+a}}{n^a},$$ where $a$ is a constant. This problem is hard to me, I have no idea.

Answer 1

Hint:

you can use this following identity: $$\sum_{k=1}^{n}\left[\binom{n}{k}\dfrac{\Gamma{(k+1)}}{\Gamma{(k+1+a)}}x^{k+a}\right]=\dfrac{n!}{\Gamma{(n+a+1)}}\sum_{k=1}^{n}\binom{n+a}{k+a}x^{k+a}$$ Proof: Note $$\binom{n}{k}\dfrac{\Gamma{(k+1)}}{\Gamma{(k+1+a)}}=\dfrac{n!}{(n-k)!k!}\dfrac{\Gamma{(k+1)}}{\Gamma{(k+1+a)}}=\dfrac{n!}{(n-k)!\Gamma{(k+1+a)}}$$ so $$LHS=n!\sum_{k=1}^{n}\dfrac{1}{(n-k)!\Gamma{(k+1+a)}}x^{k+a}=\dfrac{n!}{\Gamma{(n+1+a)}}\sum_{k=1}^{n}\dfrac{\Gamma{(n+1+a)}}{(n-k)!\Gamma{(k+1+a)}}x^{k+a}=\dfrac{n!}{\Gamma{(n+a+1)}}\sum_{k=1}^{n}\binom{n+a}{k+a}x^{k+a}$$ Let $x=1$,and note $$\dfrac{\Gamma{(n+1)}}{\Gamma{(n+1+a)}}\to\dfrac{1}{n^a}$$ and $$\sum_{k=1}^{n}\binom{n+a}{k+a}\to 2^{n+a},n\to+\infty$$

Answer 2

There is a simple probabilistic interpretation. Let $(X_i)_{i=1}^{\infty}$ be an i.i.d Bernoulli trials of parameter $1/2$ and let $S_n = X_1 + \cdots + X_n$. Then

$$ \sum_{k=1}^{n} \frac{1}{(k/n)^a} \binom{n}{k} \frac{1}{2^n} = \Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{\{ S_n \geq 1 \}} \Big]. $$

From the Strong Law of Large Numbers (SLLN), we know that

$$ \frac{S_n}{n} \to \frac{1}{2} \quad \text{a.s.} $$

So we can expect that the right-hand side converges to $(1/2)^{-a} = 2^a$, which indeed implies the desired asymptotics.

---

To justify this limiting procedure, one may use various probabilistic estimates to show that $S_n / n$ concentrates near $1/2$ with very high probability. One such example of estimate comes from large deviation theory (though it may be a sledgehammer method).

By the Hoeffding's inequality, for any sufficiently small $\epsilon > 0$ we have

$$ \Bbb{P}(|(S_n/n) - (1/2)| \geq \epsilon) \leq 2 \exp(-2\epsilon^2 n). $$

By the Borel-Cantelli's lemma we know that the event $E_{n,\epsilon} = \{ |(S_n/n) - (1/2)| < \epsilon \}$ eventually holds with probability 1. Now by writing

$$ \Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{\{ S_n \geq 1 \}} \Big] = \Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{E_{n,\epsilon}} \Big] + \Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{\{ S_n \geq 1 \} \cap E_{n,\epsilon}^c} \Big]; $$

we find that

• $\Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{E_{n,\epsilon}} \Big] \to 2^a$ by the bounded convergence theorem, and
• $\Bbb{E}\Big[\frac{1}{(S_n / n)^{a}} \mathbf{1}_{\{ S_n \geq 1 \} \cap E_{n,\epsilon}^c} \Big] \leq n^a \Bbb{P}(E_{n,\epsilon}^c) \leq 2 n^a e^{-2\epsilon^2 n} \to 0$ as $n \to \infty$.

This completes the justification.