$r_n = 2r_{n-1} + 5r_{n-2}$
Where $r_1 = r_2= 2$, Assume $r_n \le ab^n$ (primarily upper bound b as tightly as possible, and secondarily upper bound a as tightly as possible. Use Constructive Mathematical induction to derive an upper bound for $r_n$.
How do I approach this problem. From what I have gathered, the base case is either 1 or 2 I think. What would be the I.H and I.S
On
The natural induction argument goes as follows: $$ r_{n+1} = 2r_{n} + 5r_{n-1} \le 2ab^n + 5ab^{n-1} = ab^{n-1}(2b+5) $$ This argument will work iff $2b+5 \le b^2$, which happens exactly when $b \ge \sqrt{6}+1$ for $b \ge 0$.
You still need the base cases, $r_1 = r_2= 2$, which give $ab \ge 2$, $ab^2 \ge 2$.
Taking $b=\sqrt{6}+1$, we get $a \ge \frac 2b= \frac 25(\sqrt{6}-1)$.
suppose $r_n \le ab^n$
And if $b$ is chosen to most tightly bound $r_n$ then $r_n$ approximately equals $ab^n$
At the limit.
$ab^n = 2ab^{n-1} + 5ab^{n-2}\\ ab^{n-2}(b^2 - 2b-5) = 0$