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?

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.
