Recurrence relation &

generating functions 3.4

 General first-degree linear
recurrence relation with
constant coefficients
The general first-degree linear
recurrence relation with constant
coefficients has the form
qn=cqn-1 + f(n).
If f(n)=0, the relation is called
homogeneous. Otherwise, it is called
non homogeneous.
Corr : If qn = cqn -1+f(n) for
n>0 through method of forward
substitution.
n
q n  c q 0   c f(r)
n n r

r 1

Solved in book ?
Solve the recurrence relation
qr-3qr-1=r, r≥1, q0=1, through method
of generating functions .


q x
0
r
r

Let A(x)=

be the generating function for

q0, q1,…, qn,……………….
 q r -3q r-1  r, r  1
  

1
q r x -3 q r-1 x   rx ,
r

1
r

1
r

 
 (A(x)-q 0 )  3 q r x r 1   rx r ,
0 0


 (A(x)-q 0 )  3x  q r x  x(1  x)
r 2

0
2
 (A(x)-1)  3xA(x)  x(1  x)
 2
 (A(x)-1)  3xA(x)  x(1  x)
2
 A( x)(1  3x)  1  x(1  x)
1 x
 A( x)  
1  3x (1  3x)(1  x) 2

x L C M
  
(1  3x)(1  x) 2
(1  3x) (1  x) (1  x) 2
 x  L(1  x)  C (1  3x)(1  x)  M (1  3x)
2

x  1  1  2M  M  1/ 2
x  1/ 3  1/ 3  (4 / 9) L  L  3 / 4
x  0  0  L  C  M  C  (3 / 4  1/ 2)
 -1/4
x 3 1 1
  
(1  3x)(1  x) 2
4(1  3x) 4(1  x) 2(1  x) 2
 1 x
A( x)  
1  3x (1  3x)(1  x) 2

1 3 1 1
   
1  3x 4(1  3x) 4(1  x) 2(1  x) 2

7 1 1
  
4(1  3x) 4(1  x) 2(1  x) 2

  
7 r r 1 r 1
  (3) x   x   (r  1) x r

r 0 4 r 0 4 r 0 2
 
 7  r 1 1  r
A(x)      3   (r  1) x
0  4  4 2 

  qr x r

 7  r 1 1 
q r     3   (r  1) 
 4  4 2 
The second-degree linear
homogeneous recurrence
relation with constant
coefficients , general form is ,
r0qn+r1qn-1+r2qn-2=0, n2.
r2  0 r0  0
where q0 & q1 are known
General expression of a
linear recurrence relation of
degree m would involve m
unknown constants, they
can be determined to find
solution if m initial
conditions are given
Thm : Generating function A(x) for solution
of degree two linear homogenous recurrence
relation with constant coefficients
q n  r1q n-1  r2 q n-2  0 , n  2
q 0  (q1  r1q 0 ) x
is A(x) 
1  r1x  r2 x 2
 qn -5qn-1+6qn-2 = 0 n2

  


2
q n x  5 q n-1 x  6 q n-2 x  0
n

2
n

2
n


A( x)   q n x n

0
  
(A(x)-q 0 -q1x)  5x  q n x  6 x
n 2
 qn x  0
n

1 0

 (A(x)-1  2x)  5x(A(x)-1)  6 x 2 A( x)  0

A(x)(1  5x  6 x )  1  7x
2
 1 7x
A(x) 
1  5x  6x 2
Thm : Generating function A(x) for solution
of degree three linear homogenous recurrence
relation with constant coefficients
q n  r1q n-1  r2 q n-2  r3q n-3  0 , n  3
q 0  (q1  r1q 0 ) x  (q 2  r1q1  r2 q 0 ) x 2
is A(x) 
1  r1x  r2 x  r3 x
2 3
First order Linear inhomogeneous
recurrence relation and generating
function
tested : Solve the recurrence
relation
qr-2qr-1+qr-2 , = 2r+r, r≥2 ,
q0=0=q1
With the help of generating
functions.
 qr-2qr-1+qr-2 = 2r+r, r2

  


2
q r x -2 q r-1 x   q r-2 x
r

