I'm using a book to try and learn generating functions; the concept is a bit confusing to me.
There is this example in the book, that, given $\sum_{n \geq 0}f_nx^n = \frac{x}{1-3x}$, find $f_n$, which is just a sequence of numbers, presumably integers since this is about combinatorics.
The book's solution is that $\frac{x}{1-3x}$ is basically $\sum_{n \geq 0}3^nx^n$, so """of course""" $f_n = 3^{n-1}$ due to the extra x. Here is the solution:
Yeah, of course. So I tried to do it myself and get the same answer. I started with
$$\sum_{n \geq 0}f_nx^n = \frac{x}{1-3x} = x\frac{1}{1-3x} = x\sum_{n \geq 0}3^nx^n = \sum_{n \geq 0}3^nx^{n+1}$$
However, to reduce the value of $n$ in the sum, we have to increase the value of $n$ to start:
$$\sum_{n \geq 0}3^nx^{n+1} = \sum_{n \geq 1}3^{n-1}x^{n}$$
as
$$\sum_{n \geq 0}3^nx^{n+1} = x + 3x^2 + ...$$
but
$$\sum_{n \geq 0}3^{n-1}x^{n} = 1/3 + x + 3x^2 + ...$$
And this completely changes the formula, as $n\geq 1$ is different than $n\geq 0$.....right? Am I doing something wrong?
In fact, when I plug in $f_n = 3^{n-1}$ into $\sum_{n \geq 0}f_nx^n$, I get
$$ \sum_{n \geq 0}3^{n-1}x^n = \frac{1}{3}\sum_{n \geq 0}3^nx^n = \frac{1}{3}*\frac{1}{1-3x}$$
From the logic before, we can also get
$$\sum_{n \geq 0}3^{n-1}x^n = \frac{1}{3} + \sum_{n \geq 1}3^{n}x^{n+1} = x\frac{1}{1-3x} + \frac{1}{3}$$
....so what's the catch? I'm sure there is a good reason the book is saying what they're saying, and I must be either wrong or operating on a different set of assumptions. Can anyone who knows more about generating functions please tell me where I'm wrong? Thanks.
The book is wrong because it claims that $f_0=1/3$ when in fact $f_0=0$. The correct formula is $$f_n=\begin{cases}3^{n-1}&\text{if $n>0$}\\0&\text{if $n=0$}\end{cases}$$