# Unexpected Proofs Using Generating Functions

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.

• [+1] Very interesting. Can you give an indication about the original source ? Btw, are there "Collected Works" of Erdös, besides the excellent "Proofs from the Book" (amazon.fr/Proofs-Book-Martin-Aigner/dp/3662442043)? – Jean Marie Dec 31 '16 at 10:13
• Looking at the answers, I'm quite unsure as to what constitutes "unexpected." So, as a comment, I just mention MSE 1592140 in which (e)gfs were used to answer the question, What is the probability that the product of $n$ rolls is a square? – Benjamin Dickman Dec 31 '16 at 10:50
• @JeanMarie: The result is given in the following paper which I discovered almost by accident: renyi.hu/~p_erdos/1974-24.pdf. As for "Collected Works," I do not know of any but I hope someone gets to it soon. It would be very cool to have. EDIT: Actually, this site claims to have most of the papers written by him: renyi.hu/~p_erdos – Sandeep Silwal Dec 31 '16 at 16:15
• Thank you very much for these informations. – Jean Marie Dec 31 '16 at 18:35
• @JeanMarie . Erdos is a co-author on more published papers that have multiple authors than anyone else in history. Collecting all of them would be quite a feat. – DanielWainfleet Jan 1 '17 at 3:36

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)$.

• That seems like something you'd totally expect to have a proof by generating functions. – user2357112 Dec 31 '16 at 10:29
• [+1] interesting ! I knew a similar problem that I have just written as another answer. – Jean Marie Dec 31 '16 at 10:45

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

• This is a good example, I was about to write this up myself. As a sidenote it is possible to find covering systems (which has overlap) with all bases being different (which was surprising to me the first time I saw it), see e.g. en.wikipedia.org/wiki/Covering_system – Winther Dec 31 '16 at 2:22
• @Winther Thank you for the wikipedia link. After few more searches, I found that this question provides the solution to the problem in my answer. – i707107 Dec 31 '16 at 2:32

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]$.

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: 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.