13th Putnam 1953

------
 
 
Problem B7

Show that we can express any irrational number α ∈ (0, 1) uniquely in the form ∑1 (-1)n+1 1/(a1a2 ... an), where ai is a strictly monotonic increasing sequence of positive integers. Find a1, a2, a3 for α = 1/√2.

 

Solution

Answer: a1 = 1, a2 = 3, a3 = 8.

Let sn be the sum of the first n terms. The terms alternate in sign and decrease in absolute value, so the odd terms of the sequence sn decrease and the even terms increase. Every odd term exceeds every even term, so the odds and the evens must each converge. But sn - sn+1 < 1/2n which tends to zero, so they tend to a common limit.

Choose an as follows. Take a1 to be the smallest integer whose inverse exceeds α. Having chosen a2n-1, take a2n to be the largest integer such that s2n < α. Having chosen a2n, take a2n+1 to be the largest integer such that s2n+1 > α.

We have to show that these choices are always possible, or, in other words, that they yield a strictly increasing sequence an. This depends on the relation 1/k - 1/k(k+1) = 1/(k+1) (*). For suppose we have just chosen a2n-1. Then we know that s2n-1 > α, but that if increased a2n-1 by 1, then s2n-1 would be < α. Hence, using (*), taking a2n = a2n-1 + 1 certainly gives s2n < α. On the other hand, if we take a2n to be sufficiently large, then s2n will be close to s2n-1 and hence exceed α (note that α is irrational so it cannot equal any sm). So the choice of a2n will exceed a2n-1. A similar argument shows that a2n+1 exceeds a2n.

So we have established that we can find a sequence an such that all the odd partial sums sn exceed α and all the even partial sums are less than α. But we have also established that sn tends to a limit, so that limit must be α. That establishes existence.

Suppose there is another expansion so that α = 1/a1 - 1/a1a2 + ... = 1/b1 - 1/b1b2 + ... . As above, we have that 1/(a1 + 1) < α < 1/a1 and also 1/(b1 + 1) < α < 1/b1. But since a1 and b1 are both integers that implies that a1 = b1. Suppose now that we have established that ai = bi for i ≤ n. Then we have that β = (-1)n a1 ... an(α - 1/a1 + 1/a1a2 - ... + (-1)n/a1...an ) = 1/an+1 - 1/an+1an+2 + ... . But we also have β = 1/bn+1 - 1/bn+1bn+2 + ... . We now argue as before that β lies between 1/(an+1 + 1) and 1/an+1 and also between 1/(bn+1 + 1) and 1/bn+1. Hence an+1 = bn+1. That establishes uniqueness.

Finally, consider α = 1/√2. We have 1/2 < 1/√2 < 1, so a1 = 1. We must pick a2 as the largest integer so that 1 - 1/a2 < 1/√2, or a2 < 2 + √2 = 3.4. So a2 = 3. We must pick a3 as the largest integer so that 1 - 1/3 + 1/3a3 > 1/√2 or 2 + 1/x > 3/√2 or x < 3√2 + 4 = 8.2. So a3 = 8.

 


 

13th Putnam 1953

© John Scholes
jscholes@kalva.demon.co.uk
5 Mar 2002