17
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 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 '17 at 8:30
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 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 '17 at 20:54
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why are the last two lines equal? $\endgroup$ – πr8 Apr 23 '17 at 12:24
  • $\begingroup$ @πr8 That's an application of 'Laplace Method'. Thanks for your remark. $\endgroup$ – Felix Marin Apr 24 '17 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 '17 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$ – Felix Marin Apr 24 '17 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 '17 at 9:04
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Finally a good correct answer for me to upvote lol $\endgroup$ – Simply Beautiful Art Apr 22 '17 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.