1
$\begingroup$

This is a follow up on my previous linear recurrence inequality question. I have some matrices which satisfy a linear recurrence formula of the form $$ A_{n+1} = \alpha A_{n} + \beta A_{n-1},\qquad n\geq 1, $$ with $A_0 \in \mathbb{R}^{d\times d}$ given. Assume that $\alpha,\beta \geq 0$. Defining the sequence of norms $\{ f_n = ||A_n||\}_{n=0}^{\infty}$, we come up with a linear recurrence inequality, $$ f_{n+1} \leq \alpha f_n + \beta f_{n-1},\qquad n\geq 1, $$ and real non-negative $\alpha, \beta$, with the property that $f_n\geq 0$ for all $n$. The question is: is it correct to solve this by the standard generating functions method? (if the coefficients are allowed to be negative then this is not true, see the answer to my previous question).

So if we let $F(x) = \sum_{x=0}^\infty f_n x^n$, then (maybe assuming $x\in (0,\mu)\in \mathbb{R}^+$) we obtain $$ F(x) \leq \dfrac{f_0 + xf_1 - \alpha x f_0}{1-\alpha x - \beta x^2}. $$ The question is if we are allowed to compare the Taylor coefficients on the left and on the right hand sides of this inequality, $$ f_n = [x^n] F(x) \overset{?}{\leq} [x^n] \dfrac{f_0 + xf_1 - \alpha x f_0}{1-\alpha x - \beta x^2}. $$

$\endgroup$
1
$\begingroup$

If $\alpha$ and $\beta$ are nonnegative, then the conclusion is indeed true; the condition $f_n\ge0$ is not needed.
First here, note that
$$[x^n] \dfrac{f_0 + xf_1 - \alpha x f_0}{1-\alpha x - \beta x^2}=g_n,$$ where $(g_n)$ solves the linear recurrence $$ g_{n+1} = \alpha g_n + \beta g_{n-1},\qquad n\geq 1, $$ with $g_0=f_0$ and $g_1=f_1$. The conclusion now follows by induction. Indeed, if $f_k\le g_k$ for $k=0,\dots,n$ for some natural $n$, then $$ f_{n+1} \leq \alpha f_n + \beta f_{n-1}\leq \alpha g_n + \beta g_{n-1}=g_{n+1}. $$

$\endgroup$

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.