Find exact closed form of recurrence $g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $ n \geq 2$

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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

Answer 4

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$