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

  • 6
    $\begingroup$ Have you tried? Try induction and use the recursion. $\endgroup$ – Beni Bogosel Aug 14 '11 at 8:57
  • 5
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 14 '11 at 9:49
  • 1
    $\begingroup$ 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 :-( $\endgroup$ – Jyrki Lahtonen Aug 14 '11 at 12:58
  • 3
    $\begingroup$ Why does this question has 4 close-votes for "too localized"? The technique used to show this can surely be of interest to others. $\endgroup$ – Jonas Teuwen Aug 14 '11 at 15:01
  • 6
    $\begingroup$ @Jonas: It was an (evidently failed) attempt to educate Amir, see my comments here and here. $\endgroup$ – t.b. Aug 14 '11 at 15:57

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.

  • $\begingroup$ I ran into this thread just now. Just reminding you about the answer, in case you want to finish it. :) $\endgroup$ – Srivatsan Feb 21 '12 at 6:22
  • $\begingroup$ @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. $\endgroup$ – robjohn Feb 21 '12 at 21:58

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