Why do we set $u_n=r^n$ to solve recurrence relations?

Question

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?

Answer 1

This form of the the solution comes out rather naturally if one works in terms of generating functions. This reduces the linear difference equation to a matter of careful algebra, in rather a similar way as the Laplace transform does for linear differential equations.

The Fibonacci sequence provides a nice example of this. We have $F_{n+2}=F_{n+1}+F_n$ for $n\geq 0$ and $F_0=F_1=1$ as boundary values. We may introduce the generating function / formal power series $\mathcal{F}(x)=\sum_{n=0}^\infty F_n x^n$ where $x$ is a formal variable. Then

\begin{align}\mathcal{F}(x) &=1+x+\sum_{n=0}^\infty F_{n+2} x^{n+2}\\ &=1+x+\sum_{n=0}^\infty F_{n+1} x^{n+2}+\sum_{n=0}^\infty F_{n} x^{n+2}\\ &=1+x+x(\mathcal{F}(x)-1)+x^2 \mathcal{F}(x)\\&=1+(x+x^2)\mathcal{F}(x)\hspace{2.5 cm}\implies \mathcal{F}(x)=\frac{1}{1-x-x^2} \end{align}

One may verify that series expansion of $\mathcal{F}(x)$ produces the Fibonnaci sequence as coefficients. But we can also express this generating function via partial fractions as $$\mathcal{F}(x)=\dfrac{A_+}{1-r_+ x}+\dfrac{A_-}{1-r_- x}$$ where $A_\pm$ are appropriate coefficients and $r_\pm$ the roots of $1-x-x^2=0$ (i.e. the characteristic equation!) Expanding these as geometric series, we find coefficients $F_n = A_+ (r_+)^n+A_- (r_-)^n$. This is precisely the form we had expected.

Answer 2

This comes just from the observations that if $a_n = Ar^n$ then

$$a_{n+i} = r^i a_n$$

thus if we have a recurence relation on the form

$$0 = a_{i} + b a_{i+1} + c a_{i+2} + \ldots + ma_{i+k}$$

then making this guess turns it into an algebraic equation

$$a+br + cr^2 +\ldots + mr^k = 0$$

There is also a close analogy with differential equations here (many recurence relations can be seen as a discretization of a differential equation). If $y(x) = e^{r x}$ then $\frac{d^{n}y}{dx^n} = r^ny$ so if we have a differential equation of the form

$$ 0 =ay + b\frac{dy}{dx} + c \frac{d^2y}{dx^2} + \ldots + m\frac{d^ky}{dx^k}$$

and make the guess $y=e^{rx}$ then it also turns into an algebraic equation

$$a+br + cr^2 +\ldots + mr^k = 0$$

"Why it does indeed give the full solution": The recurence relation above is fully specified when we give the initial conditions $a_1,a_2,\ldots, a_{k}$ (as this allows us to calculate all the other terms). Now if the algebraic equation have $k$ distinct roots $r_k$ (it's a bit more complicated otherwise) then this method gives us that

$$a_n = Br_1^n + Cr_2^n + \ldots + Mr_k^n$$

is a solution. Is it the only solution? Yes we can prove this. Our formula has $k$ constants $B,C,\ldots,M$ which we need to match up to the $k$ initial conditions. This is enough to uniquely fix all the constants. Since our formula for $a_n$ satsify the recurence relation and have the correct initial conditions it follows that it is correct for all $n$.

Answer 3

1. 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.
2. 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.
3. 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
4. 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$.