Solve the recurrence relation $a_r=3a_{r-1}+2, r > =1$ with $a

2.3kviews

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

written 8.9 years ago by

teamques10 ★ 70k

modified 3.8 years ago by

pedsangini276 • 4.8k

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: Dec 2013

discrete mathematics

ADD COMMENT EDIT

1 Answer

191views

written 8.9 years ago by

teamques10 ★ 70k

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 …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.