Gate Discrete Mathematics

Question

Using Generating function , solve the recurrence relation 

a_n+2 - 2a_n+1 + a_n = 2ⁿ , n>=0 , a₀=2 , a₁=1

Answer 1

a_n+2 - 2a_n+1 + a_n = 2ⁿ

Solving homogeneous part

a_n+2 - 2a_n+1 + a_n =0

take, a_n=crⁿ

r²-2r+1=0

r=1,1

a_n=(c₁+c₂n)1ⁿ..........................i

Solving non homogeneous part

a_n=A.2ⁿ

A.2ⁿ⁺²  - 2A2ⁿ⁺¹ + A.2ⁿ=2ⁿ

4A - 4A+A=1

A=1

then,a_n=2ⁿ.........................ii

from i and ii we get

a_n=(c₁+c₂n)+2ⁿ

a₀=2

c₁+1=2

or,c₁=1

a₁=1

c₁+c₂+2=1

c₂= -2

a_n=(1+(-2)n)+2ⁿ

a_n=(1-2n)+2ⁿ