1
$\begingroup$

I'm on problem 18 of baby Rudin, which asks you to describe the behavior of the sequence defined by $$x_{n+1}=\frac{p-1}{p}x_n+\frac{\alpha}{p} x_n^{1-p}$$ with $x_1>\sqrt{\alpha}$, for given $\alpha>1$ and positive integer $p$. From what I can tell it's a common formula for calculating the pth root of alpha, and can be found from applying Newton's method to the equation $x^p-\alpha=0$.

(the restriction on $x_1$ can be changed to be $x_1>(\alpha)^{1/p}$; It's loosely worded. Since I proved in an earlier problem convergence for $p=2$, we can assume $p \ge 3$.)

I can prove directly that $x_{n+1}<x_n$ if and only if $x_n>(\alpha)^{1/p}$, just by expanding the first statement. I've had trouble proving that $x_{n+1}>(\alpha)^{1/p}$ whenever $x_n>(\alpha)^{1/p}$ but it appears to be true.

I have a feeling that the following identity $$x_{n+1}=x_n-\frac{x_n}{p} (1-\frac{\alpha}{x_n^p})$$ is useful, but I'm not sure how I could make use of it.

Does anyone know (hints welcome) how I can prove that this sequence converges to $\alpha^{1/p}$?

(So, monotonicity can be proven as described above, and given that the sequence converges I can prove that it converges to $\alpha^{1/p}$, but I still haven't proved boundedness)

$\endgroup$
1
  • $\begingroup$ How did you prove it for $p=2$? Can you modify your proof to show it for $p=3$? $\endgroup$
    – Calvin Lin
    Jun 10, 2013 at 5:28

1 Answer 1

Reset to default
2
$\begingroup$

Hint: You have a monotonically decreasing sequence.

Hint: A monotonically decreasing sequence that is bounded below, converges to a limit. Show that your sequence is bounded below by using AM-GM

Hint: The limit is unique. Prove that it must satisfy a certain equation which has a unique real root. Hence the limit is $\alpha ^ { \frac{1}{p} } $.

Hint 2's AM-GM on $p-1$ terms of $x_n$ and 1 term of $\alpha x_n^{1-p}$.

$$x_{n+1} = \frac { (p-1) \times x_n + 1 \times (\alpha x_n^{1-p} ) } {p} \geq \sqrt[p]{x_n^{p-1} \times (\alpha x_n^{1-p} ) } = \sqrt[p]{\alpha}$$

$\endgroup$
6
  • $\begingroup$ Thanks! Hmm... still having trouble with proving boundedness below (by $\alpha^{1/p}$ since $0$ isn't strong enough). I'm not sure how I could apply AM-GM to get a useful statement here. The only arguments that have led anywhere are ones based off of concavity of $f(x)=x^p-\alpha$ with Newton's method, but since it hasn't covered differentiation yet I can't really formalize that. :\ $\endgroup$
    – user18862
    Jun 10, 2013 at 15:57
  • $\begingroup$ For future reference (using the boundedness and monotonicity of $\{x_k\}$): given that bound, we see that we can use the fact that $|x_{n+1}-x_{n}|=(x_n^p-\alpha)/(p x_n^{p-1})<\varepsilon$ to get that $x_k^p-\alpha<C\varepsilon$ for constant $C=p x_1^{p-1}$ (from the "useful identity" in the original post), so that in the limit as $k\to\infty$, $x_k^p-\alpha\to 0$, so that $x_k$ approaches the desired value. $\endgroup$
    – user18862
    Jun 10, 2013 at 15:58
  • 1
    $\begingroup$ @NeuroFuzzy Showing bounded below by 0 is sufficient, and it is easy to show that every term will be positive. Since a bounded monotone sequence converges, say that the sequence converges to $L$. What equation must it satisfy? We must have $L = \frac{p-1}{p} L + \frac{\alpha}{p} L^{1-p} $ or that $L^p = \alpha$. $\endgroup$
    – Calvin Lin
    Jun 10, 2013 at 20:48
  • $\begingroup$ it isn't sufficient though since the sequence is only monotonic when $x_n>\alpha^{1/p}$. (I definitely see how to prove $x_n>0$ though) $\endgroup$
    – user18862
    Jun 11, 2013 at 10:45
  • 1
    $\begingroup$ @NeuroFuzzy Sorry, I read your monotone condition wrongly when I saw it again. I've shown how to apply AM-GM to show that it is bounded below by $\alpha^{1/p}$. $\endgroup$
    – Calvin Lin
    Jun 11, 2013 at 13:50

You must log in to answer this question.