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.

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)

share|improve this question
    
How did you prove it for $p=2$? Can you modify your proof to show it for $p=3$? –  Calvin Lin Jun 10 '13 at 5:28

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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. :\ –  NeuroFuzzy Jun 10 '13 at 15:57
    
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. –  NeuroFuzzy Jun 10 '13 at 15:58
    
@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$. –  Calvin Lin Jun 10 '13 at 20:48
    
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) –  NeuroFuzzy Jun 11 '13 at 10:45
    
@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}$. –  Calvin Lin Jun 11 '13 at 13:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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