So for a recurrent equation where $h_n = 2h_{n-1} + h_{n-2}$ with the initial conditions of $h_0 = h_1 = 1$ where $n \geq 2$, prove that $h_n \leq 2.5^n$
I'm suposed to prove this by using mathematical induction and I began by doing the base case where $n = 2$:
$2.5^2 \geq 2h_{2-1} + h_{2-2}$
$2.5^2 \geq 2(1) + 1$
$2.5^2 \geq 3$
which is true for the base case. However, I'm stuck on the inductive hypothesis where I need to prove true for $k+1$ where I have no idea where to begin. I simply made the equation and I'm not sure where to go from there:
$2.5^{k+1} \geq 2h_{k} + h_{k-1}$
There are subscripts and superscripts on both sides of the equation and mathematical induction problems do not have those scenarios.
You have to prove that $$h_{n+1}\le 2.5^n$$ now we have given $$h_{n+1}=2h_n+h_{n-1}$$ now using that $$h_n\le 2.5^n$$ and $$h_{n-1}\le 2.5^{n-1}$$ so we get $$h_{n+1}\le 2\cdot 2.5^n+2.5^{n-1}$$ Can you finish? This is $$2.5^{n-1}(5+1)=6\cdot 2.5^{n-1}\le 2.5^{n+1}$$ since $$6\le 2.5^2$$