Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.