<s>[INST] 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.
 [/INST] 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$
</s>