Offset between non-homogeneous and homogeneous recurrence sequences

dodo

I have a question; help is welcome.

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

As it turns out, the offset between the two (s_n - h_n) is given by the steady state value of s_n, if the initial values of h_n are offset from those of s_n 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 s_n; 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 h_n 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 s_n (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 s_n, as the one of h_n is zero) should do. But why is the part in bold true?

Thanks--

dodo

To start with a simpler question, how would you get the closed form of this sequence? (And why?)[tex]
G_n = G_{n-1} + G_{n-2} + 3
[/tex]with initial values[tex]
G_0 = 0, \quad G_1 = 1
[/tex](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[tex]
F_n = F_{n-1} + F_{n-2}
[/tex]with initial values[tex]
F_0 = 3, \quad F_1 = 4
[/tex]and then subtract 3 from that; obtaining, in the end,[tex]
G_n = \frac {(3+\sqrt 5) \phi^n + (3-\sqrt 5) \psi^n} 2 - 3
[/tex]with the usual values for[tex]
\phi = \frac {1 + \sqrt 5} 2, \quad \psi = \frac {1 - \sqrt 5} 2
[/tex]
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.

ramsey2879

I think the answer is to set up the following equivalence

s₂ = A(s₁) + B(s₀) + C = h₂ - Offset

= A*h₁ + B*h₀ - Offset= A*(s₁ + Offset) + B*(s₀ +Offset) - Offset

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

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 s_n = h_n + 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 s_n-2 and s_n-1 are both equal to Offset, then s_n will be equal to Offset too).