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.

In the recursion $ b_{n + 1} = \frac {b_n^2 + 2b_n}{b_n^2 + 2b_n+2}$, with $ b_1 = 1,$ how can one prove that $ \left|\frac{2}{n}-\frac{2\ln{n}}{n^2}-b_n\right|\leq\frac{1}{n^2}$?

share|improve this question

closed as too localized by t.b., Jyrki Lahtonen, J. M., Did, Asaf Karagila Aug 14 '11 at 16:08

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

5  
Have you tried? Try induction and use the recursion. –  Beni Bogosel Aug 14 '11 at 8:57
5  
I edited the tags, because I don't think this has much to do with algebra. But: this has the air of another past contest problem. Do you even try to work on these on your own? Show your work, and then there is much better chance of making progress. Sincerely, I don't think that posting many contest questions here in quick succession is the best way to train your abilities. Honestly: if you are training for a contest, I am trying to be helpful here. If this is not a contest problem from the past, then I apologize. –  Jyrki Lahtonen Aug 14 '11 at 9:49
1  
The function $f(x)=(x^2+2x)/(x^2+2x+2)$ gives the single iteration here. If instead of $f$ the function $$g(x)=\frac{x^2+2x}{(x^2/2)+2x+2}=\frac{2x}{x+2}$$ were used, then starting with $b_1=1$ we would have $b_n=2/(n+1)$ for all $n$. The difference $g(x)-f(x)$ increases about cubically in $x$ from $0$ to $1/15$ in the interval $x\in[0,1]$, so the question is about some kind of stability of the recursively generated sequence under small variations in the function being iterated. I don't know if this helps :-( –  Jyrki Lahtonen Aug 14 '11 at 12:58
3  
Why does this question has 4 close-votes for "too localized"? The technique used to show this can surely be of interest to others. –  Jonas Teuwen Aug 14 '11 at 15:01
5  
@Jonas: It was an (evidently failed) attempt to educate Amir, see my comments here and here. –  t.b. Aug 14 '11 at 15:57

1 Answer 1

up vote 4 down vote accepted

Note that $$ b_{n+1}+1=2\frac{(b_n+1)^2}{(b_n+1)^2+1} $$ Letting $b_n=c_n-1$, we get $$ c_{n+1}=2\frac{c_n^2}{c_n^2+1} $$ Letting $c_n=\frac{1}{d_n}$, we get $$ d_{n+1}=\frac{1}{2}(1+d_n^2) $$ Note that $d_1=\frac{1}{2}$, and if $0\le d_n\le 1$, then $0\le d_{n+1}\le 1$. Thus, $0\le d_n\le 1$ for all $n$.

Letting $d_n=1-e_n$, we get $$ e_{n+1}=e_n-\frac{1}{2}e_n^2 $$ Note that $e_n$ is non-increasing and $0\le e_n\le 1$ for all $n$. Therefore, $\lim_{n\to\infty}e_n$ exists. Thus, $\lim_{n\to\infty}\;\frac{1}{2}e_n^2=\lim_{n\to\infty}(e_n-e_{n+1})=\lim_{n\to\infty}\;e_n-\lim_{n\to\infty}\;e_{n+1}=0$. Therefore, $\lim_{n\to\infty}\;e_n=0$.

Letting $e_n=\frac{1}{f_n}$ (whereby $\lim_{n\to\infty}f_n=\infty$), we get $$ \begin{align} f_{n+1}-f_n&=\frac{1}{2}\frac{f_{n+1}}{f_n}\\ &=\frac{1}{2}\left(1+\frac{f_{n+1}-f_n}{f_n}\right) \end{align} $$ Collecting the $f_{n+1}-f_n$ on the left, we get $$ (f_{n+1}-f_n)\left(1-\frac{1}{2f_n}\right)=\frac{1}{2} $$ So that $$ f_{n+1}-f_n=\frac{1}{2}\left(1+\frac{1}{2f_n}+\frac{1}{4f_n^2}+\frac{1}{8f_n^3}+\dots\right) $$ We can iteratively apply the Euler-Maclaurin Sum Formula starting with $f_n=\frac{a+n}{2}$. Two passses gives $$ f_n=\frac{1}{2}((a+n)+\log(a+n)+\frac{\log(a+n)}{a+n})+O\left(\frac{1}{a+n}\right) $$ Note that $b_n=\frac{1}{f_n-1}$. This yields $b_n=\frac{2}{n}-\frac{2\log(a+n)}{n^2}-\frac{2(a-2)}{n^2}+\dots$.

Had a few minutes, so I added a bit more. Gotta go again; I will finish this later.

share|improve this answer
    
I ran into this thread just now. Just reminding you about the answer, in case you want to finish it. :) –  Srivatsan Feb 21 '12 at 6:22
    
@Srivatsan: The question was closed, so I didn't revisit the answer. However, the asymptotic expansion given yields the requested inequality. I was simply going to add more terms. –  robjohn Feb 21 '12 at 21:58

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