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$.

  • 1
    $\begingroup$ This appears to be related to the expectation of $1/\sqrt{X}$ where $X$ is a binomial(n, 1/2) random variable (but constrained to not be zero). That might at least help give some intuition. $\endgroup$ Apr 22, 2017 at 20:26
  • $\begingroup$ We may also ignore probabilistic arguments, and just follow the steps of a famous French mathematician, leading in a simple and effective way to the approximation $$\sum_{k=1}^{n}\binom{n}{k}\frac{1}{\sqrt{k}}\approx (2^n-1)\sqrt{\frac{2}{n}}.$$ $\endgroup$ Apr 22, 2017 at 23:11
  • $\begingroup$ Another question about the same sum: Limit of a sequence defined by a sum: $\lim_{n\to \infty} \frac1{2^n}\sum_{k=1}^n \frac1{\sqrt k}\binom nk$. Found using Approach0. $\endgroup$ Feb 14, 2018 at 16:53

6 Answers 6


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.

  • 3
    $\begingroup$ Both your arguments are easy to understand. But +1 for putting extra effort to match the level of OP. $\endgroup$
    – Paramanand Singh
    Apr 23, 2017 at 8:30

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.


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$.

  • 4
    $\begingroup$ It might be a good answer but... I don't really understand all these things. I'm in high school. $\endgroup$
    – Liviu
    Apr 22, 2017 at 20:54

$\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}.

  • $\begingroup$ Why are the last two lines equal? $\endgroup$
    – πr8
    Apr 23, 2017 at 12:24
  • $\begingroup$ @πr8 That's an application of 'Laplace Method'. Thanks for your remark. $\endgroup$ Apr 24, 2017 at 0:51
  • $\begingroup$ It's not clear to me how that justifies replacing $(1+e^{-t^2})^n-1$ with the other exponential? $\endgroup$
    – πr8
    Apr 24, 2017 at 0:56
  • $\begingroup$ $\ln\left(\left[1 + \,\mathrm{e}^{-t^{2}}\right]^{n} - 1\right) = \ln\left(2^{n} - 1\right) - {2^{n - 1} \over 2^{n} - 1}\,nt^{2} + \,\mathrm{O}\left(t^{4}\right)$. Please, visit the Laplace Method link. $\endgroup$ Apr 24, 2017 at 1:04
  • $\begingroup$ Thanks - I'd think of that step as basically just being a Taylor expansion (Laplace's method to me is the step of actually giving the integral asymptotics) but I suppose this is mostly semantics. $\endgroup$
    – πr8
    Apr 24, 2017 at 9:04

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.


$$\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$.

  • $\begingroup$ Finally a good correct answer for me to upvote lol $\endgroup$ Apr 22, 2017 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.