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

 

[ramsey2879]

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

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

 

[blue_raver22]

The offset between non-homogeneous and homogeneous recurrence sequences is an interesting concept and has practical applications in various fields of science and mathematics. The reason for the steady state value of sn being the offset between the two sequences is due to the nature of linear recurrence rules.

Firstly, it is important to understand that a linear recurrence rule will always have a steady state value, which is the root of a first-degree polynomial. This steady state value is independent of the initial values of the sequence sn, as it is solely determined by the recurrence rule itself.

In the case of a non-homogeneous sequence sn and its corresponding homogeneous sequence hn, the initial values of hn are set to be offset by the same amount as the initial values of sn. This means that the two sequences will have the same behavior at the beginning, but as the sequences progress, the non-homogeneous sequence will deviate from the homogeneous one.

However, the steady state value of hn will always be 0, as it is the root of a first-degree polynomial through the origin. This means that the difference between the steady state values of sn and hn will be equal to the steady state value of sn. In other words, the offset between the two sequences is determined by the steady state value of sn, which is independent of the initial values of the sequence.

In conclusion, the reason for the steady state value of sn being the offset between non-homogeneous and homogeneous recurrence sequences is due to the nature of linear recurrence rules and the fact that the steady state value is independent of the initial values of the sequence. I hope this helps to clarify the concept.