Asymptotic estimate of $\binom nk$ 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.
 A: 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.
A: 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$$
