Problem
Find the ordinary generating function for each of the following sequences. In each case the sequence is defined for all $n \in \mathbb{N}_0$.
$$a_n = n$$
I'm having a very hard time understanding generating functions. I know they have something to do with taylor polynomials and I'm just really trying to wrap my head around it. Maybe if someone could guide me through this problem and work with me on it I can understand what's going on!
Thank you.
The ordinary generating function of $a_n=n$ would be $$\sum_{n=1}^{\infty}nx^n.$$
There is a function that is determined by this power series and therefore we can identify both.
We probably know that $\frac{1}{1-x}=\sum_{n=1}^{\infty}x^n$, for $|x|<1$. This means that $\frac{1}{1-x}$ is the generating function of $b_n=1$.
Suppose we take derivatives on both sides. We get $$\frac{1}{(1-x)^2}=\sum_{n=1}^{\infty}nx^{n-1}.$$
If we multiply by $x$, we get $$\frac{x}{(1-x)^2}=\sum_{n=1}^{\infty}nx^n$$.
As Wilf wonderfully puts it in the opening sentence on page 1 of his excellent book generatingfunctionology, "A generating function is a clothesline on which we hang up a sequence of numbers for display".
It is a way of taking an entire infinite sequence of numbers $a_0, a_1, a_2, a_3, \dots$, and treating the whole thing as a single object, namely the function $$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots.$$
The finite analogue would be: given a bunch of numbers, consider the polynomial with those numbers as coefficients. For example, given some three arbitrary numbers, say $a_0 = 42, a_1 = 23, a_2 = 1003$, you might form the quadratic polynomial $P(x) = 42 + 23x + 1003x^2$.
What this gives you is that now you can speak of the single object $P$ (or $A$ in the general case), which implicitly encodes all the information about the numbers you started with, instead of speaking of the numbers separately. And they have several useful properties. (Such as convolution of sequences corresponding to multiplication of generating functions (or polynomials: in fact, the convolution of polynomials also comes in useful in things like the discrete Fourier transform, for instance).)
For your problem, when the sequence is given by $a_n = n$, it means that your sequence is $$0, 1, 2, 3, 4, 5, 6, 7, \dots$$ So its (ordinary) generating function is $$A(x) = 0 + 1x + 2x^2 + 3x^3 + 4x^4 + 5x^5 + 6x^6 + 7x^7 + \dots. \tag{*}$$
That is the answer!
But in this case $A(x)$ turns out to have a simpler form (which when $x$ is a real number, is valid for $|x| < 1$), so we can write it down even more compactly. The usual way to arrive at the simpler form is to differentiate the known series for $\dfrac{1}{1-x}$, but just for fun let's try another way: we have $$A(x) = x + 2x^2 + 3x^3 + 4x^4 + 5x^5 + 6x^6 + 7x^7 + \dots$$ so multiplying by $(1-x)$ gives $$\begin{align} (1-x)A(x) &= x-x^2 \ +\ 2x^2 - 2x^3 \ +\ 3x^3 - 3x^4 \ +\ 4x^4 - 5x^5 \ +\ \dots \\ &= x + x^2 + x^3 + x^4 + \dots \end{align}$$ If we once more multiply by $(1-x)$, we get $$\begin{align} (1-x)^2A(x) &= (1-x)(x + x^2 + x^3 + x^4 + \dots) \\ &= x-x^2 \ +\ x^2-x^3 \ +\ x^3-x^4 \ +\ x^4 - x^5 \ +\ \dots \\ &= x \end{align}$$
Thus $$A(x) = \frac{x}{(1-x)^2}$$ is the compact form, for the same expression as in $(*)$ above. The connection to Taylor series is that if we take $\frac{x}{(1-x)^2}$ and write down its Taylor series, we'll get the same coefficients as in $(*)$ above. And in general if we take $A(x)$ and write down its Taylor series, we'll get the coefficients $a_n$. But that's a secondary concern (having to do with treating the generating function $A(x)$ as an analytic object / function), and IMHO you shouldn't think of it till you are comfortable with what generating functions are as purely formal objects.
