$\usepackage{textcomp}$ $\newcommand{\Av}{\operatorname{Av}}$ $\newcommand{\oc}{\Av(3124,4312)}$ $\newcommand{\pa}[1]{\left({#1}\right)}$ $\newcommand{\ds}{\displaystyle}$

## Checker Jumping, Coin Counting, and Cap Throwing: Why Generating Functions are Magic!

#### August 28, 2013

Jay Pantone

University of Florida

[Wait 15 seconds for the page to load completely,
or the math will be messed up.]

[Navigate slides using the left and right arrow keys.]

## what are generating functions?

A generating function is a clothesline on which we hang up a sequence of numbers for display.
- Herb Wilf, Generatingfunctionology

Take an infinite sequence (usually of integers) $\mathcal{A} = (a_0, a_1, a_2, \ldots)$, and use these as the coefficients of a formal power series.

$A(x) = \ds\sum_{i \geq 0} a_ix^i = a_0 + a_1x + a_2x^2 + \cdots \in \mathbb{R}[[x]].$

## examples of generating functions

What's the generating function of the sequence $(0,0,2,1,0,0,\ldots)$ ?

$0 + 0x + 2x^2 + 1x^3 + 0x^4 + 0x^5 + \cdots =$ $2x^2 + x^3$

What's the generating function of the sequence $(1,1,1,1,1,1,\ldots)$ ?

$1 + x + x^2 + x^3 + x^4 + x^5 + \cdots =$ $\ds\frac{1}{1-x}$

What's the generating function of the sequence $(1,2,4,8,16,32,\ldots)$ ?

$1 + 2x + 4x^2 + 8x^3 + 16x^4 + 32x^5 + \cdots =$ $\ds\frac{1}{1-2x}$

## what's the point?

We don't care about convergence. All arithmetic is
done in the ring of formal power series.

We can perform many easy operations on generating functions
to get combinatorial results. Suppose we have the sequence $\mathcal{A} = \pa{a_n}_{n \geq 0}$ with generating function $A(x)$. Then:

The sequence $\pa{0, 0, a_0, a_1, a_2, \ldots}$ has generating function $x^2A(x) = a_0x^2 + a_1x^3 + a_2x^4 + \cdots.$

The sequence $\pa{n\cdot a_n}_{n \geq 0}$ has generating function $x\:A'(x) = a_1x + 2a_2x^2 + 3a_3x^3 + \cdots.$

The sequence of partial sums has generating function $\ds\frac{1}{1-x}\cdot A(x) = a_0 + (a_0+a_1)x + (a_0+a_1+a_2)x^2 + \cdots.$

## checker jumping

#### (solution due to John Conway)

lined up in a grid on one side of a line.

A checker can jump over an adjacent checker (not diagonally),
and the checker that got jumped over disappears.

to get a checker $n$ steps past the line?

## checker jumping

### $(n=1)$

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 2 checkers

## checker jumping

### $(n=2)$

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 4 checkers

## checker jumping

### $(n=3)$

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 8 checkers

## checker jumping

### $(n=4)$

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 20 checkers

## checker jumping

### $(n=5)$

Impossible!   Weird, huh?

Proof: Let $P$ be a location in the $5^{\text{th}}$ row, where we're trying to get a checker.

Label each space with the monomial $x^i$, where $i$ is
the grid-distance from the space to $P$.

## checker jumping

Let $S$ be the sum of all monomials which currently have a checker on them.

A jump can change $S$ in three ways:

• A checker can go from $x^n$ to $x^{n+2}$, setting $S := S+\pa{x^{n+2}-x^{n+1}-x^n}$.
• A checker can go from $x^{n}$ to $x^{n-2}$, setting $S := S+\pa{x^{n-2}-x^{n-1}-x^{n}}$.
• A checker can go from $x^{n}$ to $x^{n}$, setting $S := S+\pa{-x^{n-1}}$.

If we can successfully get a checker to $x^0$, then at this point, we should have
$S = x^0 + \text{[other stuff]} = 1 + \text{[other stuff]}.$

## checker jumping

Consider the $n=3$ case from earlier.

$S = x^3 + 3x^4 + 3x^5 + x^6$

$S = x^2 + x^3 + 2x^4 + 3x^5 + x^6$

$S = x^2 + x^3 + x^4 + 2x^5 + x^6$

$S = x + x^4 + 2x^5 + x^6$

$S = x + x^3 + x^4$

$S = x^0 = 1$

## checker jumping

What happens if we plug in a specific $x$-value into these polynomials?

For most $x$-values, the value of $S$ will go up and down as we jump around.

Instead, we're going to pick an $x$-value for which $S$ doesn't change when

Therefore, since we end with a value of $S=1$, we must start
with a configuration which has $S \geq 1$.

Recall that a jump toward the target changed $S$ by $S := S - x^n(1-x-x^2).$

The roots of $1-x-x^2$ are $x = \ds\frac{-1\pm\sqrt{5}}{2}$, and if we pick $\phi := \ds\frac{-1+\sqrt{5}}{2} \approx 0.62$, then jumps toward the target don't change $S$, while other jumps only decrease $S$.

Note: $\phi^2 = 1 - \phi$.

## checker jumping

If we start with a checker in every spot with the goal of reaching the $5^{\text{th}}$ level,
what is the value of our starting configuration?

The sum of the first row is $R := \phi^5 + 2(\phi^6 + \phi^7 + \cdots)$, and the sum of the $i^{\text{th}}$ row is $\phi^{i-1}\cdot R$.

## checker jumping

Hence, the starting configuration has value:

\begin{align*} \pa{\phi^5 + 2\pa{\phi^6 + \phi^7 + \cdots}}\pa{1 + \phi + \phi^2 + \cdots} &= \pa{\phi^5 + \ds\frac{2\phi^6}{1-\phi}}\pa{\ds\frac{1}{1-\phi}}\\ &= \ds\frac{\phi^5 - \phi^6 + 2\phi^6}{\pa{1-\phi}^2}\\ &= \ds\frac{\phi^5\pa{1+\phi}}{\pa{1-\phi}^2}\\ &= \ds\frac{\phi^5\pa{1+\phi}}{\phi^4}\\ &= \phi^2+\phi\\ &= 1. \end{align*}

Therefore, with any finite number of checkers, the starting configuration will have
value less than 1, making it impossible to reach the $5^{\text{th}}$ level.       $\square$