linear recurrence inequality of positive terms

Question

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}. $$

Answer 1

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}. $$