It is well known how to find a solution for the following linear difference equation


$$h\_{m} = h\_{m-1} + a \cdot h\_{m-2}$$


Finding the roots $r\_1$ and $r\_2$ of $r^2 - r - a$, we have that the solutions are of the type $\lambda r\_1^m + \mu r\_2^m$, and then we can solve for $m = 0$ and $m = 1$ to find $\lambda$ and $\mu$.


What about inequalities? I have a quantity $h\_{m}$ that I wish to bound below, and I derived the following recursive relationship


$$h\_{m} \geq h\_{m-1} + a \cdot h\_{m-2}$$


Knowing that $h\_0 = 0$, $h\_1 = 1$ and that $h\_m \in [0, 1], \forall m$, is it possible for me to find a general lower bound in terms of $m$ and $a$? If not, what additional knowledge would help me?




---


This question is also at: [MSE](https://math.stackexchange.com/questions/2796735/linear-difference-inequality)



Linear difference inequality
You can find the sharpest possible bound for any $m$ and numerical value of $a$ by solving a Linear Program.


Make use of $h\_0 = 0$ and $h\_1 = 1$ in the below.


**Minimize $h\_m$** with respect to $h\_2,..,h\_m$


subject to


$$h\_i \ge 0, i= 2,., m$$
$$h\_i \le 1, i = 2,.., m$$
$$h\_i \ge h\_{i-1}+ ah\_{i-2}, i=2,..,m$$


If you have additional knowledge or constraints, you can add them. If the additional constraints are linear (equality or inequality), it will still be a Linear Program. If any are not linear, it will be some other type of mathematical optimization problem, which you should solve to global optimality.


