# Solve recurrence using generating functions if possible.

I would be obliged if someone could please solve the following recurrence using generating functions:

$$a_n-a_{n-1}-2a_{n-2}=4n$$

Given that: $$a_0=-4, a_1=-5$$

I know how to solve this using the usual method (adding general solution and particular solution), but would like to see a generating function approach.

The answer, anyway, is: $$a_n=2^n-2n-5$$

Thanks to all!

My efforts:

Let $$A(x)=a_0+a_1x+ \cdots +a_nx^n+ \cdots$$ be the generating function for the sequence $$a_n$$.

Then, $$A(x)-xA(x)-2x^2A(x)=a_0+(a_1-a_0)x+(a_2-a_1-2a_0)x^2+ \cdots +(a_n-a_{n-1}-2a_{n-2})x^n+ \cdots$$ gives the required sequence.

But $$A(x)(1-x-2x^2)$$ satisfies $$4+4x+ \cdots +4x^n+ \cdots$$

Or, $$A(x)(1-x-2x^2)=4( \frac 1 {1-x})$$ Simplifying and dividing gives: $$A(x)= \frac 4 {(1-x^2)(1-2x)}$$

Then, I guess, we split it into partial fractions and get the sequence, right? Please help me out now. Thanks for your help again.

• What are your efforts so far? – Semiclassical Aug 29 '19 at 3:26
• Thank you. As a minor quibble, you should also have $A(x)=\cdots+a_n x^n+\cdots$, i.e. it doesn't stop at $x^n$. Unfortunately, your proposed generating function doesn't satisfy a quick consistency check: You would have $A(0)=4$, but $a_0=-4$. I advise looking at the RHS of your $A(x)-x A(x)-2x^2 A(x)=\cdots$ equation and checking whether you have the terms right. – Semiclassical Aug 29 '19 at 4:01
You have more or less the right idea, but the right hand side is the sequence $$(4n)$$, not $$(4)$$. We have, \begin{align*} \sum_{n=0}^\infty 4n x^n &= \sum_{n=0}^\infty 4(n + 1)x^n - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\sum_{n=0}^\infty 4x^{n+1} - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{4}{1 - x} - 4\right) - \frac{4}{1 - x} \\ &= \frac{4}{(1 - x)^2} - \frac{4}{1 - x} \\ &= \frac{4x}{(1 - x)^2}. \end{align*}
As you noted, we have \begin{align*} A(x) - xA(x) - 2x^2A(x) &= a_0 + (a_1 - a_0)x + (a_2 - a_1 - 2a_0)x^2 + (a_3 - a_2 - 2a_1)x^3 + \ldots \\ &= a_0 + (a_1 - a_0)x + (4 \cdot 2)x^2 + (4 \cdot 3)x^3 + \ldots + 4n x^n + \ldots \\ &= \frac{4x}{(1 - x)^2} + a_0 + (a_1 - a_0)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 + (-5 + 4)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 - 5x \\ &= \frac{4x - (4 + 5x)(1 - x)^2}{(1 - x)^2} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2} \\ A(x) &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - x - 2x^2)} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - 2x)(1 + x)}. \end{align*} Before we apply partial fractions, it's worth testing if this fraction can be simplified at all. Plugging in $$x = -1$$ produces $$0$$, meaning that $$1 + x$$ divides it. Dividing out $$1 + x$$ from the numerator and denominator, $$A(x) = \frac{-5x^2 + 11x - 4}{(1 - x)^2(1 - 2x)}$$
Now we apply partial fractions. We wish to find $$a, b, c$$ such that $$A(x) = \frac{a}{1 - x} + \frac{b}{(1 - x)^2} + \frac{c}{1 - 2x},$$ or equivalently, $$-5x^2 + 11x - 4 = a(1 - x)(1 - 2x) + b(1 - 2x) + c(1 - x)^2.$$ Considering $$x = 1$$, $$-5 \cdot 1^2 + 11 \cdot 1 - 4 = b \cdot (-1) \implies b = -2.$$ Considering $$x = \frac{1}{2}$$, $$-5 \cdot \left(\frac{1}{2}\right)^2 + 11 \cdot \frac{1}{2} - 4 = c \cdot \left( \frac{1}{2}\right)^2 \cdot \implies c = 1.$$ Now, using these values of $$b$$ and $$c$$, we can find $$a$$ by substituting a different value for $$x$$, e.g. $$x = 0$$: $$-4 = a + (-2) \cdot 1 + 1 \cdot 1^2 \implies a = -3.$$ That is, $$A(x) = \frac{-3}{1 - x} + \frac{-2}{(1 - x)^2} + \frac{1}{1 - 2x}.$$ We finally convert these generating functions back to sequences: $$a_n = -3 + (-2)(n + 1) + 2^n = -5 + 2n + 2^n,$$ as required.