It&#x27;s not miraculous at all, and doesn&#x27;t need to involve generating functions :-)<p>Consider all sequences f(n) that fit the constraint f(n) + f(n+1) = f(n+2), with arbitrary initial values. Such sequences form a vector space, because adding them together or multiplying by a constant doesn&#x27;t break the constraint. That vector space is two-dimensional, because the two initial values determine the rest of the sequence. Now we just need to find two different sequences that form a basis of that space. All other sequences can be expressed as linear combinations of these two.<p>How do we find the two basis sequences? Let&#x27;s make a lucky guess that they are geometric progressions with some constant c. Then we have c^n + c^(n+1) = c^(n+2), or equivalently 1 + c = c^2. That equation has two solutions, phi (the golden ratio, about 1.618) and psi = -1&#x2F;phi.<p>Going back to the original problem, we need to express the usual Fibonacci sequence (which starts with 1,1) as a linear combination of the sequences phi^n and psi^n. We just need to match the two initial values by picking the right coefficients, which turn out to be 1&#x2F;sqrt(5) and -1&#x2F;sqrt(5), giving you the desired closed form formula.<p>The above approach generalizes to any recurrence of the form a * f(n) + b * f(n+1) + c * f(n+2) + ... = f(n+k). All such sequences will form a k-dimensional vector space, and you can find k different geometric progressions by solving a polynomial equation of degree k which has k roots. All other solutions will be linear combinations of these geometric progressions. (There will be complications if some roots coincide, but it can be worked out.)<p>To me the whole chain of reasoning feels very natural and almost inevitable. If I didn&#x27;t know anything about Fibonacci numbers but had a good grasp of popular math, that&#x27;s how I would approach the problem right away. Does that make sense?