1
$\begingroup$

Given a recurrence relation: $$ x_{n+1} = x_n(2-ax_n)\\ 0 < x_1 < {1\over a} \\ a > 0 \\ n\in\Bbb N $$ Prove that $x_n$ converges and: $$ \lim_{n\to\infty} x_n = {1\over a} $$

Consider the recurrence relation: $$ \begin{align} x_{n+1} &= x_n(2-ax_n) \\ x_{n+1} &= 2x_n-ax_n^2 \\ {x_{n+1}\over a} &= {2x_n\over a}-x_n^2\\ -{x_{n+1}\over a} &= x_n^2 - {2x_n\over a} \\ -{x_{n+1}\over a} &= x_n^2 - {2x_n\over a} + {1\over a^2} - {1\over a^2} \\ {1\over a^2} - {x_{n+1}\over a} &= x_n^2 - {2x_n\over a} + {1\over a^2} \\ {1\over a^2} - {x_{n+1}\over a} &= \left(x_n - {1\over a}\right)^2 \\ {1\over a}\left({1\over a} - x_{n+1}\right) &= \left(x_n - {1\over a}\right)^2 \end{align} $$

Define a new sequence: $$ y_n = {1\over a} - x_n $$ Thus the recurrence becomes: $$ {y_{n+1}\over a} = y_n^2 \\ y_{n+1} = ay_n^2 $$

Now search for the pattern as $n$ increases: $$ \begin{align} y_1 &= {1\over a} - x_1 \\ y_2 &= a y_1^2\\ y_3 &= a^3 y_1^4\\ y_4 &= a^7 y_1^8\\ &\dots\\ y_{n+1} &= a^{2^n - 1}y_1^{2^n} = a^{2^n - 1}\left({1\over a} - x_1\right)^{2^n}\\ y_{n+1} &= a^{-1}\left(1 - ax_1\right)^{2^n} \end{align} $$

Based on initial conditions $x_1 < {1\over a}$, therefore: $$ 0 < x_1 < {1\over a} \iff ax_1 < 1 \\ \implies \lim_{n\to\infty} (1 - ax_1)^{2^n} = 0 $$

Hence: $$ \lim_{n\to\infty}y_n = 0 \implies \lim_{n\to\infty} \left({1\over a} - x_n \right) = 0 \implies \lim_{n\to\infty} x_n = {1\over a} $$

I would like to kindly request a verification of the proof above. Interestingly this recurrence eventually gives a reciprocal of the number $a$. Thank you!

$\endgroup$
  • $\begingroup$ the proof looks good $\endgroup$ – Mike Hawk Jan 31 at 16:51
1
$\begingroup$

Your proof is correct but I would make two remarks.

The first one is to delete the 5th line of the "Consider the recurrence relation" section. You add $0 = 1/a^2 - 1/a^2$ and after you pass $-1/a^2$ on the other side of the equation. You could have directly add $1/a^2$ on both sides which is a more common operation than "adding 0" and it would already have gave you the 6th line.

The other one is, if you do it for school work, to prove explicitly the formula for $y_{n+1}$. This can easily be done by recurrence and "Now search for the pattern as n increases" can let a corrector think that either you do not know how to do a proper recurrence or worst that you think that if a formula gives you the correct result for the first terms it implies that it works for all terms. This could be penalizing on an exam with a tired professor (after 20 bad copies you tend to be less forgiving).

$\endgroup$
  • $\begingroup$ I'm a self-learner, so this is just one of the problems from the book i'm solving. I agree with both parts. As for the second one I would rephrase "Now search for the pattern as n increases..." to "Using induction we may show that...". Thank you for taking your time! $\endgroup$ – roman Jan 31 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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