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$.
Answer
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.
No comments:
Post a Comment