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
Suppose sn+1 = sn + sn−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.
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. A repeated root still has a mechanism; it asks for a different second quantity.
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.