# Use generating functions to solve the recurrence relation

Use generating functions to solve $$a_n = 3a_{n-1} - 2a_{n-2} + 2^n + (n+1)3^n$$.

What I have so far, not sure if I forgot to do something or am missing out on something obvious: Define $$G(x) = \sum_{n=0}^{\infty} a_nx^n$$

Then, $$G(x) = a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} a_nx^n$$

= $$a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} (3a_{n-1} - 2a_{n-2} + 2^n + (n+1)3^n)x^n$$

= $$a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} 3a_{n-1}x^n - \sum_{n=3}^{\infty} 2a_{n-2}x^n + \sum_{n=3}^{\infty} 2^nx^n + \sum_{n=3}^{\infty} (n+1)3^nx^n$$

= $$a_0 + a_1x + a_2x^2 + 3\sum_{n=3}^{\infty} a_{n-1}x^n - 2\sum_{n=3}^{\infty} a_{n-2}x^n + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$$

=$$a_0 + a_1x + a_2x^2 + 3x\sum_{n=3}^{\infty} a_{n-1}x^{n-1} - 2x^2\sum_{n=3}^{\infty} a_{n-2}x^{n-2} + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$$

= $$a_0 + a_1x + a_2x^2 + 3x\sum_{n=2}^{\infty} a_nx^n - 2x^2\sum_{n=1}^{\infty} a_nx^n + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$$

After making these replacements, you will have $$G(x)$$ on both sides, and a couple of other summations you can (hopefully?) find closed forms for. Then you can solve for $$G(x)$$. $$\sum_{n=1}^\infty a_nx^n=G(x)-a_0\hspace{1.3cm}$$ $$\sum_{n=2}^\infty a_nx^n=G(x)-a_0-a_1x$$
Hint: if $$G(x)$$ is the generating function for $$a_n$$, what are $$x G(x)$$ and $$x^2 G(x)$$ the generating functions for?
• I know that $3xG(x) = \sum_{n=0}^{\infty} a_nx^n$, but my issue is how to make the bottom index of the sum to be n=0. Do I have to introduce some of the other previous terms into the summation? – Norman Contreras Apr 10 at 20:16
• No, $x G(x) = \sum_{n=0}^\infty a_n x^{n+1} = \sum_{n=1}^\infty a_{n-1} x^n$. – Robert Israel Apr 11 at 0:50
Given that $$G(x) = \sum_{n=0}^{\infty} a_nx^n$$, you can write $$a_n$$ as $$[x^n]G(x)$$. Then the recurrence becomes $$[x^n]G(x) = 3[x^{n-1}]G(x) - 2[x^{n-2}]G(x) + 2^n + (n+1)3^n$$
If we introduce functions $$P(x) = \sum_{n=0}^\infty 2^n x^n$$ and $$Q(x) = \sum_{n=0}^\infty (n+1)3^n x^n$$ then, by the linearity of coefficient extraction, $$[x^n]G(x) = 3[x^n]xG(x) - 2[x^n]x^2G(x) + [x^n]P(x) + [x^n]Q(x)$$ and if this holds for every $$n$$ then $$G(x) = 3xG(x) - 2x^2G(x) + P(x) + Q(x)$$ which rearranges to $$G(x) = \frac{P(x) + Q(x)}{2x^2 - 3x + 1}$$
Finding closed forms for $$P$$ and $$Q$$ is left as an exercise...