0

2.1kviews

Solve the recurrence relation $a_r=3a_{r-1}+2, r > =1$ with $a_0= 1$, using generating function.

written 8.2 years ago by teamques10 ★ 69k

modified 3.2 years ago by pedsangini276 • 4.8k

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: Dec 2013

discrete mathematics

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

191views

written 8.2 years ago by teamques10 ★ 69k

The given equation can be rearranged as

$$a_r - 3a_{r-1}=2 \\ a_{r-1} - 3a_{r-2}=2 \\ a_{r-2} - 3a_{r-3}=2 \\ − - - - - - \\ − - - - - - \\ a_3 - 3a_2=2 \\ a_2 - 3a_1=2 \\ a_1 - 3a_0=2$$

Adding all, we get

$$a_r -2(a_1+a_2+……+a_(r-1))=2 + 2…+ (n + 1) terms \\ a_r -2(a_1+a_2+……+a_{r-1}) = 2(n-1) \\ a_r -2(a_1+ (n-1)d) = 2(n-1)$$

Where d is the common difference.

ADD COMMENT SHARE EDIT