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?

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