Homogeneous linear recurrence

Trying the solution \(a_n=r^n\) turns the recurrence into an algebraic equation: dividing by \(r^{n-k}\) leaves the characteristic equation \(r^k=c_1r^{k-1}+\cdots+c_k\). For \(a_n=5a_{n-1}-6a_{n-2}\) it gives \(r^2-5r+6=0\), with roots 2 and 3, so \(2^n\) and \(3^n\) are solutions.

Because the equation is linear, every combination of solutions is again a solution. If the roots are distinct, the general solution is \(a_n=\alpha_1r_1^n+\cdots+\alpha_kr_k^n\); a root \(r\) repeated \(m\) times contributes \((\alpha_0+\alpha_1n+\cdots+\alpha_{m-1}n^{m-1})r^n\); and complex roots give oscillating sequences, like those of \(a_n=-a_{n-2}\). The \(k\) coefficients are fixed by the \(k\) initial values by solving a linear system.

With \(a_0=1\) and \(a_1=5\) the recurrence above gives \(a_n=3^{n+1}-2^{n+1}\), so \(a_{10}\) is obtained without computing the nine previous terms. For Fibonacci the roots are \(\tfrac{1\pm\sqrt5}{2}\), which leads to Binet's formula. A common mistake is to forget the double root: \(2^n\) and \(n2^n\) are independent solutions, and using only \(2^n\) cannot meet two initial values.