0

I came across some applications of generating functions, and I'm struggling to "formally justify" why the generating function $G(x)=1+x+x^2+x^3+...$ can be expressed as $\frac{1}{1-x}$.

The way you arrive to that point is this: $x \cdot G(x)=x+x^2+x^3...$, hence $G(x)-x \cdot G(x)=1$. Follows that $G(x)=\frac{1}{1-x}$. Now if $G(x)$ were an actual sum of numbers, that process wouldn't be applicable (a sum of infinite numbers converges to $\frac{1}{1-x}$ only if $|x|<1$). So my question is why is it applicable? What's the meaning of saying that $G(x)-x \cdot G(x)=1$? Why I can't say that $S-x \cdot S=1$, if $S=1+x+x^2...$ and $x$ is a number?

I realise I don't have quite understood in deep these objects, hope someone could help :)

A source might be https://www.youtube.com/watch?v=wqnpSzEzq1w.

  • You can say that $S - x\cdot S = 1$ if $S = 1 + x + x^2 + \cdots$, as long as $|x|<1$. There is no real difference between $S$ and $G(x)$. – Arthur Sep 13 '16 at 05:27
  • You actually have a pretty good understanding. As you pointed out, $G(x)$ converges and is equal to $1/(1 - x)$ only when $|x| < 1$, but the point of a generating function is that we represent a function (which in this case is $1/(1 - x)$, by such a series, even if said series diverges (see wiki on generating functions). The reason we allow such a divergence is that we only care about the coefficients, as opposed to the numerical value of evaluating the series at a specific $x$. – JMK Sep 13 '16 at 05:29
  • I think that you might find this PDF very useful. This PDF covers even more ground, but at a somewhat higher level. And the Wikipedia article on formal power series isn’t too bad for starters, though you probably want to ignore the topological parts for now. – Brian M. Scott Sep 13 '16 at 08:19
  • Thank you! I'll have a look at it :) –  Sep 13 '16 at 08:24

0 Answers0