###### Problem 211

Suppose that \(a_i=3a_{i-1} + 3^i\text{.}\)

###### (a)

Multiply both sides by \(x^i\) and sum both the left hand side and right hand side from \(i=1\) to infinity. In the left-hand side use the fact that

and in the right hand side, use the fact that

(where we substituted \(j\) for \(i-1\) to see explicitly how to change the limits of summation, a surprisingly useful trick) to rewrite the equation in terms of the power series \(\sum_{i=0}^\infty a_ix^i\text{.}\) Solve the resulting equation for the power series \(\sum_{i=0}^\infty a_ix^i\text{.}\) You can save a lot of writing by using a variable like \(y\) to stand for the power series.

###### (b)

Use the previous part to get a formula for \(a_i\) in terms of \(a_0\text{.}\)

###### (c)

Now suppose that \(a_i=3a_{i-1} + 2^i\text{.}\) Repeat the previous two steps for this recurrence relation. (There is a way to do this part using what you already know. Later on we shall introduce yet another way to deal with the kind of generating function that arises here.)

You may run into a product of the form \(\sum_{i=0}^\infty a^ix^i\sum_{j=0}^\infty b^jx^j\text{.}\) Note that in the product, the coefficient of \(x^k\) is \(\sum_{i=0}^k a^ib^{k-i} = \sum_{i=0}^k \frac{a^i}{b^i}\text{.}\)