Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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}

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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