S0 is an arbitrary finite set of positive integers. Define Sn+1 as the set of integers k such that just one of k - 1, k is in Sn. Show that for infinitely many n, Sn is the union of S0 and a translate of S0.
Solution
We show that Sn has the required form for all sufficiently large powers of 2.
We need to establish first that if n = 2k, then all the binomial coefficients in the expansion of (a + b)n except the first and last are even. This is a simple induction on k - the result for k = 1 also allows us to deduce the result for k+1 from that for k.
Define the polynomial p0(x) as ≡ aixi, where ai = 1 if i belongs to S0 and 0 otherwise. We may consider p0(x) as a polynomial over F2, the finite field with 2 elements. Similarly, we may define pm(x) by reference to Sm. Evidently, pm+1(x) = (1 + x) pm(x). Hence pm(x) = (1 + x)m p0(x). But since we are in F2 we have (1 + x)n = 1 + xn for n = 2k. So Sn has the required form if k is sufficiently large that all elements of S0 are less than 2k.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 2001