I have a question that seems simple, but it has caused me some trouble when trying to prove it. Given a recurrence relation with non-negative integer coefficients, $$ G_{n+1} = c_1G_n + c_2G_{n-1} + \cdots + c_sG_{n+1-s} + c_{s+1}G_{n-s} + \cdots + c_LG_{n+1-L}, $$ where $c_1,\cdots,c_s = 0$, $c_s,c_L > 0$ and $L\geq s\geq0$, I want to show that $$ G_n-G_{n-1} > c_L G_{n-L}. $$ Also worth noting that we always have $G_1 = 1$, and the other initial conditions of the sequence are positive and increasing. In fact, in general $G_i = i$ for $1\leq i \leq s+1$, and for $s+2 \leq n \leq L$, $$ G_n = \begin{cases}n & \text{if } c_{s+1} \leq s,\\ c_{s+1}G_{n-s-1}+c_{s+2}G_{n-s-2} + \cdots + c_{n-1}G_1+1 &\text{if } c_{s+1} > s. \end{cases} $$ Any help is appreciated!!
1 Answers
It depends on the coefficients $c_i$. It is well-known that such a recurrence has solutions of the form:
$\begin{align*} G_n &= \sum{1 \le k \le r} \alpha_k p_k(n) \rho_k^n \end{align*}$
where the $\rho_k$ are the $r$ zeros of the polynomial:
$\begin{align*} c_1 \rho^{L - 1} + c_2 \rho^{L - 2} + \dotsb + c_L \end{align*}$
and the polynomials $p_k()$ arise for repeat zeros (a zero of multiplicity $m$ gives a polynomial of degree $m - 1$).
That polynomial can have anything as zeros, positive or negative including pairs of complex conjugate ones. The stretch of 0 coefficients just give a repeat zero of 0, and they one in turn give a pure polynomial part to the solution. The $\alpha_k$ depend on your initial values. The negative and the complex zeros give fluctuating terms, and those may well add up to increasing and decreasing $G_n$.
- 27,812