# Sylvester's Problem, A Second Look

James Joseph Sylvester was one the greatest British mathematicians of the 19th century. He was known for his absentmindedness and poor memory; on one occasion he even denied the truth of one of his own theorems. Still, he never forgot his origins. E.g., he was precluded from obtaining a Cambridge degree because it required to state his allegiance to the Church of England which he - being Jewish - refused to do.

In 1884 Sylvester submitted to the *Educational Times* the following problem:

A man possess a large quantity of stamps of only two denominations:

I've treated a more general problem

Let p and q be two mutually prime integers greater than 1. What is the largest number that could not be expressed as a linear combination

elsewhere. The solution was based on the observation that the union of the arithmetic sequences

$f_0 = \{0 + 0, 0 + q, 0 + 2q, 0 + 3q, \ldots\}$

$f_1 = \{p + 0, p + q, p + 2q, p + 3q, \ldots\}$

$f_2 = \{2p + 0, 2p + q, 2p + 2q, 2p + 3q, \ldots\}$

$f_3 = \{3p + 0, 3p + q, 3p + 2q, 3p + 3q, \ldots\}$

$\ldots$

$f_{q-1} = \{(q-1)p + 0, (q-1)p + q, (q-1)p + 2q, (q-1)p + 3q, \ldots\}.$

covers the entire set of positive integers with some gaps at the beginning. (The sequence f_{k} consists of quantities that can be paid with k $p$-stamps and a number of $q$-stamps.) The sequences consist of the coefficients of the generating function

$\displaystyle f(x) = \frac{1}{1-x^{q}}(1+x^p +x^{2p} +\ldots +x^{(q-1)p}) = \frac{1-x^{pq}}{(1-x^p)(1-x^q)}.$

On the other hand, the generating function of all the nonnegative integers is simply

$\displaystyle g(x) = 1+x+x^2+x^3+\ldots = \frac{1}{1-x}.$

The difference of the two conceals the answer to Sylvester's problem: what quantity could not be represented by the stamps of two denominations.

$\displaystyle g(x) - f(x) = \frac{1}{1-x} - \frac{1-x^{pq}}{(1-x^p)(1-x^q)} = \frac{(1-x^p)(1-x^q) - (1-x)(1-x^{pq})}{(1-x)(1-x^p)(1-x^q)}.$

Since sequence $f_k$ cover the entire set of positive integers with only some gaps at the beginning, this expression is finite, i.e., a polynomial. The degree of this polynomial is exactly the highest amount that could not be paid with $p$- and $q$-stamps; it is found from

$(pq + 1) - (p + q + 1) = pq - p - q,$

which is the answer to Sylvester's problem.

The representation of the solution with generating function makes it easy to answer an additional question: what is the number of the amounts that could not be paid with $p$- and $q$-stamps? This number is equal to the number of nonzero coefficients in the polynomial. Since the polynomial is a finite part of the geometric series $\displaystyle g(x) = 1+x+x^2+x^3+\ldots = \frac{1}{1-x},$ all of its nonzero coefficients equal 1. Their number could be found by substituting $x=1$; however, since the polynomial is represented rather implicitly, the way to find its value at $x=1$ is via L'Hôpital's Rule. It so happens that the rule needs to be applied three times. The third derivative of the numerator at $x=1$ comes out to be $-3pq(pq-p-q+1)$, and that of the denominator $-6ab$. Thus the value of the polynomial is the quotient of the two:

$(pq -p -q+1)/2.$

### References

- M. Erickson,
*Beautiful Mathematics*, MAA, 2011

### Generating Functions

- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

62816457 |