To my taste this is not very illuminating, it feels like the answer is produced via a magic trick.<p>My personal preference for understanding linear recurrence relations (and understanding where/why sqrt(5) shows up for the Fibonacci sequence) is via eigenvalues and eigenvectors of a corresponding linear transformation. For example:<p><pre><code> [F_n ] = [1 1] [F_n-1]
[F_n-1] [1 0] [F_n-2]
</code></pre>
and therefore<p><pre><code> [F_n ] = [1 1]^n-2 [F_2] = [1 1]^n-2 [1]
[F_n-1] [1 0] [F_1] [1 0] [1]
</code></pre>
and therefore the nth Fibonacci number can be computed by computing the (n-2)th power of the matrix [[1, 1], [1, 0]], and then multiplying that matrix by the column vector [1, 1] (or any other desired first terms of the sequence). The matrix power can be computed by diagonalizing, and that's where the powers of the golden ratio will come up (as eigenvalues of that matrix).<p>This is completely equivalent to the method in TFA, but to my mind is better motivated.
Unfortunately the presented method only works for the most simple linear recurrence relations.<p>Tangentially: look up the master theorem if you're interested in at least estimating growth rates for recurrence relations that crop up in computer science.
A powerful method in math is to assume the thing you're looking for is continuous, in which case you can write it F(n) = a0 + a1 n + a2 n^2 + ... .<p>You can solve Fibonacci by writing it as<p>a0 + a1 n + a2 n^2 + ...<p>= a0 + a1 (n-1) + a2 (n-1)^2 + ...<p>+ a0 + a1 (n-2) + a2 (n-2)^2 + ...<p>Expand terms, then match the n, n^2, n^3 etc terms and solve for a0, a1, a2, etc. This works in solving differential equations too - it's called "Method of Frobenius" (easier in diffeq because you don't have to do annoying binomial coefficient math).
Siebert [1] is great for this stuff (z-transform). The Fibonacci sequence appears in problem 7.2.<p>[1] Siebert, William McC.. Circuits, Signals, and Systems., McGraw-Hill, 1986.