2
r

2
r

 
  2 x   rx ,
r r r

2 2
  
(A(x)-q 0 -q1x )-2x 
1
qr x  x
r 2

0
qr x r

 
  
   2 x -1-2x     rx -x 
r r r

 0   0 
 A(x)-2x(A(x)-q0 )  x A(x) 2

1 2
 (1  2 x)  (1  3x)  x(1  x)

 A(x)(1-2x  x ) 2

1 2
 (1  2 x)  (1  3x)  x(1  x)
 A(x)
1 2 2 4
 (1  2 x) (1  x)  (1  3x)(1  x)  x(1  x)
Now find partial fractions of
(1-2x)-1(1-x)-2
1 L C M
  
(1  2 x)(1  x) 2
(1  2 x) (1  x) (1  x) 2

we find
1 4 2 1
  
(1  2 x)(1  x) 2
(1  2 x) (1  x) (1  x) 2
 1 2 4
A( x)   (1  3x)(1  x)  x(1  x)
(1  2 x)(1  x) 2

4 2 1 1  3x x
    
(1  2 x) (1  x) (1  x) (1  x) (1  x)
2 2 4

4 2 2 3x x
    
(1  2 x) (1  x) (1  x) (1  x) (1  x)4
2 2

   
A( x)   (4)2 x - 2x  2 (r  1)x  3 (r)x
r r r r r

0 0 0 0

 4-1  r  r 1

  x
0  r 
    
A( x)   (4)2 x - 2x  2 (r  1)x  3 (r)x
r r r r r

0 0 0 0

 4-1  r  r 1

  x
0  r 

 4-1  r  r 1 
2 r r
0  r x    x
  r 1  r-1 

(r  2)(r  1)r r
 x
r 1 6

(r  2)(r  1)r r

 x
r 0 6
    
A( x)   (4)2 x - 2x  2 (r  1)x  3 (r)x
r r r r r

0 0 0 0

(r  2)(r  1)r r
  x
r 0 6
r (r  1)(r  2)
q r  4(2)  2  2(r  1)  3r 
r

6
r (r  1)(r  2)
 4(2)  4  5r 
r

6
check q 0  0  q1
q2  6
3 article 3.4 Solve for q n
degree three linear homogenous recurrence relation
q n  3q n-2  2q n-3  0 , n  3
q 0  1,q1  0, q 2  0, through generating
function
Solution :
q n x  3q n-2 x  2q n-3 x  0, n  3
n n n

  

q
3
n x  3 q n-2 x  2 q n-3 x  0
n

3
n

3
n
Solution :
  

q
3
n x  3 q n-2 x  2 q n-3 x  0
n

3
n

3
n

  
  q n x  3 q n x
n n2
 2 q n x n 3
0
3 1 0

 ( A( x)  q0  q1 x  q2 x 2
)  3 x ( A( x)  q )
2
0
 2 x3 A( x)  0
 ( A( x)  q0  q1 x  q2 x 2 )

3x 2 ( A( x)  q )
0
 2 x A( x)  0
3

( A( x)  1  0 x  0 x 2 )  3x 2 ( A( x)  1)  2 x 3 A( x)  0

A( x)(1  3x  2 x )  1  3x
2 3 2
A( x)(1  3x  2 x )  1  3x
2 3 2

1  3x
2
1  3x2
A( x)  
(1  3x  2 x ) (1  x) (2 x  1)
2 3 2

1  3x
2
L M C
  
(1  x) (2 x  1) 1-x (1-x) (1  2x)
2 2
 1  3x 2
L M C
  
(1  x) (2 x  1) 1-x (1-x) (1  2x)
2 2

1  3x  L(1  x)(1  2 x)  M (1  2 x)  C (1  x)
2 2

x  1  2  3M  M  2 / 3
x  1/ 2  1/ 4  (9 / 4)C  C  1/ 9
x  0  1  L  C  M  L  1 C  M
2 1 14
 1  
3 9 9
 1  3x2
L M C
  
(1  x) (2 x  1) 1-x (1-x) (1  2x)
2 2

1  3x
2
14 2 1
  
