# How can I prove this recurrence equation using mathematical induction?

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.

• The two base cases are given. You just need to prove the induction step. – Wuestenfux Mar 18 '19 at 7:26
• Just use what you know about $h_k$ and $h_{k-1}$ (your induction hypothesis). – GReyes Mar 18 '19 at 7:27
• is this $$2\cdot5^n$$ or $$2.5^n$$ – Dr. Sonnhard Graubner Mar 18 '19 at 7:29
• it's supposed to be $2.5^n$ – Code4life Mar 18 '19 at 7:53
• $$h_{n+1}=2h_n+h_{n-1}\leq 2\times 2.5^n+2.5^{n-1}=2.5^{n-1}(2\times 2.5+1)=2.5^{n-1}\times 6\leq 2.5^{n+1}$$ since $6\leq 6.25=(2.5)^2$ – learner Mar 18 '19 at 8:01

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$$
• Yeah I got it, what you did was substitute $2.5^{k+1}$ into $h_{n+1}$. Then the trick was to divide both sides by 2.5 to get rid of the $n-1$ exponent. Then you factored out $2.5^k$ and the constant arithmetic ends up being 6. Then you divided by $2.5^k$ again on both sides to get $2.5^2 \geq 6$ – Code4life Mar 18 '19 at 8:06