# 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?

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.

• ok, and how would you get the idea of generating functions and using them here? :-) historically generating functions came much later than the formula of Binet and the corresponding Ansatz ... – coproc Oct 3 '14 at 8:45
• @coproc: Do you have a source for that claim? Wikipedia gives de Moivre credit for introducing generating functions in 1730, and Mathworld indicates that Binet's formula was known by Euler/de Moivre/Bernoulli in about the same time frame. So the former hardly seems to come 'much later' than the latter. – Semiclassical Oct 3 '14 at 12:42
• Ok, so I have to withdraw my remark about history - I should have looked up the facts before posting my guess. Thanks for pointing out. – coproc Oct 4 '14 at 11:19

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$.

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$.