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!
 A: 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$$
A: 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}
