Explanation of recursive function

Question

Given is a function $f(n)$ with:
$f(0) = 0$
$f(1) = 1$
$f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$

I was wondering if there's also a non-recursive way to describe the same function.

WolframAlpha tells me there is one:
$$g(n) = \frac{(\frac{1}{2}(3 + \sqrt{17}))^n - (\frac{1}{2}(3 - \sqrt{17}))^n}{\sqrt{17}}$$

However, I have absolutely no clue how to determine this function, especially the $\sqrt{17}$ makes no sense to me.

Could anyone maybe explain why $f(n)$ and $g(n)$ are the same?

Answer 1

$$\begin{align} f(n) &= 3\,f(n-1) + 2\,f(n-2) \\ f(n-1) &= 1\,f(n-1) + 0\,f(n-2)\end{align}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n - 1) \\ f(n - 2) \end{bmatrix}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n - 1} \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$$

$$\begin{bmatrix} f(n + 1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

Diagonalize (find eigen values / eigen vectors) and you have your closed form.

$$\begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix} \begin{bmatrix} \frac{3 - \sqrt{17}}{2} & 0 \\ 0 & \frac{3 + \sqrt{17}}{2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix}^{-1} $$

Answer 2

You could prove that the formula is correct, by induction. It comes down to showing that the given expression satisfies the initial conditions and the recurrence.

There is also a general theory of homogeneous linear difference equations with constant coefficients. It says, for second-order difference equations (our case), that if the recurrence is $f(n)=pf(n-1)+qf(n-2)$, to do this.

1) Solve the equation $x^2-px-q=0$.

2) If the roots are distinct, say $\alpha$ and $\beta$, then the solutions of the difference equation are given by $$f(n)=A\alpha^n+B\beta^n.$$ The constants $A$ and $B$ can be determined by using the "initial values" $f(0)$ and $f(1)$.

Answer 3

This is called a linear recurrence. Solving them is fairly straightforward, and is explained here: http://en.wikipedia.org/wiki/Linear_recurrence#Solving.

The key thing to note is that if $f_1$ and $f_2$ are solutions of this recurrence, then $f_1 + f_2$ is as well (except for the initial conditions).

The trick is to assume that there is a solution of the form $f = cr^n$, and see where that leads you.

Let's see how it works out: $f(n) = 3f(n-1) + 2f(n-2)$\

$cr^n = 3cr^{n-1} + 2cr^{n-2}$

Dividing everything by $cr^{n-2}$ and rearranging gives: $r^2 - 3r - 2 = 0$. Factor, to get: $\frac{-1}{4} \left(-2 r+\sqrt{17}+3\right) \left(2 r+\sqrt{17}-3\right) = 0$

I conclude that $r = r_1 = \frac{\sqrt{17}-3}{2}$, or $r = r_2 = \frac{-\sqrt{17}+3}{2}$.

Using the fact that I can add solutions together and still have a solution to the recurrence relation, I'll write: $f(n) = c_1r_1^n + c_2r_2^n$

From here, you can plug in the initial conditions to solve for $c_1$ and $c_2$.

Answer 4

Use generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, write the recursion as: $$ f(n + 2) = 3 f(n + 1) + 2 f(n) $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ \frac{F(z) - f(0) - f(1) z}{z^2} = 3 \frac{F(z) - f(0)}{z} + 2 F(z) $$ With the initial values you get: $$ F(z) = \frac{z}{1 - 3 z - 2 z^2} $$ Split into partial fractions, and read off the coefficients by using geometric series.

Answer 5

There are multiple methods available, see also this wikipedia page.

Generating function
Generally speaking, the method of generating functions is very powerful and allows you to solve many recurrent relations. However, the method is a bit abstract and requires a lot of error-prone calculations, so for a simple (homogenous) recurrent relation you probably want something simpler. See this free ebook for more information (looking at some examples in the first chapter is probably enough to get a feeling for the general technique.

The method of undetermined coefficients
In which we assume a solution of the form $c^n$. This leads to a quadratic equation for which we hopefully can find two different solutions so that we can make a linear combination of the two that satisfies the boundary conditions. If there only one solution (with multiplicity 2) of the quadratic equation, you have to use the fact that the derivative of the quadratic is 0 as well (I don't remember the specifics, but it's not really relevant now, I just want to point out that this method doesn't always work).

The method of eigenvalues
This works as follows: write the recurrence relation in matrix form, and find the eigenvalues and eigenvectors of the matrix. When we've found them, we can hopefully write the initial conditions as a linear combination of eigenvectors. Now we can deduce the solution to the recurrence relatio. Suppose the initial conditions is $x_0 = av_1 + bv_2$ and $\lambda_1, \lambda_2$ are the eigenvalues of $v_1, v_2$. Then the solution to the recurrent relation is $x_n = a\lambda_1^nv_1 + b\lambda_2^nv_2$. With this method, it is also possible to see why Hero's method for approximating squareroots works (and with a little analysis, you can even come up with a better method for calculating squareroots of integers $n$ where $n > 2$).

The method of undetermined coefficients is probably the easiest one to use.