Find $ \lim\limits_{{n \to \infty}} \frac1{2^n} \sum\limits_{k=1}^n \frac1{\sqrt{k}} \binom nk$

Solution 1:

Let $a_k = k^{-1/2}$. Notice that $(a_k)$ decreases to $0$. Then for each fixed $m \geq 1$ and for all $n \geq m$,

$$ \frac{1}{2^n} \sum_{k=1}^{n} \binom{n}{k} a_k \leq \frac{1}{2^n} \underbrace{\sum_{k=1}^{m} \binom{n}{k} (a_k - a_m)}_{= \mathcal{O}(n^m)} + \frac{1}{2^n} \underbrace{\sum_{k=1}^{n} \binom{n}{k} a_m}_{=(2^n - 1)a_m}. $$

Taking limsup as $n\to\infty$, it follows that

$$ \limsup_{n\to\infty} \frac{1}{2^n} \sum_{k=1}^{n} \binom{n}{k} a_k \leq a_m $$

Since $a_m \to 0$ as $m\to\infty$, this proves

$$ \lim_{n\to\infty} \frac{1}{2^n} \sum_{k=1}^{n} \binom{n}{k} a_k = 0. $$

Addendum. I just saw that OP is a high-school student. Here is a little tweak of the argument above that does not use any fancy analysis stuffs.

Let $m_n = \lfloor \log n \rfloor$. Then for $n \geq 3$, we always have $1 \leq m_n \leq n$. Then

\begin{align*} 0 \leq \frac{1}{2^n} \sum_{k=1}^{n} \binom{n}{k} \frac{1}{\sqrt{k}} &= \frac{1}{2^n} \sum_{k=1}^{m_n} \binom{n}{k} \frac{1}{\sqrt{k}} + \frac{1}{2^n} \sum_{k=m_n + 1}^{n} \binom{n}{k} \frac{1}{\sqrt{k}} \\ &\leq \frac{1}{2^n} \sum_{k=1}^{m_n} n^k + \frac{1}{2^n} \sum_{k=m_n + 1}^{n} \binom{n}{k} \frac{1}{\sqrt{m_n}} \tag{1} \\ &\leq \frac{n^{1+m_n}}{2^n} + \frac{1}{\sqrt{m_n}}. \tag{2} \end{align*}

For $\text{(1)}$ I utilized the fact that $\binom{n}{k} \leq n^k$ and $\frac{1}{\sqrt{k}}$ is decreasing. For $\text{(2)}$ I utilized the geometric sum formula and the identity $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.

Now taking $n\to\infty$ and applying the squeezing lemma proves the claim.

Solution 2:

It is enough to apply Laplace's method.

Through the inverse Laplace transform we have $\frac{1}{\sqrt{k}}=\int_{0}^{+\infty}\frac{e^{-ks}}{\sqrt{\pi s}}\,ds $, hence

$$ \sum_{k=1}^{n}\binom{n}{k}\frac{1}{\sqrt{k}} = \int_{0}^{+\infty}\frac{-1+(1+e^{-s})^n}{\sqrt{\pi s}}\,ds =\frac{2}{\sqrt{\pi}}\int_{0}^{+\infty}\left[(1+e^{-s^2})^n-1\right]\,ds$$ where the last integrand function behaves like $(2^n-1) e^{-ns^2/2}$.
It follows that $$ \sum_{k=1}^{n}\binom{n}{k}\frac{1}{\sqrt{k}} \approx (2^n-1)\sqrt{\frac{2}{n}} $$ and the wanted limit is simply zero.

Solution 3:

Using Abel's summation and the fact that $\sum \limits_{k=1}^{n} \binom{n}{k} = 2^{n}-1$ you can solve the above question.

From the Abel's summation we can say that $\sum \limits_{k=1}^{n} \frac{\binom{n}{k}}{\sqrt{k}} \approx \frac{\sum \limits_{k=1}^{n} \binom{n}{k}}{\sqrt{n}}-\int \limits_{1}^{n} ( \sum \limits_{k=1}^{t} \binom{t}{k} \frac{d}{dx}(\sqrt{t})) dt $

By substituting we arrive at : $ \frac{2^{n}-1}{\sqrt{n}}-\int \limits_{1}^{n} ( 2^{t}-1) \frac{d}{dx}(\sqrt{t}) dt $

It easy by comparison tests to bound the integral part by $\frac{2^n}{\sqrt{n}}$.

So its at most between $0$ and $2\frac{2^n}{\sqrt{n}}$ which both approach $0$ when divided by $2^n$ when $n \to \infty$.