All notes
NumberTheory

Series

Geometric series

Derive the sum

Suppose the sum is $S$: $$ (1+x+x^2+x^3+\ldots+x^n)x - (1+x+x^2+x^3+\ldots+x^n) = (x-1)S $$ $$ x^{n+1}-1 = (x-1)S$$ $$ S = \frac{x^{n+1}-1}{x-1} $$

$$ 1+x+x^2+x^3+\ldots = \lim_{n\rightarrow \infty} \frac{x^n - 1}{x-1} $$ So only when $\|x\| \lt 1$: $$ 1+x+x^2+\ldots = \frac{1}{1-x} $$

Generating Functions

MIT OpenClassWare.

Significance. Generating functions transform problems about sequences into problems about functions, for which we've got piles of mathematical machinary.

Ordinary Generating Function
For a sequence $\{a_n\}$, $ G(x) = a_0 + a_1 x + a_2 x^2 + \ldots$.

A generating function is a formal power series, which means:

Correspondence: $$ a_0,\; a_1,\; a_2,\; \ldots \; \leftrightarrow a_0+a_1x+a_2x^2+\ldots$$ For example: $$ 0,0,0,... \; \leftrightarrow 0+0x+0x^2+\ldots = 0$$ $$ 3,2,1,0,... \; \leftrightarrow 3+2x+1x^2+\ldots = 3+2x+x^2$$

Closed form generating functions

Recall the geometric series: $$ 1+z+z^2+\ldots = \frac{1}{1-z}, \; |z|\lt 1$$ Since we don't worry about convergence for now, this formula gives closed form generating functions for a lot of sequences: $$ 1,1,1,1,\ldots \leftrightarrow \frac{1}{1-x} $$ $$ 1,-1,1,-1,\ldots \leftrightarrow \frac{1}{1+x} $$ $$ 1,a,a^2,a^3,\ldots \leftrightarrow \frac{1}{1-ax} $$ $$ 1,0,1,0,\ldots \leftrightarrow \frac{1}{1-x^2} $$

Operation Rules

If $$ \{a_n\} \leftrightarrow F(x)$$ $$ \{b_n\} \leftrightarrow G(x)$$ 1. Then, Scaling Rule: $$ kF(x) \leftrightarrow \{k\cdot a_n\}$$ 2. Addition: $$ F(x)+G(x) \leftrightarrow \{a_n+b_n\}$$ 3. Right Shifting ($k$ zeros): $$ \{ \overbrace{0,0,\ldots}, a_0, a_1, \ldots\} \leftrightarrow x^k F(x)$$ 4. Differentiation (Note $a_0$ is missing): $$ F'(x) \leftrightarrow \{a_1, 2a_2, 3a_3, \ldots\}$$ Since: $$ \frac{d}{dx} (a_0+a_1x+a_2x^2+\ldots) = a_1+2a_2x+3a_3x^2+\ldots $$ 5. Product Rule: $$F(x)\cdot G(x) \leftrightarrow \{c_0, c_1, c_2, \ldots\}$$ where $c_n = \sum_{i+j=n} a_ib_j$. See below for detail.
6. Summation Rule: $$ \{s_0, s_1, s_2, \ldots\} \leftrightarrow F(x)\cdot \frac{1}{1-x}$$ where $s_n = \sum_{i=0}^n a_i$.

Differentiation

There are two effects in differentiation. 1. Multiply by index; 2. Left shifting one place. We usually want one of them and cancel the other out.

For example, find the generating function for $\{0, 1, 4, 9, \ldots \}$:
Based on the observation: $ 0, 1, 4, 9, \ldots = 0\cdot 0, 1\cdot 1, 2\cdot 2, \ldots$, $$ 1,1,1,1,\ldots \leftrightarrow \frac{1}{1-x}$$ $$ 1,2,3,4,\ldots \leftrightarrow F'(x) = \frac{1}{(1-x)^2}$$ $$ 0,1,2,3,\ldots \leftrightarrow x \cdot \frac{1}{(1-x)^2}$$ $$ 1,4,9,\ldots \leftrightarrow F''(x) = \frac{1}{(1-x)^2} + x \cdot 2 \cdot \frac{1}{(1-x)^3} = \frac{2x + 1-x}{(1-x)^3} = \frac{x+1}{(1-x)^3}$$ $$ 0,1,4,9,\ldots \leftrightarrow x\cdot \frac{x+1}{(1-x)^3}$$

Products

Multiply two polynomial functions: $F(x)\cdot G(x) = \sum c_n x^n$. Now we infer the $c_n$ out: $$ (a_0+a_1x+a_2x^2+\ldots)(b_0+b_1x+b_2x^2+\ldots) = a_0b_0+(a_0b_1+a_1b_0)x+(a_2b_0+a_1b_1+a_0b_2)x^2+\ldots$$ Here $c_n = a_0b_n + a_1b_{n-1} + \ldots + a_nb_0$, is called convolution of sequences $\{a_n\}$ and $\{b_n\}$.

Summation rule

We could derive this rule directly from product rule:
Let $G(x) = \frac{1}{1-x}$, which corresponds to $\{1,1,1,1,\ldots\}$. For any $\{a_n\} \leftrightarrow F(x)$, $$ F(x)\cdot G(x) \leftrightarrow \{a_0b_0, a_1b_0+a_0b_1, \ldots\} \leftrightarrow \{s_0, s_1, \ldots\}$$

For example, if we want to get: $$ s_n = \sum_{i=0}^n i^2$$ We know the sequence is $0, 1, 4, 9, \ldots$, which corresponds to $\frac{x(1+x)}{(1-x)^3}$. Hence the generating function for summation is $\frac{x(1+x)}{(1-x)^4}$. Finally, to obtain the summation, Taylor series expansion is used.

Extracting coefficients

Taylor series. Let $F(n)$ be the generating function, then $a_n = \frac{F^{(n)}(0)}{n!}$.
This gives the Taylor/Maclaurin expansion: $F(x) = \sum_{n=1}^\infty \frac{F^{(n)}(0)}{n!} x^n$.