Proof by Induction of a Recursively Defined Sequence

Question

The question I'm currently struggling with is:

Consider the following recursively defined sequence:

$$\ a_1 = 0, a_{n+1}= \frac{a^2_n+4}{5} $$

a) Show by induction that $0\le a_n \le 1 $ for all n

b) Prove that if $a_n$ converges, so that $\lim_{n\to \infty}a_n=A$ then $A^2−5A+4 =0$, and thus $A = 1$.

c) Prove by induction that $a_n$ is strictly increasing, $a_{n+1}>a_n$ for all n.

d) Conclude that $\lim_{n \to\infty}a_n$ exists, and thus that $\lim_{n \to \infty}a_n=1$

I've managed to complete part a) where I did:

Basis - at $n=1$ $a_{1+1}=\frac{0+4}{5}$

Inductive Hypothesis - for k as an element of the natural numbers, it is always true that $0 \le a_{k+1} \le 1$ where $a_{k+1}=\frac{a_k+4}{5}$

Inductive Step - Here I tried to prove it by making $n=k+1$ which meant

$a_{k+2}= \frac{a_k+1^2+4}{5}$

which I split in to $\frac{a_k+1^2}{5}+\frac{4}{5}$

and from the inductive hypothesis I know that $0 \le a_{k+1} \le 1$ and therefore it's evident that $\frac{a_k+1^2}{5}$ can take a minimum value of $\frac{0}{5}$ and a minimum value of $\frac{1}{5}$

Part b) seems relatively simple as you can prove

$A^2−5A+4 =0$ quite easily but I'm unsure how to get the equation in the first place. I think it has something to do with rearranging:

$a_{k+1}= \frac{a^2_k+4}{5} $

Part c) is the part I'm struggling with most and the answer in my notes doesn't really explain to me how it's done.

I did the basis and my inductive hypothesis and at the inductive step I got to:

$a_{k+1}^2-5a_{k+1}+4>0$ but I'm not sure what to do after this

Would anyone mind helping me with part c) and d)?

Answer 1

It is $$a_{k+1}^2-5a_{k+1}+4>0$$ and not $a_{k+1}^2-5a_{k+1}-4>0$. So you have $$(a_{k+1}-1)(a_{k+1}-4)>0$$

which is true by a).

Answer 2

The inductive step for the monotonicity (c) is just $$ a_{n+1} > a_n \implies \frac{a^2_{n+1}+4}{5} > \frac{a^2_n+4}{5} \implies a_{n+2} > a_{n+1} $$ The first implication holds because $a_n \ge 0$.

The convergence (d) then follows from the monotone convergence theorem.

Answer 3

b) The argument is that at the fixed point, which has the value A, $$a_{k+1}=a_{k}=A$$
So $$a_{k+1}=\frac{a_k^2+4}{5}$$ becomes $$A=\frac{A^2+4}{5}$$ $$5A=A^2+4$$ $$A^2+5A+4=0$$

Answer 4

a) By the assumption of the induction we obtain: $$0\leq a_{n+1}=\frac{a_n^2+4}{5}<\frac{1^2+4}{5}=1.$$ b),c) $$a_{n+1}-a_n=\frac{a_n^2+4}{5}-a_n=\frac{(a_n-1)(a_n-4)}{5}>0,$$ which says that $a$ increases and bounded.

Thus, there is $\lim\limits_{n\rightarrow+\infty}a_n$ and let this limit be equal to $A$.

Thus, by theorems about limits we obtain: $$A^2-5A+4=0,$$ which gives $A=1$.

I like the following way: $$|a_{n+1}-1|=\left|\frac{a_n^2+4}{5}-1\right|=\frac{a_n+1}{5}|a_n-1|<\frac{2}{5}|a_n-1|<...<\left(\frac{2}{5}\right)^n|a_1-1|\rightarrow0,$$ Which says $$\lim_{n\rightarrow+\infty}a_n=1.$$