Answer to Question #275326 in Discrete Mathematics for feey

Question

Suppose a recurrence relation

an=an−1+20an−2

where a1=9 and a2=189

can be represented in explicit formula, either as:

Formula 1:

an=pxn+qnxn

                      or  

Formula 2:

an=pxn+qyn

 

where 

x

and

y

are roots of the characteristic equation.

**If the explicit formula is in the form of Formula 2, consider p > q.

 

Determine p and q

Answer:

Answer 1

Let us solve the characteristic equation of the recurrence relation $a_n=a_{n−1}−20a_{n−2},$ which is equivalent to $a_n-a_{n−1}-20a_{n−2}=0.$ 

It follows that the characteristic equation $x^2-x-20=0$ is equivalent to $(x+4)(x-5)=0,$ and hence has the roots $x_1=-4, x_2=5.$ 

It follows that the solution of the recurrence equation is 

$$a_n=p\cdot (-4)^n+q\cdot (5)^n.$$

 Since $a_1=9$ and $a_2=189,$ we conclude that

$$9=a_1=-4p+5q$$ $$189=a_2=16p+25q$$

$$9=-4p+5q$$ $$36+189=-16p+16p+20q+25q$$

$$9=-4p+5q$$ $$225=45q$$

Therefore, $q=5$ and $p=4.$

$$a_n=4(-4)^n+5(5)^n.$$