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!!

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP