# Uniformly at Random

## The Fine-Wilf Theorem

The Fine-Wilf Theorem is as follows. Supppose $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ are two infinite periodic sequences with periods $p$ and $q$ respectively. If $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ agree on their first $p+q-\gcd(p,q)$ terms then the two sequences are identical.

We present here the elegant algebraic proof given as the solution to Problem 134 in Bollobas’ book The Art of Mathematics and attributed by Bollobas to Ernst Straus.

We first define formal power series $F(X) = \sum_{n \geq 0} a_n X^n$ and $G(X) = \sum_{n \geq 0} b_n X^n$. By the periodicity hypothesis, we have $F(X) = P(X)/(1-X^p)$ and $G(X) = Q(X)/(1-X^q)$ for some polynomials $P,Q$ of maximum degrees $p-1$ and $q-1$ respectively. However, since $(1-X^{\gcd(p,q)})$ divides each of $(1-X^p)$ and $(1-X^q)$, we also have

$F(X) - G(X) = [(1-X^q)P(X) - (1-X^p)Q(X)](1-X^p)^{-1}(1-X^q)^{-1} = (1-X^{\gcd(p,q)})R(X)(1-X^p)^{-1}(1-X^q)^{-1}$

where $R(X)$ is some polynomial of degree at most $p+q-\gcd(p,q)-1$. If the first $p+q-\gcd(p,q)$ coefficients of $F$ and $G$ coincide, then the first $p+q-\gcd(p,q)$ coefficients of $F(X) - G(X)$ are zero, whence the polynomial $R$ is the zero polynomial. It follows that $F(X) - G(X)$ is identically zero, so that $F$ and $G$ and hence $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ are identical, as claimed.

We should point out that several other results that we have discussed in previous posts appear as problems in the previously mentioned book by Bollobas.