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.
Best Answer
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.