(1  x) (2 x  1) 9(1-x) 3(1-x) 9(1  2x)
2 2
 1  3x
2
14 2 1
  
(1  x) (2 x  1) 9(1-x) 3(1-x) 9(1  2x)
2 2


14 n  2 
1
  x   (n  1) x   (2) x
n n n

0 9 0 3 0 9
 
14 n  2 
1
  x   (n  1) x   (2) x
n n n

0 9 0 3 0 9


  qn x n

 2 14 2 1 n
q n      n  (2) 
 3 9 3 9 
8 2 1 n
   n  (2) 
9 3 9 
 4 Find general solution for q n for solution of
degree three linear homogenous recurrence relation
q n -3q n-1  3q n-2  q n-3  0 , n  3 through generating
function hence find solution satisfying
q 0  1,q1  1, q 2  1

Solution :
q n x  3q n-1 x  3q n-2 x  q n-3 x  0, n  3
n n n n

   
  q n x  3 q n-1 x  3 q n-2 x   q n-3 x  0
n n n n

3 3 3 3
Solution :
   

q
3
n x  3 q n-1 x  3 q n-2 x   q n-3 x  0
n

3
n

3
n

3
n

   
  q n x  3 q n x
n n 1
 3 q n x n2
  qn x n 3
0
3 2 1 0

 ( A( x)  q0  q1 x  q2 x 2
)  3x( A( x)  q  q x)
0 1
 3x ( A( x)  q )  x A( x)  0
2 3
0
( A( x)  q0  q1 x  q2 x 2
)  3x( A( x)  q  q x)
0 1
 3x ( A( x)  q )  x A( x)  0
2 3
0
A( x)(1  3x  3x 2  x3 )
 q  q 1 x  q2 x 2  3xq  3q 1 x 2  3q 0 x 2
0 0
q 0  (q1 -3q 0 ) x  (q 2 -3q1  3q 0 ) x 2
A(x) 
1-3x  3x 2 -x 3
 q 0  (q1 -3q 0 ) x  (q 2 -3q1  3q 0 ) x 2
 3
(1-x)
L C M
  
1-x (1-x) (1-x)32

L C M

0
qr x 
r
 2

1-x (1-x) (1-x) 3

  

0
q r x  L x  C
r

0
r
 (1  r )x
0
r

(r  2)(r  1) r

M x
0 2
(r  2)(r  1)
 q r  L  C (1  r )  M
2
 (r  2)(r  1)
q r  L  C (1  r )  M
2
q0  1  L  C  M .......(i )
q1  1  L  2C  3M ......(ii )
q2  1  L  3C  6M .....(iii )

(i ) & (ii)  C  2M  0 M  2
L  1
(ii ) & (iii)  C  3M  2 C4

q r  1  4(1  r )  (r  2)(r  1)
 Check : q0  1,q1  1,q2  1
q3  1  4(1  3)  (3  2)(3  1)  -5
q3 -3q 2  3q1  q0  0
Q.10 Solve the divide & conquer 10
8 Solve relation qn=qn/2+2n-1, n2,
q1=1,For n=2r

Solution : q 2r  q 2r-1 2r1 1 Qr  q 2r

transformed recurrence relation is
Q r=Qr-1+2r+1 -1, r≥1, Q0=1
 r 1
Q r -Qr-1  2 -1, r  1 Q 1 -Q0  2 -1, ....(1)
2

Q 2 -Q1  2 -1,
3
...(2) Qr=4(2r-1)-r+1

Q 3 -Q2  2 -1,
4
...(3)

r 1
Q r -Q r-1  2 -1, ...(r) Add all we get

r 1
Q r -Q0  2  2  ...........2 -r
2 3

r 1
Q r -1  2  2  ...........2 -r
2 3

Qr=4(1+2+…….2r-1)-r+1
Q r  4(2)  3  ( r )
r

q 2r  4(2)  3  ( r )
r

q n  4n  3  log 2 n for n  2 r
tested : Find general solution of the
recurrence relation
qr-2qr-1+qr-2 , = 2r+r, r≥2
taking help of generating
functions.
 qr-2qr-1+qr-2 = 2r+r, r2
  


