Unexpected Proofs Using Generating Functions

Question

I recently came across this beautiful proof by Erdős that uses generating functions in a unique way:

Let $S = \{a_1, \cdots, a_n \}$ be a finite set of positive integers such that no two subsets of $S$ have the same sum. Prove that $$\sum_{i=1}^n \frac{1}{a_i} < 2.$$

Question: Are there any more examples of surprising or unexpected proofs using generating functions that this community is aware of?

(Please refrain from posting answers that are widely known such as change making, closed form for Fibonacci, etc.)

The proof of the above theorem:

Proof: Suppose $0< x < 1$. We have $$\prod_{i=1}^n (1 + x^{a_i}) < \sum_{i = 0}^{\infty} x^i = \frac{1}{1-x}.$$ Thus, $$\begin{align*} \sum_{i=1}^n \log(1+x^{a_i}) &< - \log(1-x) \\ \sum_{i=1}^n \int_0^1 \frac{\log(1+x^{a_i})}{x} \ dx &< - \int_0^1 \frac{\log(1-x)}x \ dx . \end{align*}$$ Putting $x^{a_i} = y$, we obtain $$\begin{align*} \sum_{i=1}^{n} \frac{1}{a_i} \int_0^1 \frac{\log(1+y)}{y} \ dy < - \int_0^1 \frac{\log(1-x)}{x} \ dx \end{align*}$$ i.e., $$\sum_{i=1}^n \frac{1}{a_i} \left( \frac{\pi^2}{12} \right) < \frac{\pi^2}6.$$ Thus, $\sum_{i=1}^n \frac{1}{a_i} < 2$ and the theorem is proved.

Answer 1

I remember this problem from Stein & Shakarchi's Complex Analysis.

Let $\mathbb{N}$ denote the set of positive integers. A subset $S\subset \mathbb{N}$ is said to be in arithmetic progression if $$ S=\{a, a+d, a+2d, a+3d, \ldots\} $$ where $a, d\in \mathbb{N}$. Here $d$ is called the step of $S$.

Show that $\mathbb{N}$ cannot be partitioned into a finite number of subsets that are in arithmetic progression with distinct steps (except for the trivial case $a=d=1$).

Hint: Write $\sum_{n\in\mathbb{N}} z^n$ as a sum of terms of the type $\frac{z^a}{1-z^d}$.

In the hint of this problem, the terms $\frac{z^a}{1-z^d}$ represents the ordinary generating function for the characteristic function of the arithmetic progression $S=\{a, a+d, a+2d, \ldots\}$.

Another good example is this problem, and the answer by @barto

Answer 2

Sicherman dice are the only pair of 6-sided dice that are not normal dice, bear only positive integers, and have the same probability distribution for the sum as normal dice.

The faces on the dice are numbered 1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8.

(Source: Wikipedia article on Sicherman dice)

We can prove this fact using generating functions.

Let the non-standard dice $A$ and $B$ have faces $(a_1,a_2,a_3,a_4,a_5,a_6)$ and $(b_1,b_2,b_3,b_4,b_5,b_6)$.

Let $a(x) = x^{a_1}+x^{a_2}+x^{a_3}+x^{a_4}+x^{a_5}+x^{a_6}$ and $b(x) = x^{b_1}+x^{b_2}+x^{b_3}+x^{b_4}+x^{b_5}+x^{b_6}$ be the generating functions for the number rolled on dice $A$ and dice $B$ respectively.

When the product $$a(x)b(x) = (x^{a_1}+x^{a_2}+x^{a_3}+x^{a_4}+x^{a_5}+x^{a_6})(x^{b_1}+x^{b_2}+x^{b_3}+x^{b_4}+x^{b_5}+x^{b_6})$$ is expanded as a polynomial, the $x^n$ coefficient is the number of ways these non-standard dice can have a sum of $n$. If the sum of the non-standard dice has the same distribution as two standard dice, then the above product must be equal to the product of the generating functions for two standard dice, i.e. \begin{align} a(x)b(x) &= (x+x^2+x^3+x^4+x^5+x^6)^2 \\ &= [x(1+x+x^2+x^3+x^4+x^5)]^2 \\ &= [x(1+x^3)(1+x+x^2)]^2 \\ &= [x(1+x)(1-x+x^2)(1+x+x^2)]^2. \end{align}

We just need to figure out how to distribute the factors between the polynomials $a(x)$ and $b(x)$.

Since each dice must have only positive integer faces, $x$ divides both $a(x)$ and $b(x)$. Hence, $a(x)$ and $b(x)$ must each get one of the two $x$ factors.

Since dice $A$ and $B$ both have $6$ faces, $a(1) = b(1) = 6$. Notice that $(1+x)\left.\right|_{x = 1} = 2$, $(1-x+x^2)\left.\right|_{x = 1} = 1$, and $(1+x+x^2)\left.\right|_{x = 1} = 3$. Clearly, $a(x)$ and $b(x)$ must each get one of the two $1+x$ factors and one of the two $1+x+x^2$ factors.

This leaves only the two $1-x+x^2$ factors. If we distribute one to each of $a(x)$ and $b(x)$, then we will have $a(x) = b(x)$, and we'll end up with the standard dice. Thus, we have to give both $1-x+x^2$ factors to the same dice generating function (WLOG $b(x)$).

