Step by Step Second Order recurrence relations

680 Views Asked by At

Hi I have the following linear relation

$S(n)= 2S (n-1)+3S(n-2)$

$S(1) = 3$
$S(2) = 1$
$S(3) = ?$

1- I know I need to find $c_1$ & $c_2$ Which are $c_1 = 2 $, $c_2 = 3$

2-I Know the roots are $r_1 = 3$ and $r_2 = -1$

3 I know that the formula for the next step is $S(1) = p+ q$ and for $S(2)$, $pr_1 + qr_2$

How do I find the value $p$ & $q$ to get the right equation

1

There are 1 best solutions below

0
On BEST ANSWER

You are trying to solve the linear recurrence $S(n)=2S(n-1)+3S(n)$.

The first step is solving characteristic equation $x^2-2x-3=0$; and you found the roots $r_1=3$, $r_2=-1$.

You wrote, that you know that general solution has the form $S(n)=pr_1^n+qr_2^n$, but you have to find $p$ and $q$.

Since you know that $S(1)=p+q$, $S(2)=pr_1+qr_2$, you can simply plug the known values into these equations and you get $$ \begin{align} p+q&=3\\ 3p-q&=1 \end{align} $$

This is a very simple system of linear equations with unknowns $p$, $q$. You can solve this system to find out that $p=1$ and $q=2$.