In How Many Transformations, Daniel came to the realization that linear recurrence of the form
could easily be solved by setting up the matrix interpretation, and then diagonalize the matrix (assuming that's possible) which would allow us quick exponentiation, and hence obtain the Nth term directly.
We've seen this in the context of the Fast Fibonacci Transform. Specifically, set and , and you get the system of equations
Using this, show the following:
1. Performing the eigenvalue decomposition, prove Binet's formula.
2. Using only matrix properties, conclude that
3. Find a similar formula for .
4. Express in terms of .