# Prove sequence defined by recurrence relation using induction

Confused at this question, from what I gather strong induction is necessary here to prove this but the algebraic step after the Inductive Hypothesis is where I'm not too sure.

Basis:
2 <= a1 = 2 <= 4
2 <= a2 = 2 <= 4

Inductive Hypothesis:
Assume that for any 2 < n <= k, we have that 2 <= an <= 4

Show an+1 is true.

## 1 Answer

Your base case is correct.

Now, fix an $n\geq 3$ and suppose that for all $k<n$, $2\leq a_{k}\leq 4$. We want to show that $2\leq a_{n}\leq 4$. Note that $$a_{n}=\frac{1}{2}\left(a_{n-1}+\frac{8}{a_{n-2}}\right)\leq\frac{1}{2}\left(4+\frac{8}{2}\right)=4$$

and

$$a_{n}=\frac{1}{2}\left(a_{n-1}+\frac{8}{a_{n-2}}\right)\geq \frac{1}{2}\left(2+\frac{8}{4}\right)=2,$$ by the inductive hypothesis.

Hence, $2\leq a_{n}\leq 4$, as desired.

• Thanks so much! Prepping for an exam and while I think I understand induction, some of these recurrence relation questions trip me up sometimes. – SS' Apr 11 '16 at 17:58