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.

  • $\begingroup$ The two base cases are given. You just need to prove the induction step. $\endgroup$ – Wuestenfux Mar 18 '19 at 7:26
  • $\begingroup$ Just use what you know about $h_k$ and $h_{k-1}$ (your induction hypothesis). $\endgroup$ – GReyes Mar 18 '19 at 7:27
  • $\begingroup$ is this $$2\cdot5^n$$ or $$2.5^n$$ $\endgroup$ – Dr. Sonnhard Graubner Mar 18 '19 at 7:29
  • $\begingroup$ it's supposed to be $2.5^n$ $\endgroup$ – Code4life Mar 18 '19 at 7:53
  • $\begingroup$ $$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$ $\endgroup$ – 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$$

  • $\begingroup$ 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$ $\endgroup$ – Code4life Mar 18 '19 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.