Find exact closed form of recurrence $g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $ n \geq 2$ $g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$  for $n \geq 2$
Our lecture notes suggest us to work backwards until you get the first term, i.e. $g(1)$
I am not quite sure how that works as the example on my notes is quite confusing.
 A: Set $x^2-x-2=0$. solve it we have $x_1=2,x=1$. Then $g(n)=a2^n+b(-1)^n$.
Plug $g(0)=0,g(1)=3$, we have $a=1,b=-1$. 
So $g(n)=2^n-(-1)^n$.

The same method is used to solve the general recurrence relation
$$a_n = pa_{n−1} + qa_{n−2}$$ 
We first write down the characteristic equation
$$r^2 =pr+q$$
If this quadratic equation has two distinct real solutions $r = r_1$ and $r = r_2$ then the
general solution is where $c$ and $d$ are constants.
$$a_n = c r_1^n + d r_ 2^n$$
If the characteristic equation has a repeated solution $r = r_1$ then $a_n = nr_1^n$ is a solution of the recurrence relation . The general solution is
$$a_n = c r_1^n + d nr_1^n$$

If you didn't know this general formula, you can solve it as follows:
By assumption, $g(n) = g(n − 1) + 2g(n − 2)$
This implies $g(n) - 2g(n − 1)=-g(n − 1) + 2g(n − 2)=-\bigg(g(n − 1) - 2g(n − 2)\bigg)$
Let $f(n)=g(n)-2g(n-1)$, then $f(n)=-f(n-1),f(1)=3$
Hence you get a formula for $f(n)=3(-1)^{n-1}$. Then solve for $g(n)$.
A: $x^2 - x - 2 = 0 \Rightarrow (x-2)(x+1) = 0 \Rightarrow x = -1, 2 \Rightarrow g_n = A\cdot (-1)^n + B\cdot 2^n$.
$g_0 = 0, g_1 = 3 \Rightarrow 0 = A+B, 3 = -A+2B \Rightarrow A = -1, B = 1 \Rightarrow g_n = (-1)^{n+1} + 2^n$
A: This is a linear recurrence in the form $$g_n=g_{n-1}+2g_{n-2}$$
$$0=g_n-g_{n-1}-g_{n-2}.$$
This has characteristic polynomial $x^2-x-2$. Its roots are 2 and -1. Therefore the explicit formula is in the form $c_1(2)^n+c_2(-1)^n. $Plugging in n=0 and 1 using the given values gives a system of equations, which can be solved for $c_1$ and $c_2$. 
$$c_1+c_2=0$$
$$2c_1-c_2=3$$
$$c_1=1,c_2=-1$$
Therefore the equation is $g(n)=2^n-(-1)^n$
A: Hint:
One way to look at the problem is to write the recurrence relation $g_n=ag_{n-1}+bg_{n-2}$ ($b\neq0$)as \begin{equation} 
\begin{bmatrix}a&&b\\
1&&0 \end{bmatrix}\begin{bmatrix}g_{n-1}\\g_{n-2} \end{bmatrix}=\begin{bmatrix}g_{n}\\g_{n-1} \end{bmatrix}
\end{equation}
This gives
 \begin{equation} 
\begin{bmatrix}a&&b\\
1&&0 \end{bmatrix}^{n-2}\begin{bmatrix}g_{2}\\g_{1} \end{bmatrix}=\begin{bmatrix}g_{n}\\g_{n-1} \end{bmatrix}
\end{equation}
The matrix can be diagonalized with the eigenvectors as the basis. The eigenvalues are the roots of the characteristic equation $ x^2 -ax -b =0 $. 
 \begin{equation} 
\begin{bmatrix}r_1&&0\\
0&&r_2 \end{bmatrix}^{n-2}\begin{bmatrix}k_{2}\\k_{1} \end{bmatrix}=\begin{bmatrix}k_{n}\\k_{n-1} \end{bmatrix}
\end{equation} where k is the vector represented in the eigenvector basis.
From this it can be seen that the solutions are 
$g_n = A(r_1)^n +B(r_2)^n$
