# Deriving formulas for recursive functions

If I had a recursive function (f(n) = f(n-1) + 2*f(n-2) for example), how would I derive a formula to solve this? For example, with the Fibonacci sequence, Binet's Formula can be used to find the nth term.

-
That particular recurrence relation is homogeneous linear with constant coefficients. Wikipedia is a pretty good reference for getting started, and they have many further references at the bottom of the page: en.wikipedia.org/wiki/… –  Jonas Meyer Feb 8 '11 at 4:16

If the recurrence relation is linear, homogeneous and has constant coefficients, here is the way to solve it. First obtain the characteristic equation. To do this, assume $f(n) = m^n$. Plug it in to get a quadratic in $m$. Solve for $m$. Get the two roots say $m_1$ and $m_2$. Now the general solution is given by the linear combination namely $f(n) = a_1 m_1^n + a_2 m_2^n$. Solve for $a_1$ and $a_2$ using the initial conditions.

For your recurrence, the corresponding equation becomes, $m^2-m-2 = 0 \Rightarrow (m-2)(m+1) = 0$. So $f(n) = a 2^n + b (-1)^n$. You need to specify two initial conditions to get $a$ and $b$.

This methodology is analogous to plugging in $y=e^{mx}$ when you want to solve a linear, homogeneous ODE with constant coefficients. Here you have a difference equation instead of a differential equation.

-

Formal power series can be also be used to solve recurrence relations.

Let $a_n=f(n)$ and

$$\begin{eqnarray} S=\sum a_nx^n&=&a_0+a_1x+\sum_2 a_{n-1}x^n+2\sum_2 a_{n-2}x^n\\ &=&a_0+a_1x+\sum_1 a_n x^{n+1}+2\sum_0 a_n x^{n+2}\\ &=&a_0+a_1x+x(S-a_0)+2x^2S \end{eqnarray}$$

For the example, suppose that $a_0=0, \ a_1=1$. Then

$$\begin{eqnarray} S&=&\frac{-x}{2x^2+x-1}\\ &=&\frac{1}{3}\left(\frac{1}{x+1}-\frac{1}{2x-1}\right)\\ &=&\frac{1}{3}\sum_0 (-(-1)^n+2^n)x^n \end{eqnarray}$$

Thus $a_n=\frac{1}{3}\left(-(-1)^n+2^{n}\right)$.

-