0
$\begingroup$

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.

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2016 at 17:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .