Find $ \lim\limits_{{n \to \infty}} \frac1{2^n} \sum\limits_{k=1}^n \frac1{\sqrt{k}} \binom nk$ Find
$$\lim_{n \to \infty} \frac {1}{2^n} \sum_{k=1}^n \frac{1}{\sqrt{k}} \binom{n}{k}.$$
First time I thought about Stirling's approximation but didn't get anything by applying it. I would also think about a Riemann Sum, but no idea how to rewrite...
The answer is $0$.
 A: 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.
A: 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$. 
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\lim_{n \to \infty}\bracks{{1 \over 2^{n}}\sum_{k = 1}^{n}
{{n \choose k} \over \root{k}}} & =
\lim_{n \to \infty}\bracks{{1 \over 2^{n}}\sum_{k = 1}^{n}
{n \choose k}\,{1 \over \root{\pi}}\int_{0}^{\infty}t^{-1/2}\expo{-kt}\,\dd t}
\\[5mm] & =
{1 \over \root{\pi}}\lim_{n \to \infty}\bracks{{1 \over 2^{n}}\int_{0}^{\infty}{\pars{1 + \expo{-t}}^{n} - 1 \over t^{1/2}}\,\dd t}
\\[5mm] & =
{1 \over \root{\pi}}\lim_{n \to \infty}\braces{{1 \over 2^{n - 1}}
\int_{0}^{\infty}\bracks{{\pars{1 + \expo{-t^{2}}}^{n} - 1}}\,\dd t}
\label{1}\tag{1}
\\[5mm] & =
{1 \over \root{\pi}}\lim_{n \to \infty}\bracks{{1 \over 2^{n - 1}}
\int_{0}^{\infty}\pars{2^{n} - 1}
\exp\pars{-\,{2^{n - 1} \over 2^{n} - 1}\,n\,t^{2}}\,\dd t}
\label{2}\tag{2}
\\[5mm] & = \bbx{\ds{0}}
\end{align}

In line \eqref{1}, I used the Laplace Method to 'arrive' to line \eqref{2}.

A: The limit is part of a broad class of limits for which the classical analysis designed Toeplitz theorem. The theorem says that given an array of real numbers, $\lambda_{n,k}: 1\le k\le n,\  n\ge1 $, such that: $i) \ \lim_{n\to\infty}\lambda_{n,k}=0, \ \forall k\in \mathbb{N}$, $ii) \lim_{n\to\infty} \sum_{k=1}^n \lambda_{n,k}=1$ and $iii)$ there exists $C>0$ such that for all positive integers $n$, $\sum_{k=1}^n |\lambda_{n,k}|\le C$, then for any convergent sequence $\delta_k$, we have 
$$\lim_{n\to\infty} \sum_{k=1}^n \lambda_{n,k} \delta_k=\lim_{n\to\infty}\delta_n .$$
In your problem set $\displaystyle \lambda_{n,k}=\frac{1}{2^n}\binom{n}{k}$ and $\displaystyle \delta_k=\frac{1}{\sqrt{k}}$, and since the conditions are satisfied, we have
$$\displaystyle \lim_{n \to \infty} \frac {1}{2^n} \displaystyle \sum_{k=1}^n \frac{\displaystyle \binom{n}{k}}{\sqrt{k}}=\lim_{n\to\infty} \frac{1}{\sqrt{n}}=0,$$
which ends the little proof.
A: $$\lim_{n \to \infty} \frac {1}{2^n} \sum_{k=1}^n \frac{{n}\choose{k}}{\sqrt{k}}=0$$
I offer a sketch proof. The basic idea is as follows: for large $n$, the small values of $k$ will make small contributions, because $\frac{{n \choose k}}{2^n}$ will be small there, and the large values of $k$ will make small contributions because $\sqrt{\frac{1}{k}}$ will be small there. Thus, the whole sum should be small too.


*

*Write $f(x)=x^{-1/2}\mathbb{I}(x\ge 1)$, and let $X$ denote a binomial random variable with parameter $1/2$ and $n$ trials.

*Then, the term we are taking limits of is $\mathbb{E}f(X)$

*The Central Limit Theorem says that, for large $n$, we have that $X\approx N(n/2,n/4)$ as distributions.

*We can thus (handwaving a bit) deduce that $$\frac{{n}\choose{k}}{2^n} \approx\sqrt{\frac{2}{\pi n}}\exp\left(-\frac{(2k-n)^2}{2n}\right)$$


*

*One could also establish this via Stirling's formula, or likely other methods, if need be.


*Take some $\epsilon\in(0,1/3)$, and split the sum up into $1\le k\le (1-\epsilon)\frac{n}{2}, k>(1-\epsilon)\frac{n}{2}$.


*

*In the first case, we have $$(2k-n)^2 \geq \epsilon^2n^2 \implies \exp\left(-\frac{(2k-n)^2}{2n}\right) \le \exp\left(-\frac{n\epsilon^2}{2}\right).$$ Thus, approximately, $$\frac {1}{2^n} \sum_{k=1}^{(1-\epsilon)\frac{n}{2}} \frac{{n}\choose{k}}{\sqrt{k}} \le \sum_{k=1}^{(1-\epsilon)\frac{n}{2}}\sqrt{\frac{2}{\pi n k}}\exp\left(-\frac{n\epsilon^2}{2}\right) \le(1-\epsilon)\sqrt{\frac{n}{2\pi}}\exp\left(-\frac{n\epsilon^2}{2}\right)\to 0$$

*For the remainder of the sum, we have $$\frac {1}{2^n} \sum_{k>(1-\epsilon)n/2} \frac{{n}\choose{k}}{\sqrt{k}} \le \sum_{k>(1-\epsilon)n/2} \frac{{n}\choose{k}}{2^n}\sqrt{\frac{2}{{(1-\epsilon)n}}} \le \sum_{k\ge0} \frac{{n}\choose{k}}{2^n}\sqrt{\frac{2}{{(1-\epsilon)n}}}=\sqrt{\frac{2}{{(1-\epsilon)n}}}\to 0.$$



Thus, as desired, the limit is $0$.
A: 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.
