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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented May 26, 2018 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .