0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are your efforts so far? $\endgroup$ – Semiclassical Aug 29 '19 at 3:26
  • $\begingroup$ Uploading my efforts. $\endgroup$ – Sen47 Aug 29 '19 at 3:27
  • $\begingroup$ 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. $\endgroup$ – Semiclassical Aug 29 '19 at 4:01
  • $\begingroup$ Thanks sir. If you could provide the full solution, I'd be very obliged since it would help me understand Generating Functions better. I'm new to them... $\endgroup$ – Sen47 Aug 29 '19 at 4:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much, sir!!! $\endgroup$ – Sen47 Aug 29 '19 at 4:52
  • $\begingroup$ Very nicely done (+1) $\endgroup$ – clathratus Aug 29 '19 at 4:53

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.