2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ is that a formula you used for the general recurrence relation, as our lecture did not include anything about general formulas in solving recurrence. $\endgroup$
    – Benjamin
    Nov 16 '14 at 7:35
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.