Showing that generating function satisfies function

Question

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.

Answer 1

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}\;.$$

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