enter image description here

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.

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.


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


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

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

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.