3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Sorry about that, added the reference in the question. $\endgroup$
    – John
    May 26, 2018 at 13:41
  • $\begingroup$ You mean that $a<0$ here? (otherwise it is a bit hard to keep the sequence in $[0,1]$). $\endgroup$
    – fedja
    May 26, 2018 at 15:06

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ For many values of $a$ and $m$, this problem with be either infeasible (i.e.,, no h exists which satisfies the constraints) or trivial. So this mainly serves as a template for how to address some modified problem which is more interesting. $\endgroup$
    – Mark L. Stone
    May 26, 2018 at 13:22
  • 1
    $\begingroup$ Thank you for your reply. I am interested in analytical solutions. I know that there are method for solving differential inequalities and as differential equations and linear difference inequalities are not far from each other, I was more interested in a general method to solve such problems. $\endgroup$
    – John
    May 26, 2018 at 13:39
  • $\begingroup$ $h_m$ are bounded from below by the solutions of the linear recurrence with identities as long as the latter stay positive (which is up to $\infty$ for $a\ge-\frac 14$). Beyond that point you only have the trivial bound $h_k\ge 0$. (Just think of it a tiny bit: every time you increase $h_k$ by $\delta$ from what identity would give you, you just start a new identity recursion with $0,\delta$ for the initial data, so as long as it produces positive terms, you have the bound) $\endgroup$
    – fedja
    May 26, 2018 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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