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
Introduce a weight that we have not chosen yet:
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.
This calculation tells us what to require. The old variable disappears precisely when 1 + c − c² = 0. The weight is derived from the desired operation.
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.
What the change earned
The original operation required a pair of interacting values. The refactored operation is scalar multiplication on each of two quantities. The inverse calculation proves that the change has not lost the original sequence.
This is also what diagonalising the two-state update matrix accomplishes. Starting with the quantity we wanted to construct makes the choice of coordinates explicit. The same calculation explains the matrix method instead of merely invoking it.
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 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.