RefacteA recurrence can be easy to iterate and still conceal the quantities that evolve independently. We will find one of those quantities by asking what its update would have to look like.
The coupled update
Work with real sequences satisfying sn+1 = sn + sn−1 for n ≥ 1. To obtain the next value, we keep two previous values. With s₀ = 0 and s₁ = 1, this gives 0, 1, 1, 2, 3, 5, 8, ….
An ordinary difference gives sn+1 − sn = sn−1. That identity exposes the update, but the old sequence remains on the right. Can a modified difference update using only itself?
Design a quantity
We already store two values, so first try a linear combination of them. A multiple of sn−1 alone would update to a multiple of the independently variable sn. For a candidate involving sn, rescaling does not affect whether it updates by scalar multiplication. Normalize that coefficient to one, leaving one unknown weight:
un = sn − c sn−1.
Substitute the recurrence and then replace sn by un + c sn−1:
un+1 = (1 − c)sn + sn−1
= (1 − c)un + (1 + c − c²)sn−1.
We want the rule to work for arbitrary initial values, so the remaining coefficient of sn−1 must vanish. This requires 1 + c − c² = 0. The decision to try a linear combination came first; this equation determines which weights make it work.
A working example
Choose what moves.
Start with sn+1 = sn + sn−1. Try un = sn − c sn−1.
At c = 1, the extra input remains. The ordinary difference has not separated the recurrence.
| n | sₙ | uₙ | (1 − c)ⁿ⁻¹u₁ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 |
| 3 | 2 | 1 | 0 |
Two independent motions
The two possible weights are φ = (1 + √5)/2 and ψ = (1 − √5)/2. They satisfy φ + ψ = 1 and φψ = −1.
Use both weights:
un = sn − φsn−1, un+1 = ψun,
vn = sn − ψsn−1, vn+1 = φvn.
The new quantities each follow a one-step multiplication rule. We can recover the old value because φ − ψ = √5 ≠ 0:
sn = (φvn − ψun)/(φ − ψ).
With the initial values above, u₁ = v₁ = 1. Repeated multiplication and reconstruction therefore give
sn = (φⁿ − ψⁿ)/√5.
The closed formula arrives after we have explained the independent motions. For arbitrary initial values, only the starting values of u and v change.
Recover the two stored values
The difference of the two new quantities recovers the previous value:
sn−1 = (vn − un)/(φ − ψ).
Together with the formula for sn, this gives an inverse change of coordinates on the two stored values. In matrix language, these are coordinates that diagonalise the update. Each coordinate was found by requiring its dependence on the other one to disappear.
What the two motions predict
For the Fibonacci initial values, the φ-motion grows while the ψ-motion decays and alternates in sign. The formula therefore gives an exact error estimate for keeping only the growing term:
|sn − φn/√5| = |ψ|n/√5 < 1/2 (n ≥ 0).
Since sn is an integer, it is the nearest integer to φn/√5. A formula for the dominant motion has become an exact recovery rule because the discarded motion has a bound.
The same update can behave quite differently for other initial data. If s₀ = 1 and s₁ = ψ, then v₁ = 0: the growing motion is absent, and sn = ψn tends to zero. The two multipliers describe the available motions; the new coordinates of the initial data tell us which ones actually occur.
When separation needs more
For sn+1 = A sn + B sn−1, the same experiment gives
un+1 = (A − c)un + (Ac − c² + B)sn−1.
Thus the weight condition is c² − Ac − B = 0. Distinct roots let us recover two independent quantities. A repeated root does not give two independent coordinates; the reconstruction step reveals exactly where this version of the method stops. Over the real numbers the roots may also require complex coordinates.
For example, sn+1 = 2sn − sn−1 has only the weight c = 1. The first difference is constant, so sn = s₀ + n(s₁ − s₀): the sequence is affine in n, including the constant case.
We can also see this loss of independent coordinates as a limit. For a real parameter δ ≠ 0, the recurrence with A = 2, B = δ² − 1 has multipliers 1 ± δ. With s₀ = 0 and s₁ = 1,
sn = ((1+δ)n − (1−δ)n)/(2δ).
For each fixed n, expanding the numerator shows that this tends to n as δ → 0. The sequence has a regular limit even though the inverse coordinate change divides by a vanishing separation. Near a repeated root, errors in the separated coordinates can be amplified by that division. Exact decoupling and accurate numerical reconstruction are separate questions.
Further refactors
A subgroup becomes a machine makes a different kind of change: expressions become paths and a local folding rule produces a finite test.
The archived Fourier study develops quantities that transform simply under permutations, then uses their products to recover polynomial roots. How far can a change of coordinates go? explores a correction that succeeds once and then meets a provable obstruction.
Sources and another route
This is the standard diagonalization method for a second-order recurrence, derived here by finding the linear quantities first. Gilbert Strang’s lecture on diagonalization and powers of a matrix develops the matrix formulation. Herbert S. Wilf’s generatingfunctionology, second edition (1994), §1.3, reaches the Fibonacci formula by a generating function instead. Comparing the routes shows the same two multipliers as eigenvalues in one description and reciprocals of poles in the other.