Exercise 3.18

Question

\def\where{\,|\,}
Exercise 18:
    Replace the recursion formula of Exercise 16 by $$x_{n+1}=\frac{p-1}{p}\,x_n+\frac{\alpha}{p}\,x_n^{-p+1}$$ where $p$ is a fixed positive integer, and describe the
    behavior of the resulting sequences $\{x_n\}$.

Dan Whitman · Accepted Answer

\def\where{\,|\,} \def\pra{\sqrt[p]\alpha} \def\sa{\sqrt\alpha} \textbf{Lemma 3.18.1:} For an integer $p \geq 1$ and real $a$ where $0 < a < 1$ $$ p(1-a) \geq 1 - a^p \,. $$ \emph{Proof:} We have \begin{align*} p &= \sum_{n=0}^{p-1} 1 = \sum_{n=0}^{p-1} 1^n \geq \sum_{n=0}^{p-1} a^n && \text{(equality when $p=1$)}\ &= \frac{1-a}{1-a} \sum_{n=0}^{p-1} a^n = \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n - a\sum_{n=0}^{p-1} a^n\right) && \text{(since $1-a \neq 0$)} \ &= \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n - \sum_{n=0}^{p-1} a^{n+1}\right) \ &= \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n - \sum_{n=1}^{p} a^n\right) \ &= \frac{1}{1-a} \left(a^0 + \sum_{n=1}^{p-1} a^n - \sum_{n=1}^{p-1} a^n - a^p\right) \ &= \frac{1}{1-a} \left(1 - a^p\right) \,. \end{align*} From this the desired result follows immediately since $1-a > 0$. \qedsymbol Now we assume that for this family of sequences we always have $x_1 > \pra$ and we claim that the sequence converges to $\pra$ for a given $p$. So assume that $p$ is a fixed positive integer. First we claim that $x_n > \pra$ for all $n \geq 1$. We show this by induction. The $n=1$ case is by construction so assume that $x_n > \pra$. We then have $$ x_n > \pra > 0 $$ $$ 1 > \frac{\pra}{x_n} > 0\,. $$ So then by Lemma~3.18.1 above we have \begin{align*} p\left(1 - \frac{\pra}{x_n}\right) &\geq 1 - \left(\frac{\pra}{x_n}\right)^p \ p - p\frac{\pra}{x_n} &\geq 1 - \frac{\alpha}{x_n^p} \ p + \frac{\alpha}{x_n^p} &\geq 1 + p\frac{\pra}{x_n} \ p x_n + \frac{\alpha}{x_n^{p-1}} &\geq x_n + p\pra && \text{(since $x_n > 0$)} \ (p-1) x_n + \frac{\alpha}{x_n^{p-1}} &\geq p\pra \ \frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}} &\geq \pra \ x_{n+1} &\geq \pra \,. \end{align*} Given this it is easy to show that $\{x_n\}$ decreases monotonically. Since $x_n \geq \pra$ for any $n \geq 1$, clearly $x_n^p \geq \alpha$. Therefore we have $$ x_{n+1} = \frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}} \leq \frac{p-1}{p} x_n + \frac{x_n^p}{p x_n^{p-1}} = \frac{p-1}{p} x_n + \frac{x_n}{p} = \frac{p - 1 + 1}{p} x_n = \frac{p}{p} x_n = x_n \,. $$ So since $\{x_n\}$ is bounded (above by $x_1$ and below by $\pra$) and monotic, it converges by Theorem~3.14. So let $x = \lim_{n\to\infty} x_n$, and then clearly $\lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} x_n = x$ also. Therefore we have $$ \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} \left(\frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}}\right) $$ $$ = \left(\frac{p-1}{p} \lim_{n\to\infty} x_n + \frac{\alpha}{p \lim_{n\to\infty} x_n^{p-1}}\right) $$ $$= \left(\frac{p-1}{p} x + \frac{\alpha}{p x^{p-1}}\right) = x \,. $$ Solving this straightforward equation for $x$ results in $x = \pra$. Thus these sequences provide a means by which the $p$th root of a real number can be calculated (approximately), and it is worth mentioning that the $p=2$ case corresponds to the sequence in Exercise~3.16 for the square root.

Round · Answer

Assume $x_1>0$. Then $x_n>0$. Similarly to Exercise 3.16, we conjecture the following two properties and prove them: (a) $\{x_n\}$ decreases monotonically for $n\geq 2$; (b) $\lim x_n = \sqrt[p]{\alpha}$. Since $$ \frac{x_{n+1}}{x_n}=\frac{p-1}{p}+\frac{\alpha x_n^{-p}}{p},$$ to prove (a), it suffices to show that \begin{equation*} \alpha x_n^{-p}\leq 1 \quad ext{for}\quad n\geq 2, \end{equation*} which is equivalent to \begin{equation} x_n\geq \sqrt[p]{\alpha} \quad ext{for}\quad n\geq 2. \label{x>sqrt} \end{equation} We now prove \eqref{x>sqrt}. \begin{equation} \begin{aligned} \frac{x_{n+1}}{\sqrt[p]{\alpha}} &= \frac{p-1}{p}x_n\alpha^{-\frac{1}{p}}+\frac{\alpha^{1-\frac{1}{p}}}{p}x_n^{-p+1}\ &= \frac{p-1}{p}x_n\alpha^{-\frac{1}{p}}+\frac{1}{p}(x_n\alpha^{-\frac{1}{p}})^{-p+1}. \end{aligned} \label{x_n+1/sqrt} \end{equation} For $$f(y)=\frac{p-1}{p}y+\frac{1}{p}y^{-p+1},$$ since \begin{equation*} \begin{aligned} f'(y) &= \frac{p-1}{p}(1-y^{-p}) \ &\begin{cases} <0, &00, &y>1, \end{cases} \end{aligned} \end{equation*} $f(y)\geq f(1)=1$ for $y>0$. By \eqref{x_n+1/sqrt}, $$x_{n+1}\geq \sqrt[p]{\alpha},$$ implying \eqref{x>sqrt}. This proves (a). Since $\{x_n\}$ is monotonic and bounded, it converges. Let $x=\lim x_n$. Then $\lim x_{n+1}=x$. Taking the limits of the LHS and RHS of the condition in the question implies $$x=\frac{p-1}{p}x+\frac{\alpha}{p}x^{-p+1},$$ which implies $x=\sqrt[p]{\alpha}.$ This proves (b).

Exercise 3.18

Answers

Comments

Comments

Exercise 3.18

Answers

Comments

Comments

Add answer