# Math Induction

• Feb 27th 2008, 12:46 PM
Ideasman
Math Induction
Given a sequence of #'s $a_1, a_2, a_3, a_4, \ldots$ which is defined by:

$a_1 = 1$
$a_2 = 2$
$a_n = a_{n-1} + a_{n-2}\ \ n \geq 3$

Prove, using math induction:

$a_n < \left(\frac{7}{4}\right)^{n} \ \forall$ integers $n \geq 1$
• Feb 27th 2008, 12:50 PM
galactus
Notice that this is the Fibonacci sequence.
• Feb 27th 2008, 01:12 PM
galactus
I will go ahead and use $f_{n}$ instead of $a_{n}$ because we are dealing with a Fibonacci sequence. Okey-doke.

Prove $f_{n}\leq{(\frac{7}{4})^{n}}$

Show for n=1:

$f_{1}\leq{\frac{7}{4}}\Rightarrow{1\leq{\frac{7}{4 }}}$, TRUE.

Assume $f_{n-1}\leq{(\frac{7}{4})^{n-1}}; \;\ f_{2-1}\leq{(\frac{7}{4})^{2}}=1\leq{\frac{49}{16}}$....TRUE

Since $f_{n}+f_{n-1}=f_{n+1}$, we have:

$f_{n+1}\leq{(\frac{7}{4})^{n}}+(\frac{7}{4})^{n-1}=\frac{11}{4}(\frac{7}{4})^{n-1}$

$f_{n+1}\leq{\frac{11}{4}(\frac{7}{4})^{n-1}}$

$f_{n+1}\leq{(\frac{49}{44})(\frac{11}{4})(\frac{7} {4})^{n-1}}=(\frac{7}{4})^{2}(\frac{7}{4})^{n-1}=(\frac{7}{4})^{n+1}$

$f_{n+1}\leq{(\frac{7}{4})^{n+1}}$

$f_{n+1}\leq{\frac{11}{4}(\frac{7}{4})^{n-1}}<(\frac{7}{4})^{n+1}$

$\therefore, \;\ f_{n}\leq{(\frac{7}{4})^{n}}$

And the induction is complete.
• Feb 28th 2008, 06:14 PM
Ideasman
Where did 49/44 mysteriously come from?
• Feb 29th 2008, 06:40 AM
galactus
it's rather redundant. Notice that $(\frac{49}{\not{44}^{4}})(\frac{\not{11}^{1}}{4})$
$=\frac{49}{16}=(\frac{7}{4})^{2}$