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?

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.
