# Mathematical Induction Help

• May 20th 2009, 09:43 AM
micky_577
Mathematical Induction Help
I have trouble with following question and I was wondering if someone can help me.

For
recurrence relation an = 2an-1 +an-2, a1 = 5 and a2 = 10. Use mathematical induction to show that an < 3^nfor all n >3.

This is how I tried.

Basic step p(3) = 2(10) + 5 = 25 < 3^3

So p(3) is true

Inductive step

an < 3^n
2an + ak-1 < 2*3^n + ak-1
ak+1 < 2*3^n + ak-1

I would appreciate any help.
Thanks

• May 20th 2009, 09:59 AM
Plato
$a_K < 3^K \, \Rightarrow \,a_{K + 1} = 2a_K + a_{K - 1} < 2\left( {3^K } \right) + 3^{K - 1} < 2\left( {3^K } \right) + 3^K = 3(3^K )$