Why does the method for solving linear recurrence relation work

Question

Specifically for the homogeneous linear recurrence relation. How does one derive the method for solving such equation,namely by findingthe roots of characteristic polynomial and the solution is of the form $$U\cdot x_1^n+V\cdot x_2^n$$ and why is it for repeating roots the solution become something of the form $$U\cdot x_1^n+V\cdot n\cdot x_1^n$$ I've noticed that this method is very similar to solving higher order homogeneous differential equation

Answer 1

Suppose $x$ and $y$ are the roots of the quadratic $p(z)=z^2-qz+r=0$ where we have $q=x+y$ and $r=xy$.

If we now set $u_n=Ax^n+By^n$ and compute

$$0=Ax^np(x)+By^nP(y)=u_{n+2}-qu_{n+1}+pu_n$$we can see how the recurrence arises from the sum of the roots.

Now if $u_0=V$ and $u_1=W$ we obtain $A+B=V$ and $Ax+By=W$ so that $$A=\frac {Vy-W}{y-x} ; B=\frac {Vx-W}{x-y}$$

Next suppose $y=x+h$ so that $A=\frac {Vx-W}{h}+V; B=-\frac{Vx-W}h$ and $$u_n=Vx^n+\frac {W-Vx}h\left((x+h)^n-x^n\right)$$ and as $h\to 0$ we see how the derivative arises and when roots are equal we get $$u_n=x^n+ n \left( \frac{W-Vx}x \right)x^n$$

This is one way through. Another way is to use generating functions to obtain the solution as the coefficients of the expansion of $u_n=\frac A{z-x}+\frac B{z-y}$ or, for equal roots, of $\frac A{z-x} +\frac B{(z-x)^2}$ - and it is clearer that this method generalises.

Answer 2

Another way to approach this is to vectorize the recursion $x_{n+1}+px_n+qx_{n-1}=0$ as $$ \pmatrix{x_{n+1}\\x_n} = \pmatrix{-p&-q\\1&0} \pmatrix{x_n\\x_{n-1}} = \pmatrix{-p&-q\\1&0}^n \pmatrix{x_1\\x_0} $$ The matrix power can be computed in a systematic way from the Jordan normal form of the matrix, which for different eigenvalues is diagonal and for equal eigenvalues is one Jordan block.