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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

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