Offset between non-homogeneous and homogeneous recurrence sequences

1. Apr 17, 2012

dodo

I have a question; help is welcome.

Let sn be a linear, non-homogeneous recurrence sequence, and let hn be a corresponding homogeneous sequence (with initial values to be determined).

As it turns out, the offset between the two (sn - hn) is given by the steady state value of sn, if the initial values of hn are offset from those of sn by the same amount. Precisely what is the reason for that?

This steady state value bears no relation to the initial values of the sequence sn; more properly, it should be called the steady state value of the recurrence rule. I believe it is clear that a linear recurrence rule will have exactly one steady state value, neither none nor multiple (as the steady state is given by the root of a first-degree polynomial). And the steady state of hn is, of course, 0 (the root of a first-degree polynomial through the origin -- d'oh!). Therefore, if the desired offset does not depend on the initial values of sn (the offset was hand-set on the initial values, but who says it will stay that way further on in the sequences?), then the difference of the two steady states (thus the steady state of sn, as the one of hn is zero) should do. But why is the part in bold true?

Thanks--

2. Apr 18, 2012

dodo

To start with a simpler question, how would you get the closed form of this sequence? (And why?)$$G_n = G_{n-1} + G_{n-2} + 3$$with initial values$$G_0 = 0, \quad G_1 = 1$$(Not a homework problem; change the sequence to any other that has a constant term, if you wish.)

- - -

P.S. The answer is that you look for the closed form of$$F_n = F_{n-1} + F_{n-2}$$with initial values$$F_0 = 3, \quad F_1 = 4$$and then subtract 3 from that; obtaining, in the end,$$G_n = \frac {(3+\sqrt 5) \phi^n + (3-\sqrt 5) \psi^n} 2 - 3$$with the usual values for$$\phi = \frac {1 + \sqrt 5} 2, \quad \psi = \frac {1 - \sqrt 5} 2$$
but the question is why is the first step valid.

- - -

P.P.S.: Hmm, maybe the proof by induction that you'd use for this example can be extended to the generic case. I'll try and be back.

Last edited: Apr 18, 2012
3. Apr 18, 2012

ramsey2879

I think the answer is to set up the following equivalence

s2 = A(s1) + B(s0) + C = h2 - Offset

= A*h1 + B*h0 - Offset= A*(s1 + Offset) + B*(s0 +Offset) - Offset

As you can see the terms A(s1) and B(s0) on both the right and left hand sides of the equation cancel out.

Last edited: Apr 18, 2012
4. Apr 19, 2012

dodo

Yes, ramsey, I think that is helpful. Not just for the first three terms, but for any three successive terms, if an offset was to have these properties, it would have to comply with an equation where only A,B,C appear. (Assuming A+B is not 1, because then the whole method breaks -- but that's another story.)

It is better to define the offset with the opposite sign (so that sn = hn + Offset, and not - Offset) because then the equation simplifies to Offset = C/(1 - A - B) instead of C/(A + B - 1). The former value can be shown to be the steady state of the sequence rule:

A ( C/(1 - A - B) ) + B ( C/(1 - A - B) ) + C = (AC + BC + C(1 - A - B)) / (1 - A - B) = C/(1 - A - B)

(that is, for this value of "Offset", if sn-2 and sn-1 are both equal to Offset, then sn will be equal to Offset too).