# What is generally the strategy for converting recurrence to closed form?

Consider the Fibonacci sequence (as an example) \begin{align*} f(n) &= f(n-1) + f(n-2) \\ f(0) &= 0\\ f(1) &= 1 \end{align*} How do you convert this to the closed form expression we all know? Does the strategy change for more advanced linear recurrences?

-

A good start:

When given the general definition of a recurrence relation with its initial value(s), a good general approach is to first start by writing out a series of terms: here write out the $f(i)$s without necessarily evaluating them, and see what sort of pattern you get.

Also, explore some sequences, like the fibonacci sequence, whose closed form is known, try the above, while also trying to work "backwards" from the closed form, to gain some insight into why the two forms express the same relation.

Since you seem to be interested in knowing how to solve recurrence relations in general, you might be interested in exploring the process of generating closed forms of recurrences. See, for example, Herbert Wilf's Generatingfunctionology. The book is available to download, free of charge, from the author's webpage.

Why should one care about the generating function for a sequence? There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the nth coefficient — which can be pretty useful! For example, a closed form for the coefficient of $x^n$ in the power series for $x/(1−x−x^2)$ would be an explicit formula for the $n$th Fibonacci number.

See this generating function tutorial on the strategies for a step-by-step approach to finding the generating functions and closed forms of a sequences, using the the Fibonacci sequence as an example, but generalizing from that.

-
A quick question: If the characteristic polynomial has both real and imaginary roots, do you only pay attention to the real roots? –  KaliMa Dec 10 '12 at 18:24

Consider the recurrence given by $f(n)=Af(n-1)+Bf(n-2)$ and $f(0)=C,f(1)=D$. Then consider the roots of the auxilary equation $x^2-Ax-B=0$, say roots are $\alpha$ and $\beta$. Then $f(n)$ is given by $f(n)=C_1\alpha^n+C_2\beta^n$ and the constants $\alpha,\beta$ are determined from initial conditions.

-
So for example what about f(n) = Af(n-1) + Bf(n-2) + Cf(n-3)? How does the auxiliary equation change? x^3 - Ax^2 - Bx - C = 0? Is this the same as f(n) = C1*alpha^n + C2*beta^n + C3*gamma^n? –  KaliMa Dec 10 '12 at 15:06
@KaliMa: Yes, you are correct. Look at the wikipedia link: en.wikipedia.org/wiki/Recurrence_relation –  pritam Dec 10 '12 at 15:12
Will there always be as many roots as there are degrees in the auxilary polynomial? How do I know which roots apply to which coefficient? –  KaliMa Dec 10 '12 at 15:24
KaliMa - see the tutorial link in my answer; it shows the step by step process of finding and solving the auxiliary polynomial, which roots are which coefficients, etc. –  amWhy Dec 10 '12 at 15:28
@amWhy I am trying to extrapolate it to higher-degree recurrences and finding it a little tough to follow. I can get the characteristic polynomial and the roots down fine, but from there I am totally stuck –  KaliMa Dec 10 '12 at 15:36

You can look at the general way to solve linear recurrence relations I wrote here. In this case, the characteristic polynomial is $t^2-t-1$. The roots are $t_{1,2}=\frac{1\pm\sqrt{5}}{2}$. So $f(n)=\alpha t_1^n+\beta t_2^n$. Find the coefficients from the initial values.

-
Do initial values start at f(0) or f(1)? –  KaliMa Dec 10 '12 at 15:28
Both. You will get a system of two equations with two variables: $\alpha,\beta$ –  Dennis Gulko Dec 11 '12 at 0:00

The basic observation for linear, autonomous recurrences, that is of the form \begin{align*} a_{n+k} &= \sum_{i=0}^{k-1} b_i a_{n+i} \\ \end{align*} and given $a_0, \ldots, a_{k-1}$ is that we can rewrite it by introducing $$A_n := \begin{pmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{n+k-1} \end{pmatrix}$$ as $$A_{n+1} = \begin{pmatrix} a_{n+1} \\ a_{n+2} \\ \vdots \\ a_{n+k} \end{pmatrix} = \underbrace{\begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 &0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b_0 & b_1 & b_2 &\cdots & b_{k-1}\end{pmatrix}}_{M:=} \cdot \begin{pmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{n+k-1} \end{pmatrix} = M\cdot A_n$$ Which has the solution $$A_n = M^n \cdot A_0 = M^n \cdot\begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{k-1} \end{pmatrix}$$ So to solve the recursion, we must compute matrix powers. To do this, we write $M$ in Jordan normal form $M = T(\Lambda + N)T^{-1}$, with $\Lambda$ diagonal, $N$ nilpotent with only non-zero entries in its subdiogonal are some ones, $\Lambda N = N\Lambda$. Then $M^n = T(\Lambda + N)^n T^{-1}$ and the powers of $(\Lambda + N)$ can be easily computed.

-
I really don't work that well with abstractions like these even though I trust it's correct; it's just a bit over my head. Can you provide a hard example to illustrate? –  KaliMa Dec 10 '12 at 15:08