2
q r x -2 q r-1 x   q r-2 x
r

2
r

2
r

 
  2 x   rx ,
r r r

2 2
  
(A(x)-q 0 -q1x )-2x  1
qr x  x
r 2

0
qr x r

 
   
   2 x -1-2x     rx -x 
r r r

 0   0 
1 2
(A(x)-q 0 -q1x)-2x(A(x)-q 0 )  x A(x)  (1  2 x)  (1  3x)  x(1  x)
2

1 2
(1-2x+x )A(x)  (1  2 x)  (1  3x)  x(1  x) +q 0 +q1x-2xq 0
2

q0 +q1x-2xq0  (1  2 x)1  (1  3x)  x(1  x) 2

 A( x) 
(1  x) 2
 1 2
q0 +q1x-2xq0  (1  2 x)  (1  3x)  x(1  x)
 A( x) 
(1  x)2
x(q1  2q0 )  q0  (1  3x) 1 x
  
(1  x) 2
(1  x) (1  2 x) (1  x) 4
2

1 L C M
  
(1  2 x)(1  x) 2
(1  2 x) (1  x) (1  x) 2
we find
1 4 2 1
  
(1  2 x)(1  x) 2
(1  2 x) (1  x) (1  x) 2

x(q1  2q0 )  q0  (1  3x) A C

 
(1  x) 2
1  x (1  x) 2
 x(q1  2q0 )  q0  (1  3x) 1 x
  
(1  x) 2
(1  x) (1  2 x) (1  x)
2 4

x 
 4-1  r  r 1
  x
(1  x) 4
0  r 
 x(q1  2q0 )  q0  (1  3x) 1 x
A( X )   
(1  x) 2
(1  x) (1  2 x) (1  x)
2 4

A C 4 2 1 x
=  +   
(1  x) (1  x) (1  2 x) (1  x) (1  x) (1  x)
2 2 4

A  2 C 1 4 x
=   
(1  x) (1  x) (1  2 x) (1  x)
2 4
 hence general solution is

(r  1)(r  2)r
q r  A  C (1  r )  4(2 ) 
r

3!
Method of Characteristic
polynomial roots to solve linear
homogenous recurrence relation
The second-degree linear
homogeneous recurrence
relation with constant
coefficients
qn+r1qn-1+r2qn-2=0, n2. r20
If we take qn=cn ,c0 ,  0
then we get c n-2 ( 2+r1+r2 )=0
C()2+r1+r2=0
C() is called characteristic
polynomial of recurrence relation
C()2+r1+r2=0
C() is called characteristic polynomial
of recurrence relation
qn+r1qn-1+r2qn-2=0, n2.
The roots 1, 2 of this equation are called
characteristic roots.
Three possibilities for the roots:
(1) distinct real roots,
(2) repeated real roots,
(3) complex roots
qn+r1qn-1+r2qn-2=0, n2. -------(a)

Characteristic polynomial
2+r1+r2=0 -----------(i)
(I ) 1 & 2 are real and distinct roots
Then qn= 1(1 )n+ 2(2 )n
is general solution of (a) , where
1 & 2 are arbitrary constants.
(II) If 1 = 2 = is double root of
(i)
Then qn= 1( )n+ 2 n( )n
is general solution of (a)
Third degree linear
homogenous recurrence
relation
qn+ r1 qn-1+ r2 qn-2+ r3 qn-3 =0,n3, r30
---------(*)
Characteristic equation is
3+r12+r2  + r3 = 0 --------(i)
Different possibilities
(I ) 1 , 2 and 3 are real and
distinct roots of (i)
Then qn=L(1 )n+C(2 )n +M(3 )n
is general solution of (*)
(II) 1 is a double root & 2 is
a simple root of (i) Then
qn=L(1 )n+ C n(1 )n +M(2 )n
Is general solution of (*)
(III) 1 = 2 = 3 = is root of
multiplicity 3 of characteristic
polynomial (i), then
qn=L( ) +C
n n( )n +B n ()
2 n

Is general solution of (*)

