# linear recurrence inequality

Given two real analytic functions, $g(x)$ and $f(x)$, on an open interval $I\subset \mathbb{R}$, it is obvious that $g(x) \leq f(x)$ does not imply $g_n \leq f_n$ (here $g_n = [x^n] g(x)$ denotes the $n$-th Taylor coefficient of $g$). However, does the inequality in the coefficients hold if we restrict to the class of univariate holonomic functions? Let me illustrate with a simple example:

Suppose we are given a linear recurrence inequality, $$f_{n+1} \leq \alpha f_n + \beta f_{n-1},\qquad n\geq 1,$$ and real $\alpha, \beta$, and $f_0, f_1$ are given. We approach this with the standard generating function $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}.$$

The answer is no. E.g., let $\alpha = -1,\beta = 0,f_0= 0,f_1= 0,f_2= -2,f_3= 1$. Then $f_{n+1} \leq \alpha f_n + \beta f_{n-1}$ for $n=1,2$, whereas $$f_3 = 1 \not\leq 0= \left(\alpha ^2+\beta \right)f_1 +\alpha \beta f_0=[x^3] \dfrac{f_0 + xf_1 - \alpha x f_0}{1-\alpha x - \beta x^2}.$$
• $f_0=f_1=0$ does imply $f_2\le0$. However, you allowed $\alpha$ (and $\beta$) to be any real numbers, and so, they may be negative. Thus, it is then possible to have $f_3>0$, as we have in the above example -- please recheck it. I think if you additionally require that $\alpha$ and $\beta$ be nonnegative, then the conclusion will be true -- however, that will be a different question. – Iosif Pinelis Apr 25 '16 at 15:35
• Great answer! Now, if I tell you, in my real problem $\alpha$, $\beta$ are indeed known to be non-negative, and also the $f_n$ are norms of matrices, so that $f_n\geq 0$. Perhaps I should pose this as a new question, as you suggest. – bbn Apr 25 '16 at 15:41