Define the function Q n n element J by Q 0 2 Q 1 6 Q x 6Q

Define the function Q (n), n element J^+ by Q (0) = 2; Q (1) = 6; Q (x) = 6Q (x - 1) - 5Q (x - 2). Prove by induction: Q (n) = 5^n - 1.

Solution

The recurrence relation is linear homogeneous with constant coefficients so we let

Q(n)=r^n

Substituting gives

r^2=6r-5

r^2-6r+5=0

r^2-5r-r+5=0

r=1,5

So,

Q=A*1^n+B*5^n=A+B*5^n

Q(0)=A+B=2

Q(1)=A+5B=6

Hence, A=B=1

So,

Q(n)=5^n+1

Given formula is wrong