The linear nonhomogeneous
recurrence relation of degree one &
two
qn+r1qn-1=f(n), n>o,
qn+r1qn-1+r2qn-2=f(n), n2
how to find general solution of
non homogenous recurrence relation
through method of characteristic roots
& method of undetermined coefficients
Let qn(h) denote the general
solution of the associated
homogeneous relation.
Let qn(p) denote a particular
solution of the given
nonhomogeneous relation.
(particular solution)
Then qn= qn(h)+ qn(p) is the general
solution of the problem.
Method for the first degree non
homogenous relation
qn+r1 qn-1= w n.
If C() 0 then qn(p)=Dn.
If C() =0 , then qn(p)=Bnn.
f(n) Characteristic polynomial Form of particular solution
C()

Dn C()0 An

Dn C()=0 ,  is root of Bns n

multiplicity s of C()

Dnp n C()0 (Q0 + Q1 n +…….Qp np ) n

Dnp n C()=0 ,  is root of ns (Q0 + Q1 n +…….Qp np ) n

multiplicity s of C()

Dnp C(1)0 (Q0 + Q1 n +…….Qp np )

Dnp C(1)=0 , 1 is root of ns (Q0 + Q1 n +…….Qp np )

multiplicity s of C()
Rajiv Kumar I semester 2012-
2013 Discrete math
Comment

In last four types of table form of the

particular solution is same if Dnp
is replaced with (R0 + R1 n +…….Rp np )
Q.2 Find the general form of
particular solution qn(p)
Need not solve for constants to the
following recurrence relations
(i) qn-2qn-1=n2n , n>o,
(ii) qn -7qn-1+12qn-2=n4n, n2
(iii) qn -3qn-1+2qn-2=n4n n2
(iv) qn -2qn-1+qn-2=4 n2
(i) qn-2qn-1=n2n , n>o,

Solution : C()= (-2)

f(n)=n2n form of particular
solution
C(2) = 0

qn(P) = n(Q0 + Q1 n )2n

(ii) qn -7qn-1+12qn-2=n4n, n2

Solution : C()= (-4) (-3)

f(n)=n4n form of particular solution

C(4) = 0 4 is simple root

qn(P) = n(Q0 + Q1 n )4n

(iii)qn -3qn-1+2qn-2=n4n n2

Solution : C()= (-2) (-1)

n
f(n)=n4 form of
particular solution
qn(P) = (Q0 + Q1 n )4n
 (iv) qn -2qn-1+qn-2=4 n2

Solution : C()= (-1) (-1)

f(n)=4 form of particular solution

1 is double root of C()

qn(P) = Q0 n2
tested : Find general solution
of recurrence relation
qn -2qn-1+qn-2=4 n2

Solution : C()= (-1) (-1) ,

qn(h) = A+Cn
f(n)=4 form of particular solution
1 is double root of C()
qn(p) = Q0 n2
qn(p) -2 qn-1(p) + qn-2(p) =4
Q0 n2 -2Q0 (n-1)2 + Q0 (n-2)2 =4

-2Q0 + 4Q0 =4Q0 =2

qn = A+Cn+2n2
4 : Solve the recurrence relation
qr-5qr-1+6qr-2 , = 4r-2 r≥2 ,
q0=1,5=q1
(i)first taking help of generating
functions
(ii) taking help of undetermined
Coefficients
 qr-5qr-1+6qr-2 , = 4r-2
   

 2
q r x -5 q r-1 x  6 q r-2 x   4 x
r

2
r

2
r

2
r-2 r

   


2
q r x -5x  q r x  6 x
r

1
r 2

0
qr x  x
r 2

0
4xr r
 2
x
(A(x)-q 0 -q1x)-5x(A(x)-q 0 )  6 x A( x)  2

1  4x
2
x
A( x)(1  5 x  6 x ) 
2
 1 q 0  1& q1  5
1 4x
1  x2  4x L M C
A( x)    
(1  4 x)(1  2 x)(1  3x) 1  4 x 1  2 x 1  3x
1  x  4 x  L(1  2 x)(1  3x)  M (1  4 x)(1  3x)  C (1  2 x)(1  4 x)
2
 1 3 2
