# Prob. 17, Chap. 3 in Baby Rudin: For $\alpha > 1$, how to obtain these inequalities from this recurrence relation?

Here's Prob. 17, Chap. 3 in the book Principles of Mathematical Analysis by Walter Rudin, 3rd edition:

Fix $\alpha > 1$. Take $x_1 > \sqrt{\alpha}$, and define $$x_{n+1} = \frac{\alpha + x_n}{1+x_n} = x_n + \frac{\alpha - x_n^2}{1+x_n}.$$

(a) Prove that $x_1 > x_3 > x_5 > \cdots$.

(b) Prove that $x_2 < x_4 < x_6 < \cdots$.

(c) Prove that $\lim x_n = \sqrt{\alpha}$.

My effort:

From the recursion formula, we can obtain \begin{align} x_{n+1} &= \frac{ \alpha + x_n}{1+ x_n} \\ &= \frac{ \alpha + \frac{\alpha + x_{n-1}}{1+x_{n-1}} }{ 1 + \frac{\alpha + x_{n-1}}{1+x_{n-1}} } \\ &= \frac{ (\alpha + 1) x_{n-1} + 2 \alpha }{ 2x_{n-1} + ( 1 + \alpha ) } \\ &= \frac{\alpha+1}{2} + \frac{2 \alpha - \frac{(\alpha+1)^2}{2} }{2x_{n-1} + ( 1 + \alpha ) } \\ &= \frac{\alpha+1}{2} + \frac{ \alpha - \frac{\alpha^2+1 }{2} }{2x_{n-1} + ( 1 + \alpha ) }. \end{align}

What next?

Notice that $$x_{n+1} = \frac{\alpha+x_n}{1+x_n} = 1 + \frac{\alpha-1}{1+x_n}.$$ Since $\alpha-1>0$, we have that if $x_n<\sqrt{\alpha}$, then $$x_{n+1} > 1 + \frac{\alpha-1}{1+\sqrt{\alpha}} = \frac{1+\sqrt{\alpha}+\alpha-1}{1+\sqrt{\alpha}} = \frac{\sqrt{\alpha}+\alpha}{1+\sqrt{\alpha}} = \sqrt{\alpha}$$ and similarly, if $x_n > \sqrt{\alpha}$, then $x_{n+1} < \sqrt{\alpha}$. Since $x_1>\sqrt{\alpha}$, it follows from induction that $x_n<\sqrt{\alpha}$ for $n$ even and $x_n>\sqrt{\alpha}$ for $n$ odd. In particular, $x_{n+1}-x_n > 0$ if $n$ is even, and $x_{n+1}-x_n < 0$ if $n$ is odd.

Notice that $$x_{n+1} = \frac{\alpha+x_n}{1+x_n}\implies x_{n+1}(1+x_n) = \alpha+x_n \implies x_nx_{n+1} = \alpha - (x_{n+1}-x_n)$$ and hence $$x_n(x_{n+1}-x_{n-1}) = (x_n-x_{n-1}) - (x_{n+1}-x_n).$$ It is clear that $x_n>0$ for all $n$, so we see that if $n$ is odd, then $x_n-x_{n-1}>0$ and $x_{n+1}-x_n<0$, so $x_{n+1}-x_{n-1} > 0$, while if $n$ is even, then $x_n-x_{n-1}<0$ and $x_{n+1}-x_n>0$, so $x_{n+1}-x_{n-1} <0$.

Thus, $x_3-x_1<0$, $x_5-x_3<0$, and so on, so $x_1 > x_3 > x_5 > \dots$, while $x_4-x_2>0$, $x_6-x_4>0$, and so on, so $x_2 < x_4 < x_6 < \dots$.

This proves (a) and (b).

Now, since $x_n>\sqrt{\alpha}$ for $n$ odd, and $x_1>x_3>x_5>\dots$, it follows that the subsequence of odd terms $\{x_{2n-1}\}$ is monotonically decreasing and bounded from below, and hence has a limit (say $L$). Similarly, the subsequence of even terms $\{x_{2n}\}$ is monotonically increasing and bounded from above (namely by $\sqrt{a}$), and so it has a limit as well (say $M$). These limits must satisfy $L\ge\sqrt{\alpha}$ and $M\le\sqrt{\alpha}$. From the equation $$x_{n+1} = \frac{\alpha+x_n}{1+x_n}$$ if we consider $n$ odd and take limits on both sides, we obtain $$M = \frac{\alpha+L}{1+L}$$ while if we consider $n$ even and take limits, we obtain $$L = \frac{\alpha+M}{1+M}.$$ Thus, if we define the sequence $\{y_n\}$ by $y_1 = L$ and $y_{n+1} = \frac{\alpha+y_n}{1+y_n}$, then the sequence $\{y_n\}$ is just $\{L,M,L,M,\dots\}$. If $L>\sqrt{\alpha}$, then we can actually apply what we proved in part (a) to conclude that $y_1 > y_3 > y_5 > \dots$, which is impossible since all odd terms are $L$. Since $L\ge\sqrt{\alpha}$, it must follow that $L = \sqrt{\alpha}$, and you can easily check that this forces $M = \sqrt{\alpha}$ as well. Thus, the odd and even subsequential limits are both $\sqrt{\alpha}$, so the limit of the sequence is $\sqrt{\alpha}$ as well.

• yes, please do enlighten me with your proof of (c) also. Thank you very much for such a beautiful answer!! – Saaqib Mahmood Jan 1 '17 at 10:11
• @SaaqibMahmuud now updated with a proof of (c) as well – Joey Zou Jan 1 '17 at 10:26
• I will remark that to solve for the value of $L$, we could just use your equation relating $x_{n+1}$ and $x_{n-1}$, and take the limit over $n$ even to get the same equation except with $x_{n+1}$ and $x_{n-1}$ replaced with $L$, and then solve for $L$ (it will be a quadratic equation in that case). However, this method avoids potentially messy algebra. – Joey Zou Jan 1 '17 at 10:30
• thank you so much!! Your answer is just fantastic!! – Saaqib Mahmood Jan 1 '17 at 10:36
• which textbook have you used for your first course in analysis, topology, and functional analysis at Chicago? – Saaqib Mahmood May 22 '17 at 14:41

$$\text {Let } a_n=(\sqrt \alpha)\tan (d_n+\pi /4) \text { with } d_n\in (0,\pi /4).$$ Using $\tan (x +\pi /4)=(1+\tan x)/(1-\tan x)$ when $\tan x \ne 1,$ we arrive, after some calculation, that $$\tan d_{n+1}=k \tan d_n$$ $$\text { where } k=\frac {1-\sqrt {\alpha} }{1+\sqrt {\alpha}}.$$ Observe that $0>k>-1$ because $\alpha >1.$

Remark. I tried this substitution by heuristic analogy with a substitution for Heron's method: If $\sqrt {\alpha} \ne b_1>0$ and $b_{n+1}=(b_n+\alpha /b_n)/2,$ then $b_n>\sqrt {\alpha}$ for $n\geq 2.$ Let $b_n=\sqrt {\alpha} \coth c_n$ for $n\geq 2$, with $c_2>0.$ Then $c_n=2^{n-2}c_2$ for $n\geq 2.$ In this Q I tried $\tan$ because $\tan d_n$ alternates $\pm.$

• How is $d_n$ defined? – Arin Chaudhuri Jan 1 '17 at 15:15
• @ArinChaudhuri. In the first line. $d_n=\tan^{-1}(a_n/\sqrt {\alpha}) - \pi /4.$ – DanielWainfleet Jan 2 '17 at 5:11