Explanation of recursive function

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?

-
Are you familiar with linear algebra, especially diagonalizing a matrix? –  Alex Becker Apr 16 '14 at 21:05
You could just prove they are the same by induction. –  Git Gud Apr 16 '14 at 21:20
Cool, so far 5 different ways to solve this (including the induction comment). I wonder how many different ways can be found. –  DanielV Apr 16 '14 at 21:45
@AlexBecker I should be, but I feel like my knowledge about that didn't survive the semester holidays... :/ –  Christian Schnorr Apr 16 '14 at 22:45
The $\sqrt{17}$ comes from $3^2+4 \times 2$, based on the coefficients of the recursion. In the Fibonacci sequence $f(n)=f(n-1)+f(n-2)$ you get $\sqrt{5}$ from $1^2+4 \times 1$ –  Henry Apr 17 '14 at 13:20

\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}$$

-

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

-
Probably the (for me) easiest to understand answer! Thanks! –  Christian Schnorr Apr 16 '14 at 22:43
You are welcome. –  André Nicolas Apr 16 '14 at 22:47
This is brilliant. –  András Hummer Apr 17 '14 at 9:08

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

-

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.

-

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