A( x)   
2(1  4 x) 2(1  2 x) (1  3x)
  
1 r r 3
A( x)   4 x -  2 x  2 (3 )x
r r r r

2 0 2 0 0

1 r r 1
q r  (4)  3(2 )  2(3 )
r

2
lengthy : Solve the recurrence
relation qn-2qn-1+qn-2 = 2n+ 3n,
n>1 , q0=0=q1 .
Solution: Associated homogenous
equation
qn-2qn-1+qn-2 =0
C()= 2-2+1 ,
C()= 0 , i.e =1 is a double root
Hence qn(h)=A + Bn,
f(n) = 2n+ 3n = f1(n) + f2(n)
 2n = f1(n) , f2(n) = 3n
f1(n) = 2n ,
Now find (qn(p))1 for
f1(n) is not solution of homogenous
equation hence set
(qn(p))1 =  2n & find 
For that
(qn(p))1 -2 (qn-1(p))1 + (qn-2(p))1 = 2n
 2n -2  2n-1+  2n-2 = 2n
2n-2 (4  -4  +  )= 2n  = 4
 (qn(p))1 = 4 (2n)

Now find (qn(p))2 for f2(n) = 3n ,

f2(n) = 3n
Hence (qn(p))2 = 0 3n
(qn(p))2 -2 (qn-1(p))2 + (qn-2(P))2 = 3n
0 3n - 20 3n-1+0 3n-2=3n
90 - 60 +0 =9  0 =9/4
qn= qn(h)+ qn(p) = qn(h)+ (qn(p))1 + (qn(p))2
= A + Bn + 4 (2n)+(9/4 ) 3n
qn= A +Bn + 4 (2n)+(9/4 ) 3n
q0 =0 =A+4+(9/4)
q1 =0 =A+B+8+(27/4)
A=-(25/4)
B= -(17/2)
qn=-(25/4) -(17/2) n + 4 (2n)+(9/4 ) 3n

Check q2=13
Q.1 Find particular solution to the
recurrence relation
qn-3qn-1+2qn-2 = 5n+3, n2 ,
using method of undetermined
coefficients

Solution : Homogenous equation

qn-3qn-1+2qn-2 = 0
C()= 2 -3+2=(-2) (-1)
=2 & =1
As C(1)=0 & 1 is simple root
& f(n) is a polynomial , we have
qn(p)  0 + 1n
but for reasons that 1 is simple
root of C()
qn(p)=(0 + 1n)n
qn(p) -3 qn-1(p)+ 2qn-2(p) = 5n+3
(0 + 1n)n -3 {0 + 1(n-1)}(n-1)
+2 {0 + 1(n-2)}(n-2)=5n+3
 (0 + 1n)n -3 {0 + 1(n-1)}(n-1)
+2 {0 + 1(n-2)}(n-2)=5n+3
(0 n +1n2 ) -3 0 (n-1)-3 1(n-1)2
+ 2  (n-2)+2  (n-2)2 = 5n+3
0 1

(0 n +1n2 )+3 0 -3 0n- 31n2

+6 1n- 31 +2 0 n-4 0
+2 1n2 - 8 1n + 81 = 5n+3
(0 n +1n2 )+ 3 0 -3 0n- 31n2
+6 1n- 31 +2 0 n-4 0
+2 1n2 - 8 1n + 81 = 5n+3
equating coefficients of n on left and right

i.e, 0 n -3 0 n +6 1n+2 0 n -81n =5n

 -2 1 =5  1 =-5/2
& 51 - 0 =3  0 = -31/2
qn(p)={-(31/2)–(5/2)n)}n
Q.A: qn -3qn-1+2qn-2=n2n n2
solve for q0 =q1 =1
Solution : homogenous equation
qn-3qn-1+2qn-2 = 0
C()= 2 -3+2=(-2) (-1)

=2 & =1

qn(h) = C(2n)+ D
As C(1)=0 & 1 is simple root

