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