# Showing that generating function satisfies function

Suppose that the sequence $S = (s_0, s_1, \dots )$ is defined by:

$s_0 = 0$, $s_1= 1$ and $s_{n+2} = s_{n+1}+2s_n$ for $n \ge 0$. Thus, $S = (0, 1, 1, 3, 5, 11, 21,...)$.

Show that the generating function $S(x) = s_0 + s_1 x + s_2 x^2 + \dots$ satisfies $S(x) = \frac{x}{1 - x - 2x^2}$.

I would start this problem with $(1,1,1,1,1,1,...) = 1/(1-x)$ and manipulate it until I end up with $S(x) = x/(1-x-2x^2)$, but I don't know how to manipulate it.

• You can get formulas much more readable and much easier by using TeX instead of HTML. I've done a few as example (and removed a nested <sub> in passing that I think was not intended). – Marc van Leeuwen Jan 31 '13 at 6:43
• Here is a basic MathJax tutorial, with links to more information. – Brian M. Scott Jan 31 '13 at 6:50

## 2 Answers

There are many ways to do this; here’s the one that I prefer. Start with your recurrence:

$$s_n=s_{n-1}+2s_{n-2}\;.\tag{1}$$

This holds for $n\ge 2$, and in addition you have the initial conditions $s_0=0$ and $s_1=1$. If we assume that $s_n=0$ for all negative integers $n$, $(1)$ also works for $n=0$; it fails only for $n=1$, when it gives $s_1=0$ instead of $s_1=1$. I’ll fix this by adding a term:

$$s_n=s_{n-1}+2s_{n-2}+[n=1]\;,\tag{2}$$

where $[n=1]$ is an Iverson bracket whose value is $1$ if $n=1$ and $0$ otherwise. The modified recurrence $(2)$ gives the correct value for all $s_n$, again on the assumption that $s_n=0$ for $n<0$.

Now multiply $(2)$ by $x^n$ and sum over $n\ge 0$:

\begin{align*} \sum_{n\ge 0}s_nx^n&=\sum_{n\ge 0}\left(s_{n-1}+2s_{n-2}+[n=1]\right)x^n\\\\ &=\sum_{n\ge 0}s_{n-1}x^n+2\sum_{n\ge 0}s_{n-2}x^n+\sum_{n\ge 0}[n=1]x^n\\\\ &=x\sum_{n\ge 0}s_{n-1}x^{n-1}+2x^2\sum_{n\ge 0}s_{n-2}x^{n-2}+x\\\\ &=x\sum_{n\ge 0}s_nx^n+2x^2\sum_{n\ge 0}s_nx^n+x\;. \end{align*}\tag{3}

Now let $g(x)$ be the generating function: by definition

$$g(x)=\sum_{n\ge 0}s_nx^n\;.$$

From $(3)$ we see that $g(x)=xg(x)+2x^2g(x)+x$, and solving this for $x$ yields

$$g(x)=\frac{x}{1-x-2x^2}\;.$$

What does $S(x)=\frac x{1-x-2x^2}$ really mean? It means that if you multiply the foormal power series $S(x)$ by the polynomial $1-x-2x$ then you should get the polynomial $x$ (which is a power series whose coefficients become $0$ after the one for $x$). So just do the multiplication!

From the initial terms of $S$ you get that the product starts with $0x^0+1x^1$ as it should (and you only needed the constant term $1$ of $1-x-2x^2$ to find this). It remains to show that the remaining coefficients in the product are all $0$. But the coefficient of $x^{n+2}$ in the product is $s_{n+2}-s_{n+1}-2s_n$ for all $n\in\mathbf N$, and by the recurrence relation this is always $0$.

So you see the generating function identity just reflects the initial conditions and the recurrence relation in a very straightforward way (or maybe it would be more appropriate to say "straightbackward"). The correspondence is so directd that you should not have difficulty guessing the proper identity, given any similarly defined recursive sequence.