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.


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.

  • 2
    $\begingroup$ $\sum 2^{n}x^{n}$ is a geometric series. $\endgroup$ Aug 17 '20 at 9:52
  • $\begingroup$ 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"? $\endgroup$ Aug 17 '20 at 10:41
  • $\begingroup$ @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. $\endgroup$
    – Math123
    Aug 17 '20 at 10:55

You made a mistake somewhere in the generating function derivation (hard to tell where since you did not include this part), I've got

\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.