discrete mathematics - Let $a_1=1$, $a_2=3$ , and for $n ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < left(frac{7}{4}right)^n$ for all natural numbers.

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers.

I assume I'm supposed to use induction. base step is easy. I'm stuck on how to form the inductive step. Any tips are greatly appreciated.

Answer

Here is the inductive step for anyone reading this...

Assuming $P(k-2)$: $a_{k-2} < \left(\frac{7}{4}\right)^{k-2}$

Assuming $P(k-1)$: $a_{k-1} < \left(\frac{7}{4}\right)^{k-1}$

Definition of $a_k$: $a_k=a_{k-1}+a_{k-2}$

Combining with inductive assumptions: $a_k < \left(\frac{7}{4}\right)^{k-2} + \left(\frac{7}{4}\right)^{k-1}$

Algebraically factor out $\left(\frac{7}{4}\right)^{k-2}$: $a_k < \left(\frac{7}{4}\right)^{k-2} \cdot \left(1 + \frac{7}{4}\right)$

$a_k < \left(\frac{7}{4}\right)^{k-2} \cdot \frac{11}{4} = \left(\frac{7}{4}\right)^k \cdot \left(\frac{4}{7}\right)^2 \cdot \frac{11}{4} = \left(\frac{7}{4}\right)^k \cdot \frac{44}{49} < \left(\frac{7}{4}\right)^k$

$a_k < \left(\frac{7}{4}\right)^k$