Here is Prob. 24, Chap. 5 in the book Principles of Mathematical Analysis by Walter Rudin, 3rd edition:

The process described in part (c) of Exercise 22 can of course also be applied to functions that map $(0, \infty)$ to $(0, \infty)$.

Fix some $\alpha > 1$, and put $$ f(x) = \frac{1}{2} \left( x + \frac{\alpha}{x} \right), \qquad g(x) = \frac{\alpha+x}{1+x}. $$ Both $f$ and $g$ have $\sqrt{\alpha}$ as their only fixed point in $(0, \infty)$. Try to explain, on the basis of properties of $f$ and $g$, why the convergence in Exercise 16, Chap. 3, is so much more rapid than it is in Exercise 17. (Compare $f^\prime$ and $g^\prime$, draw the zig-zags suggested in Exercise 22.)

Do the same when $0 < \alpha < 1$.

Here are the links to my posts here at Math SE on Prob. 22, Chap. 5, Prob. 16, Chap. 3, and Prob. 17, Chap. 3, in Baby Rudin, 3rd edition:

Prob. 22, Chap. 5 in Baby Rudin: Fixed Points of Real Functions

Prob. 16, Chap. 3 in Baby Rudin: $x_{n+1} = (x_n + \alpha/x_n)/2$, with $x_1 > \sqrt{\alpha}$, $\alpha > 0$

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

My Attempt:

We note that, for $0 < x < \infty$,
$$ g(x) = 1 + \frac{\alpha-1}{x+1},$$ and so $$f^\prime(x) = \frac{1}{2} \left( 1 - \frac{\alpha}{x^2} \right), \qquad g^\prime(x) = - \frac{\alpha-1}{(x+1)^2},$$ and for $\alpha > 1$, we see that, if $x > \sqrt{\alpha}$, then $x^2 > \alpha$, and so $$0 < f^\prime(x) < \frac{1}{2}. $$ which implies (by part (c) of Prob. 22, Chap. 5, in Baby Rudin, 3rd edition) that the sequence $x_0 > \sqrt{\alpha}$, $x_{n+1} = f \left( x_n \right)$, for $n = 0, 1, 2, 3, \ldots$, does converge to the only fixed point of $f$, which is $\sqrt{\alpha}$. In fact, for all $n$, we have $$ \left| x_{n+1} - x_n \right| \leq \frac{1}{2} \left| x_n - x_{n-1} \right| \leq \cdots \leq \frac{1}{2^n} \left| x_1 - x_0 \right|, $$ and so for any $m < n$, we have $$ \begin{align} \left| x_n - x_m \right| &\leq \left| x_n - x_{n-1} \right| + \cdots+ \left| x_{m+1} - x_m \right| \\ &\leq \left( \frac{1}{2^{n-1}} + \cdots + \frac{1}{2^m} \right) \left| x_1 - x_0 \right| \\ &= \frac{1}{2^m} \left( 1 + \cdots + \frac{1}{2^{n-m-1}} \right) \left| x_1 - x_0 \right| \\ &= \frac{1}{2^m} \frac{ 1 - \frac{1}{2^{n-m}} }{ 1 - \frac{1}{2} } \left| x_1 - x_0 \right| \\ &= \left( \frac{1}{2^{m-1}} - \frac{1}{2^{n-1}} \right) \left| x_1 - x_0 \right|, \end{align} $$ and upon letting $n \to \infty$, while keeping $m$ fixed, we obtain $$ \left| x_m - x \right| \leq \frac{1}{2^{m-1}} \left| x_1 - x_0 \right| = \frac{1}{2^{m-1}} \left| \frac{1}{2} \left(x_0 + \frac{\alpha}{x_0} \right) - x_0 \right| = \frac{1}{2^m } \left( x_0 - \frac{\alpha}{x_0} \right), $$ for $m = 1, 2, 3, \ldots$, which gives the rate of convergence of this recursive algorithm.

And, the similar situation occurs for $0 < \alpha < 1$ as well, provided we choose $x_0 > \sqrt{\alpha}$.

Is my analysis correct? Or, have I erred anywhere or missed something of substance?

And, what about $g$? How to analyze it? How to show what Rudin has demanded to be shown?

  • $\begingroup$ f(x) goes back about 19 or 20 centuries to Hero (Heron) of Alexandria. $\endgroup$ Jun 3, 2017 at 22:07
  • $\begingroup$ This looks right. You have the functions and their derivatives, so use L'hopital's rule to find some intermediate function in an interval $ [0,1] $. $\endgroup$
    – McTaffy
    Jun 4, 2017 at 17:05

1 Answer 1


For $f:$

Suppose $x_0>0$ and $a>0$.Let $x_{n+1}=(x_n+a/x_n)/2.$ Assume $x_0\ne \sqrt a \;$( because if $x_0=\sqrt a$ then $x_n=\sqrt a$ for all $n,$ which is a trivial case). Then we have:

(I). $x_1^2>a$ so $x_1>\sqrt a.$

(II). If $x_n^2>a$ then $x_n>x_{n+1}>\sqrt a.$ So by (I), $n\geq 1\implies x_n>x_{n+1}>\sqrt a.$

(III). If $n\geq 1$ and $x_n=k\sqrt a$ with $k\geq 2$ then $x_{n+1}=\sqrt a\;(k+1/k)/2<\sqrt a\;(k+1)/2$, so for some $m>n$ we will have $1<x_m/\sqrt a\;<2.$

(IV). If $1<x_m/\sqrt a<2$ then let $x_n=(1+d_n)\sqrt a$ for each $n$. Then $0<d_m<1.$ We have $$2ad_{m+1}<2ad_{m+1}+ad_{m+1}^2=x_{m+1}^2-a=$$ $$=\frac {1}{4}\left(x_m+\frac {a}{x_m}\right)^2-a=\frac {1}{4}\left(x_m-\frac {a}{x_m}\right)^2=$$ $$=\frac{(x_m^2-a)^2}{4x_m^2}=\frac {(2ad_m+ad_m^2)^2}{4a(1+d_m)^2}<\frac{(2ad_m+2ad_m^2)^2}{4a(1+d_m)^2}=ad_m^2,$$ $$\text {so we have }\quad 0<d_{m+1}<d_m^2<1.$$ By induction on $n,$ for all $n\geq m$ we have $0<d_{n+1}<d_n^2<1.$

Another way to do this: With $x_1>\sqrt a\;,$ let $x_n/\sqrt a\;=\coth T_n$ for $n\geq 1.$ Then when $n\geq 1$ we have $T_{n+1}=2T_n$, so $T_n=2^{n-1}T_1.$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .