1. ## Math Induction

Given a sequence of #'s $\displaystyle a_1, a_2, a_3, a_4, \ldots$ which is defined by:

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

Prove, using math induction:

$\displaystyle a_n < \left(\frac{7}{4}\right)^{n} \ \forall$ integers $\displaystyle n \geq 1$

2. Notice that this is the Fibonacci sequence.

3. I will go ahead and use $\displaystyle f_{n}$ instead of $\displaystyle a_{n}$ because we are dealing with a Fibonacci sequence. Okey-doke.

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

Show for n=1:

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

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

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

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

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

$\displaystyle 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}$

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

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

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

And the induction is complete.

4. Where did 49/44 mysteriously come from?

it's rather redundant. Notice that $\displaystyle (\frac{49}{\not{44}^{4}})(\frac{\not{11}^{1}}{4})$
$\displaystyle =\frac{49}{16}=(\frac{7}{4})^{2}$