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.
Deriving formulas for recursive functions
-
4That particular recurrence relation is ho$m$ogeneous linear with constant coefficients. Wikipedia is a pretty good reference for getting started, and they have $m$any further references at the bottom of the page: http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients – 2011-02-08
2 Answers
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)$.