# Use generating functions to solve the non-homogenous recurrence relation

Let $$a_0=0, a_1=2,$$ and $$a_2=5$$. Use generating functions to solve the recurrence equation: $$a_{n+3} = 5a_{n+2} - 7a_{n+1}+3a_n + 2^n$$ for $$n\geq0$$.

This is a book problem from Applied Combinatorics. I am really confused about tackling $$2^n$$ part of the recurrence relation using generating functions.

Edit:

I know I need to convert the recurrence into series and I have broken it down, but am struggling with getting it into a proper form to do partial fractions. These are the equations I have managed to get.

If we let $$A(x) = \sum_{n \geq 0} a_n x^n$$ be the generating function for $$a_n$$ then after the calculations I got:

$$A(x)\cdot(1-5x+7x^2-3x^3)= 12x^3 - 9 x^2 + \frac{2x}{1-2x}$$

After simplifying: $$A(x) = \frac{12x^3 - 9 x^2 + \frac{2x}{1-2x}}{1-5x+7x^2-3x^3}$$ $$= \frac{24 x^4 - 30 x^3 + 9 x^2 - 2 x}{(1-2x)(x-1)^2(3x-1)}$$

Then, the partial fraction decomposition is: $$A(x) = -\frac{8}{1-2x} + \frac{13}{4}\frac{1}{1-3x} + \frac{37}{4}\frac{1}{1-x} - \frac{1}{2} \frac{1}{(1-x)^2} - 4$$

I have tried to plug in the values, but something doesn't seem right. Please let me know where I would have gone wrong.

• $\sum 2^{n}x^{n}$ is a geometric series. Aug 17, 2020 at 9:52
• If you understand how to use generating functions for "two steps back", what difficulty do you encounter applying the same concepts to "three steps back"? Aug 17, 2020 at 10:41
• @GerryMyerson you're right. I've just updated my question and added some of the steps I have managed to do. But, I can't figure out where I may have gone wrong. Aug 17, 2020 at 10:55

\begin{align} A(x)&=2x+5x^2+\sum_{n \geq 3}a_{n}x^n\\ &=2x+5x^2+5\sum_{n \geq 3}a_{n-1}x^n-7\sum_{n \geq 3}a_{n-2}x^n+3\sum_{n \geq 3}a_{n-3}x^n+\sum_{n \geq 3}2^{n-3}x^n\\ &=2x+5x^2+5x\sum_{n \geq 2}a_{n}x^n-7x^2\sum_{n \geq 1}a_{n}x^n+3x^3\sum_{n \geq 0}a_{n}x^n+x^3\sum_{n \geq 0}2^{n}x^n\\ &=2x+5x^2+5x(A(x)-2x)-7x^2(A(x)-0)+3x^3A(x)+x^3\cdot \frac{1}{1-2x} \end{align} which solves to \begin{align} A(x)&=\frac{x(11x^2-9x+2)}{(1-2x)(1-3x)(x-1)^2}\\ &=\frac{2}{(x-1)^2}-\frac{3}{2}\frac{1}{1-x}-\frac{1}{1-2x}+\frac{1}{2}\frac{1}{1-3x}. \end{align} Check your solution, hopefully you can finish it from here.