Why do we set $u_n=r^n$ to solve recurrence relations? This is something I have never found a convincing answer to; maybe I haven't looked in the right places. When solving a linear difference equation we usually put $u_n=r^n$, solve the resulting polynomial, and then use these to form a complete solution. This is how to get $F_n=\frac{1}{\sqrt{5}}(\phi^n-(-\phi)^{-n})$ from $F_{n+1}=F_n+F_{n-1}$ and $F_0=0, F_1=1$ for example.
I can see that this works, but I don't understand where it comes from or why it does indeed give the full solution. I have read things about eigenfunctions and other things but they didn't explain the mechanics behind this very clearly. Could someone help me understand this?

*

*if $u_n=f(n)$ satisfies a linear recurrence relation (without looking at the starting condition(s)) then $u_n=cf(n)$ also satisfies the recurrence relation.

*if $u_n=f_1(n)$ and $u_n=f_2(n)$ both satisfy a linear recurrence relation (again: without the starting conditions(s)) then $u_n=f_1(n)+f_2(n)$ also satisfies the recurrence relation.

*so having $u_n=f_1(n), \ldots, u_n=f_k(n)$ satisfying the recurrence also $u_n=c_1f_1(n)+\cdots+c_kf_k(n)$ satisfies the recurrence relation

*Now substituting $u_n=r^n$ into a recurrence of order $k$ gives a polynomial equation of degree $k$. If this polynomial has $k$ different roots $r_1,\ldots,r_k$ we have $k$ different functions $f_1(n)=r_1^n,\ldots,f_k(n)=r_k^n$ satisfying the recurrence. The linear combination of them has $k$ coefficients $c_1,\ldots,c_k$ to be set, just enough to make the linear combination fulfill the starting condition(s).


So this shows why the Ansatz $u_n=r^n$ works. How this Ansatz was originally guessed? Well, for a recurrence relation of order 1 $u_{n+1}=r u_n$ you naturally get $u_n=u_0 r^n$.
