Answer to Question #273335 in Discrete Mathematics for nur

Question

Suppose a recurrence relation

an=2an−1−an−2

where a1=7 and a2=10

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.

  Determine p and q

Answer 1

Let us solve the characteristic equation of the recurrence relation $a_n=2a_{n−1}−a_{n−2},$ which is equivalent to $a_n-2a_{n−1}+a_{n−2}=0.$ It follows that the characteristic equation $x^2-2x+1=0$ is equivalent to $(x-1)^2=0,$ and hence has the roots $x_1=x_2=1.$ It follows that the solution of the recurrence equation is $a_n=p\cdot 1^n+q\cdot n1^n=p+q\cdot n.$ Since $a_1=7$ and $a_2=10,$ we conclude that $7=a_1=p+q$ and $10=a_2=p+2q.$ Therefore, $q=3$ and $p=4.$

Answer: $p=4,\ q=3.$