Definition
We define the generating function as the characteristic function which encodes an infinite sequence
$$
\langle g_0, g_1, g_2, g_3 \dots \rangle
$$
as below
$$
G(x) = \sum_{i = 0}^{\infty} g_{i}x^{i}
$$
For example, the generating function of the following sequences are
$$
\begin{split}
\langle 0, 0, 0, 0, \dots \rangle
\longleftrightarrow G(x) &= 0 + 0x + 0x^2 + 0x^3 + \dots
= 0\\\\
\langle 1, 0, 0, 0, \dots \rangle
\longleftrightarrow G(x) &= 1 + 0x + 0x^2 + 0x^3 + \dots
= 1\\\\
\langle 3, 2, 1, 0, \dots \rangle
\longleftrightarrow G(x) &= 3 + 2x + 1x^2 + 0x^3 + \dots
= 3 + 2x + x^2\\\\
\langle 1, 1, 1, 1, \dots \rangle
\longleftrightarrow G(x) &= 1 + x + x^2 + x^3 + \dots
= \frac{1}{1 - x}\\\\
\end{split}
$$
Thee last equation does not hold when
$$
|x| \ge 1
$$
But in the context of generating functions, we regard infinite series as formal algebraic objects and define generating function as symbolic identities that hold for purely algebraic reasons. We won’t worry about convergence issues for now.
Some other examples are
$$
\langle 1, -1, 1, -1, \dots \rangle \longleftrightarrow
G(x) = 1 - x + x^2 - x^3 + \dots = \frac{1}{1 +
x}\\\\
\langle 1, a, a^2, a^3, \dots \rangle
\longleftrightarrow G(x) = 1 + ax + a^2 x^2 + a^3 x^3 + \dots
= \frac{1}{1 - ax}\\\\
\langle 1, 0, 1, 0, 1, 0, \dots
\rangle \longleftrightarrow G(x) = 1 + x^2 + x^4 + \dots
= \frac{1}{1 - x^2}\\\\
$$
Properties
Scaling
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
$$
then
$$
\langle c \cdot g_0, c \cdot g_1, c \cdot g_2, c \cdot
g_3, \dots \rangle \longleftrightarrow H(x) = \sum_{i =
0}^{\infty} c \cdot g_{i}x^{i} = c \cdot \sum_{i =
0}^{\infty} g_{i}x^{i} = c \cdot G(x)\\\\
$$
For Example
$$
2 \cdot \langle 1, 0, 1, 0, 1, 0, \dots \rangle =
\langle 2, 0, 2, 0, 2, 0, \dots \rangle \longleftrightarrow G(x)
= 2 + 2x^2 + 2x^4 + \dots = 2 \cdot \frac{1}{1 - x^2}
= \frac{2}{1 - x^2}\\\\
$$
Addition
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
\langle h_0, h_1, h_2, h_3,
\dots \rangle \longleftrightarrow H(x)\\\\
$$
then
$$
\langle g_0 + h_0, g_1 + h_1, g_2 + h_2, g_3 + h_3, \dots
\rangle \longleftrightarrow \sum_{i = 0}^{\infty} (g_{i} +
h_{i}) \cdot x^{i} = \sum_{i = 0}^{\infty} g_{i}x^{i} +
\sum_{i = 0}^{\infty} h_{i}x^{i} = G(x) + H(x)\\\\
$$
For Example
$$
\langle 1, 1, 1, 1, \dots \rangle + \langle 1, -1, 1, -1,
\dots \rangle = \langle 2, 0, 2, 0, \dots \rangle
\longleftrightarrow G(x) = \frac{1}{1 - x} + \frac{1}{1 + x}
= \frac{2}{1 - x^2}\\\\
$$
Right Shifting
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
$$
then the sequence by adding k leading zeros
$$
\langle 0, 0, \dots, 0, g_0, g_1, g_2, g_3, \dots \rangle
\implies x^k \cdot G(x) = \sum_{i = 0}^{\infty}
g_{i}x^{i}x^{k} = g_{0}x^{k} + g_{1}x^{k + 1} + g_{2}x^{k +
2} + g_{3}x^{k + 3} + \dots\\\\
$$
For Example
$$
\langle 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, \dots \rangle =
\frac{x^4}{1 - x}
$$
Differentiation
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
$$
then
$$
G^{\prime}(x) = \frac{d}{dx}(g_{0} + g_{1}x +
g_{2}x^{2} + g_{3}x^{3} + g_{4}x^{4} + \dots) \longleftrightarrow
\langle g_1, 2 g_2, 3 g_3, 4 g_4, \dots \rangle
$$
For Example
$$
\begin{split}
& \langle 1, 1, 1, 1, \dots \rangle
\longleftrightarrow G(x) = \frac{1}{1 - x}\\\\
\text{Differentiation}
\quad & \langle 1, 2, 3, 4, \dots \rangle \longleftrightarrow
1 + 2x + 3x^2 + 4x^3 + \dots = \frac{d}{dx}(1 + x + x^2 + x^3
+ \dots) = \frac{d}{dx}{\frac{1}{1 - x}} = \frac{1}{(1 -
x)^2}\\\\
\text{Right Shifting} \quad & \langle 0, 1, 2,
3, 4, \dots \rangle \longleftrightarrow \frac{x}{(1 - x)^2}\\\\
\text{Differentiation}
\quad & \langle 1, 4, 9, 16, \dots \rangle \longleftrightarrow
\frac{d}{dx}{\frac{x}{(1 - x)^2}} = \frac{1 + x}{(1 -
x)^3}\\\\
\text{Right Shifting} \quad & \langle 0, 1, 4,
9, 16, \dots \rangle \longleftrightarrow x \cdot \frac{1 + x}{(1 -
x)^3} = \frac{x(1 + x)}{(1 - x)^3}
\end{split}
$$
So, we have found the sequence of squares
Convolution
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
\langle h_0, h_1, h_2, h_3,
\dots \rangle \longleftrightarrow H(x)\\\\
$$
then
$$
G(x) * H(x) = \sum_{i = 0}^{\infty}
c_{i}x^{i}
$$
where
$$
c_n := \sum_{i = 0}^{n} g_{i}h_{n - i}
$$
Proof
$$
\begin{array}{l|lllll}
& h_{0}x^{0} & h_{1}x^{1} & h_{2}x^{2} &
h_{3}x^{3} & \dots\\\\
\hline
g_{0}x^{0} &
g_{0}h_{0}x^{0} & g_{0}h_{1}x^{1} & g_{0}h_{2}x^{2} &
g_{0}h_{3}x^{3} & \\\\
g_{1}x^{1} & g_{1}h_{0}x^{1}
& g_{1}h_{1}x^{2} & g_{1}h_{2}x^{3} & \dots &
\\\\
g_{2}x^{2} & g_{2}h_{0}x^{2} & g_{2}h_{1}x^{3}
& \dots & & \\\\
g_{3}x^{3} & g_{3}h_{0}x^{3}
& \dots & & & \\\\
\vdots & \dots &
& & &
\end{array}
$$
We notice that all terms involving the same power of $x$ lie on a diagonal.
Summation
If
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
\longleftrightarrow G(x)\\\\
$$
then
$$
\langle s_0, s_1, s_2, s_3, \dots \rangle
\longleftrightarrow \frac{G(x)}{1 - x}\\\\
$$
where
$$
s_n := \sum_{i = 0}^{n} g_{i}
$$
For Example
$$
\frac{1}{1 - x} \frac{x(1 + x)}{(1 - x)^3} =
\frac{x(1 + x)}{(1 - x)^4}
$$
is the generating function for the sequence where the nth element is
$$
s_n = \sum_{i=0}^{n} i^2
$$
Proof
For any sequence represented by $G(x)$, we multiply with
$$
\frac{1}{1 - x} \longleftrightarrow \langle 1, 1, 1, 1,
\dots \rangle
$$
then the nth element of the sequence is
$$
\sum_{i = 0}^{n} g_{i} \cdot 1
$$
Find the nth element
Taylor Series
Let
$$
G(x)
$$
be the generating function for the sequence
$$
\langle g_0, g_1, g_2, g_3, \dots \rangle
$$
then
$$
g_0 = G(0)\\\\
g_n =
\frac{G^{(n)}(0)}{n!}\\\\
$$
Partial Fractions
While it is theoretically possible to compute the nth derivative of $G(x)$, using generating functions to get the result may have seemed to be more complicated. The good news is that we can use the method of partial fractions to express any generating function that is a ratio of polynomials as a sum of a polynomial.
$$
\frac{cx^{a}}{(1 - ax)^{b}}
$$
where $a$ and $b$ are integers and $b \gt a \ge 0$. We do that because it is easier to compute the derivative.
After some calculation (see reference 1), we can conclude that the element in the sequence represented by
$$
\frac{cx^{a}}{(1 - ax)^{b}}
$$
is
$$
\frac{c(n - a + b - 1)! a^{n - a}}{(n - a)!(b - 1)!}
$$