This gives us \begin{align} a(x) &= x(1+x)(1+x+x^2) \\ &= x+2x^2+2x^3+x^4 \\ \left.\right. \\ b(x) &= x(1+x)(1+x+x^2)(1-x+x^2)^2 \\ &= x+x^3+x^4+x^5+x^6+x^8 \end{align}

Therefore, the only pair of 6-sided dice that are not normal dice, bear only positive integers, and have the same probability distribution for the sum as normal dice have faces numbered $(1,2,2,3,3,4)$ and $(1,3,4,5,6,8)$.

Answer 3

Here is another one (but maybe not as interesting of a problem) that nicely combine generating series with complex analysis to solve a problem which is located in the context of the reals. IIRC this is an example or problem in J. Bak's (very nice) complex analysis book. I don't know if this counts as unexpected though (if not let me know and I'll remove it), but I've used to find it surprising that methods like these could be used for problems that naively seems to far removed from the problem itself.

Consider the (infinite) equation system $$\sum_{k=0}^n {n\choose k}a_{n-k}b_k = a_nb_0 + {n\choose 1}a_{n-1}b_1 + \ldots + {n\choose n-1} a_1 b_{n-1} + a_0b_n = 2^n~~~\text{for}~~~n\in\mathbb{N}$$ with $a_0 = b_0 = a_1 = b_1 = 1$. Find all solutions with $a_n,b_n\geq 0$.

The binomial theorem shows that $a_n=b_n=1$ is one solution and if we did allow negative numbers then there are infinitely many solutions. Even though we are introducing two free variables ($a_n,b_n$) at every step $(n)$ it turns out that $a_n=b_n=1$ is the only solution where all $a_n,b_n$ are positive.

Proof: Assume $\{a_n,b_n\}_{n=1}^\infty$ solves the above system and introduce the exponential generating functions $A(z) = \sum_{n=0}^\infty \frac{a_nz^n}{n!}$ and $B(z) = \sum_{n=0}^\infty \frac{b_nz^n}{n!}$. The Cauchy product of the two series satisfy $$A(z)B(z) = \sum_{n=0}^\infty \left(\frac{1}{n!}\sum_{k=0}^n {n\choose k}a_k b_{n-k}\right)z^n = \sum_{n=0}^\infty \frac{2^nz^n}{n!} = e^{2z}$$ Since $a_n,b_n\geq 0$ we have $a_n,b_n\leq 2^n$ so $A$ and $B$ are entire functions. As $AB = e^{2z}$ they are also of finite order and zero-free so we must have $A(z) = e^{az + b}$ and $B(z) = e^{cz + d}$ with $a+c = 2$ and $b+d = 0$. Taking into account the initial conditions we get $b=d=0$ and $a=c=1$ so $A(z) = B(z) = e^{z} = 1 + z + \frac{z^2}{2!} + \ldots$ and it follows that $a_n = b_n \equiv 1$ is the only solution.

If we relax $a_1=b_1=1$ then the same type of derivation as above shows that all positive solutions are on the form $a_n = c^n$ with $b_n = (2-c)^n$ for some $c \in [0,2]$.

Answer 4

Here is another neat application that appeared on the Putnam exam.

Let $S_0$ be a finite set of positive integers. We define finite sets $S_1, S_2, \cdots$ of positive integers as follows: the integer $a$ is in $S_{n+1}$ if and only if exactly one of $a−1$ or $a$ is in $S_n.$ Show that there exist infinitely many integers $N$ for which $S_N = S_0 \cup \{N +a : a \in S_0\}.$.

Proof Sketch: Define $$f_0(x) = \sum_{a_i \in S_0} x^{a_i}.$$ Note that $$f_{k+1}(x) \equiv (1+x)\cdot f_k(x) \pmod 2$$ is the corresponding polynomial to $S_k$. Then we use the fact that $$(1+x)^{2^n} \equiv 1 + x^{2^n} \pmod 2$$ and the result follows.

Answer 5

In the same vein as the example of @JimmyK4542, although different.

Is it possible that the sum of the outcomes of two "flawed" dices with usual numbers $\{1,2, \cdots 6\}$ on their sides has a uniform distribution on $\{2, \cdots 12\}$ ? The answer is negative.

Proof: We should have, with evident notations

$$\tag{1}(p_1x+p_2x^2+\cdots p_6x^6)(p'_1x+p'_2x^2+\cdots p'_6x^6)=\frac{1}{11}(x^2+x^3+\cdots x^{12})$$

Factoring $x^2$, $(1)$ is equivalent to:

$$\tag{2}(p_1+p_2x+\cdots p_6x^5)(p'_1+p'_2x+\cdots p'_6x^5)=\frac{1}{11}(1+x+\cdots x^{10})$$

But this is impossible because

• on the LHS of $(2)$, we have the product of two odd degree polynomials, each one having at least one real root, whereas

• the roots of the polynomial in the RHS, which can be written under the form $\frac{1-x^{11}}{1-x}$, are the $e^{2i\pi k/11}$, k=1..10$, with no real root among them. Contradiction.

Remark: insted of "flawed dices", it is probably better to give a context of two "roulettes" with unequal sectors as represented on the graphics below: