0
2.1kviews
Solve the recurrence relation ar=3ar1+2,r>=1 with a0=1, using generating function.

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: Dec 2013

1 Answer
0
191views

The given equation can be rearranged as

ar3ar1=2ar13ar2=2ar23ar3=2a33a2=2a23a1=2a13a0=2

Adding all, we get

ar2(a1+a2++a(r1))=2+2+(n+1)termsar2(a1+a2++ar1)=2(n1)ar2(a1+(n1)d)=2(n1)

Where d is the common difference.

Please log in to add an answer.