# Evaluate $\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\{\sqrt{k^2+2k+2}\}$

Evaluate

$$\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\{\sqrt{k^2+2k+2}\}$$

where $\{x\}$ is the fractional part of $x$. Some suggestions here? Thanks!

-
The only thing I can say for now is that $\{\sqrt{k^2+2 k+2}\} = \sqrt{k^2+2 k+2} - (k+1)$ –  Ron Gordon Feb 8 '13 at 9:24
@rlgordonma this is also what I noticed. Since $\{\sqrt{k^2+2k+2}\} = \frac{1}{2k}( 1 + O(\frac{1}{k}) )$, one can check that the extra term behind $\frac{1}{2k}$ drops out from the limit and the final limit is just $\frac{1}{2}$. –  achille hui Feb 8 '13 at 9:42
@achillehui: perhaps you'd like to elaborate in an answer? –  Ron Gordon Feb 8 '13 at 10:06

For $k \ge 1$, we have $$\{\sqrt{k^2+2k+2}\} = \sqrt{(k+1)^2+1)} - (k+1) = \frac{1}{2k}( 1 + m_k )$$ for some bounded sequence $m_k$ which $\to 0$ as $k \to \infty$.

Let $M$ be an upper bound for $|m_k|$. Rewrite the expression in the limit as: \begin{align} &\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\{\sqrt{k^2+2k+2}\}\\ =&\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\frac{1}{2k}( 1 + m_k )\\ =&\frac{1}{2^{n+1}}\sum_{k=1}^{n}\dbinom{n}{k}( 1 + m_k )\\ =&\frac{2^n-1}{2^{n+1}} + \frac{1}{2^{n+1}}\sum_{k=1}^{n}\dbinom{n}{k} m_k \end{align} For any $\epsilon > 0$, pick a $N_1$ large enough such that $|m_k| < \epsilon$ for $k > N_1$. For any $n > N_1$, we have: \begin{align} \left|\frac{1}{2^{n+1}}\sum_{k=1}^{n}\dbinom{n}{k} m_k\right| &\le \frac{M}{2^{n+1}}\sum_{k=1}^{N_1}\dbinom{n}{k} + \frac{\epsilon}{2^{n+1}}\sum_{k=N_1+1}^{n}\dbinom{n}{k}\\ &\le \frac{M}{2^{n+1}}\sum_{k=1}^{N_1}\dbinom{n}{k} + \frac{\epsilon}{2} \end{align} Notice for fixed $N_1$, $\frac{M}{2^{n+1}}\sum_{k=1}^{N_1}\dbinom{n}{k} \to 0$ as $n \to \infty$. We can pick another $N_2 > N_1$ such that this part is $< \frac{\epsilon}{2}$ whenever $n > N_2$. For $n > N_2$, we then have: $$\left|\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\{\sqrt{k^2+2k+2}\} - \frac{1}{2}\right| \le \epsilon + \frac{1}{2^{n+1}}$$ Since $\epsilon$ can be arbitrary small, we conclude: $$\lim_{n\to\infty} \frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\{\sqrt{k^2+2k+2}\} = \frac12$$

-
Well explained! I like this answer. Thanks! –  Chris's sis Feb 8 '13 at 11:34
I just figured out that my sister's question may be computed elementarily by Toeplitz theorem - Chris. –  Chris's sis Feb 9 '13 at 14:33
Great, I learned a new (or forgotten?) thing today! –  achille hui Feb 9 '13 at 23:56

Note that $\{\sqrt{k^2+2k+2}\}=\sqrt{k^2+2k+2}-(k+1)=\frac{1}{\sqrt{k^2+2k+2}+(k+1)}=\frac{1}{2k}+O\left(\frac{1}{k(k+1)}\right)$. \begin{align} & \lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\binom{n-1}{k-1}\{\sqrt{k^2+2k+2}\} \\ & =\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\binom{n-1}{k-1}\frac{1}{2k}+O\left(\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\dbinom{n-1}{k-1}\frac{1}{k(k+1)}\right) \\ & =\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\binom{n}{k}\frac{1}{2n}+O\left(\lim_{n\to\infty}\frac{n}{2^n}\sum_{k=1}^{n}\binom{n+1}{k+1}\frac{1}{n(n+1)}\right) \\ &=\lim_{n\to\infty}\frac{2^n-1}{2^{n+1}}+O\left(\lim_{n\to\infty}\frac{2^{n+1}-1-(n+1)}{2^n(n+1)}\right) \\ &=\frac{1}{2} \end{align}

-
Thanks for your answer (+1) –  Chris's sis Feb 8 '13 at 11:34