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?

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