I have seen a few derivations of Binet's formula for the nth Fibonacci number, most of them using linear combinations of the solutions to a characteristic polynomial, like so:
$F_0=0, F_1=1$
$F_n=F_{n-1}+F_{n-2}$
let $x^n=x^{n-1}+x^{n-2}$
$x^2=x+1$
$x=\frac{1\pm\sqrt{5}}{2}$
(I will call the two solutions of x $\phi$ and $\psi$)
Which is all fine. But why can you then say:
$F_n=c_1\phi^n+c_2\psi^n$
Why is the nth Fibonacci number a linear combination of powers of the solutions to the characteristic polynomial $x^n=x^{n-1}+x^{n-2}$? I see some connection, namely as n grows, $\frac{F_n}{F_{n-1}}$ approaches a constant, so $F_n=ax^n$ is a reasonable guess at a solution. But especially for the early numbers, this is not exactly true.
What I'd like is a proof that the nth Fibonacci can be represented exactly as a linear combination of powers of the solutions to the characteristic polynomial.
Since the Fibonacci numbers are defined by a simple recurrence, if you want to show that some expression is equal to the Fibonacci numbers you just need to check that the expression satisfies the same recurrence. In this case, this amounts to checking that $$ c_1\phi^0+c_2\psi^0=0,\qquad c_1\phi^1+c_2\psi^1=1, $$ and that $$ c_1\phi^{n+2}+c_2\psi^{n+2}=c_1\phi^{n+1}+c_2\psi^{n+1}+c_1\phi^{n}+c_2\psi^{n}. $$ The last equation follows because $$ \phi^{n+2}=\phi^{n+1}+\phi^n\text{ and }\psi^{n+2}=\psi^{n+1}+\psi^n, $$ where each of these equations hold since they are equivalent to $\phi^2=\phi+1$ and $\psi^2=\psi+1$, that is $\phi$ and $\psi$ are solutions of the characteristic equation $x^2=x+1$.