# Difference of Consecutive Terms in a Recurrence Sequence

Mathematics Asked by ThomasMart on October 10, 2020

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 $$Lgeq sgeq0$$, 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 $$1leq 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!!

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

Answered by vonbrand on October 10, 2020