motivation for $1/(1-x)$ used in generating functions

670 Views Asked by At

A closed form for the infinite series $1+x+x^2+\ldots+x^n$ works out quickly like this:

$S_n = 1+x+x^2+\ldots+x^n$

$xS_n = x+x^2+x^3\ldots+x^{n-1}$

$S_n-xS_n=S_n(1-x)=1+x-x+x^2-x^2\ldots+x^n-x^n-x^{n-1} = 1-x^{n+1}$

$S_n=\frac{1-x^{n+1}}{1-x}$

When $|x|<1$ and $n$ is large, this becomes $\frac{1}{1-x}$.

I've been trying to udnerstand the basics of generating functions, and every account seems to take the fact that $\frac{1}{1-x}$ generates $\sum{x^n}$ for granted, saying that we don't worry about convergence and leaving it at that.

So why we don't use $\frac{1-x^{n+1}}{1-x}$ to generate $\sum{x^n}$ instead? I'm looking for a separate explanation or derivation explaning the general use of $\frac{1}{1-x}$.

2

There are 2 best solutions below

4
On BEST ANSWER

I think you have a few misconceptions running around here. First of all, it is not true that "$\frac{1}{1-x}$ generates $\sum x^n$."
Rather, for $ |x| < 1$ we have that $$ \sum_{i =0}^{\infty} x^i = \frac{1}{1-x}, $$ whereas for every $x \in \mathbb{C}$ $$ \sum_{i =0}^{n} x^i = \frac{1-x^{n+1}}{1-x}. $$ Note that, if $|x| < 1$ and we let $n \to \infty$, we have $|x^{n+1}| \to 0$. So the two equations are not contradicting or from different realms or whatever. It's just that in one case the sum is finite and in the other it's not.

Another important point I think you are missing: $f(x) = \frac{1}{1-x}$ is a function on the whole complex plane, $x=1$ excluded. Just for $|x| < 1$ you may also write the function as the power series above.

I don't know what exactly you mean with the term generating in your context, but a generating function is not an object that generates functions (I think it's that what you mean), and it's not a bridge between functions and formal power series. It is rather a formal power series that is associated to a sequence of numbers. These formal power series may be interpreted as functions in certain areas of the complex plane, eg for $|x | < 1 $ in the example above. By interpreting the formal power series as a function and studying its properties (eg radius of convergence) we can learn a lot about the sequence that is associated with the generating function (eg its asymptotic growth).

2
On

A generating function is a formal power series. The set of formal power series forms a ring and in this ring $1-x$ has an inverse, which is $1+x+x^2+\cdots$.