qn(p)=(0 + 1n)n2n
qn(p) -3 qn-1(p)+ 2qn-2(p) = n2n
(0 + 1n)n2n-3{0+ 1(n-1)}(n-1) 2n-1
+2 {0 + 1(n-2)}(n-2) 2n-2=n2n

(0 n +1n2 ) 2n -3 0 (n-1) 2n-1-3 1(n-1)22n-1

+ 2 0 (n-2) 2n-2+2 1(n-2)2 2n-2= n2n
(0 n +1n2 ) 2n -3 0 (n-1) 2n-1-3 1(n-1)22n-1
+ 2 0 (n-2) 2n-2+2 1(n-2)2 2n-2= n2n

4(0 n +1n2 ) -6 0 (n-1) -6 1(n-1)2

+ 2 0 (n-2) +2 1(n-2)2 = 4n

4(0 n +1n2 )+6 0 -6 0n- 61n2

+12 1n- 61 +2 0 n-4 0
+2 1n2 - 8 1n + 81 = 4n
4(0 n +1n2 )+6 0 -6 0n- 61n2
+12 1n- 61 +2 0 n-4 0
+2 1n2 - 8 1n + 81 = 4n
equating Coefficients of n
i.e, 40 n -6 0 n +12 1n+2 0 n -81n =4n

 4 1 =4  1 =1
& 20 +2 1 =0  0 = -1
 qn(p)=(-1+n)n2n

qn = C(2n)+ D +(-1+n)n2n
q0 = C+ D=1
q1 = 2C+ D =1 i.e C=0 &
D=1
qn = 1 +(-1+n)n2n
 recurrence relation that can be
transformed to linear
recurrence relation with
constant coefficients
18 : Solve the following recurrence relations
by making an appropriate substitution to
transform the relations into recurrences
with constant coefficients
 (i ) q n  q n-1  2 q n-2  0, q 0  q1  1

Solution : substitution q n  rn
transforms relation to a linear recurrence
relation. rn  rn-1  2rn-2  0, r0  1  r1
 (i ) q n  2 q n-1  q n-2  0, q 0  q1  1

Solution : substitution q n  rn
transforms relation to a linear recurrence
relation. rn  rn-1  2rn-2  0, r0  1  r1
(i ) q n  4 q n-1  4 q n-2  0, q 0  q1  1

Solution : substitution q n  rn
transforms relation to a linear recurrence
relation. rn  rn-1  2rn-2  0, r0  1  r1
 (ii) nqn  nqn-1  qn-1  2 n
, q0  10
Solution : nq n  nq n-1  q n-1  2 n
, q 0  10
First transform to linear recurrence relation
nq n  (n  1)q n-1  2 ...............(*)
n

rn nq n
n 1
(n  1)q n 1  nq n  2 ...............(*)
q1  2 rn nq n
transformed relation is
rn 1  rn  2 n1
..........(a)
r1  2
 (ii) nqn  nqn-1  qn-1  2 n
, q0  10
Solution : nq n  nq n-1  q n-1  2 n
, q 0  10
First transform to linear recurrence relation
nq n  (n  1)q n-1  2 ...............(*)
n

rn nq n
n 1
(n  1)q n 1  nq n  2 ...............(*)
q1  2 rn nq n
 (ii) nqn  nqn-1  qn-1  2 n
, q0  10

Solution : nq n  nq n-1  q n-1  2 n

, q 0  10
First transform to linear recurrence relation
nq n  (n  1)q n-1  2 ...............(*)
n

rn nq n
 n2
(ii) (n+1)qn  (n  1)qn-1  qn-1  3 , q0  1

Solution :
First transform to linear recurrence relation
n2
(n+1)q n  nq n-1  3 ...............(*)
rn (n+1)q n
 (iii)q  2qn-1  0, q0  8
3
n

Solution : q  2q n-1  0, q 0  8
3
n

q  2q n-1  0  q
3
n
3
n  2q n-1
3log 2 q n  1  log 2 q n-1

log 2 q n  rn
3rn  rn1  1, log 2 q 0  r0  log 2 8  3
(iv)q n  nq n-1  n !, q 0  2
qn q n-1
Solution :   1, q 0  2
n ! (n  1)!

r n  r n 1  1, r0  2