Find the number of odd coefficients of the polynomial (x2 + x + 1)n.
Answer In binary n is a block of a1 1s, followed by a block of 0s, followed by a block of a2 1s, followed by a block of 0s, ... , followed by a block of ak 1s, (followed by a block of 0s). Let f(x) = (2x+2 + (-1)x+1)/3. Then the number of odd coefficients is ∏ f(ai).
Solution
Let c(n) be the number of odd coefficients. Obviously c(1) = 3. We have (x2 + x + 1)2 = x4 + x2 + 1 mod 2. Hence by a trivial induction c(2k) = 3.
It is convenient to consider the expansion of (x + 1 + 1/x)n which obviously has the same number of odd coefficients. We guess that for n = 2k - 1 and k odd, we have (x + 1 + 1/x)n = (xn + xn-1 + xn-3 + xn-4 + xn-6 + ... + x + 1 + 1/x + ... + 1/xn) mod 2 (missing out every third term), and for k even we have (x + 1 + 1/x)n = (xn + xn-1 + xn-3 + xn-4 + xn-6 + ... + x2 + 1 + 1/x2 + ... + 1/xn) mod 2 (missing out every third term for the positive powers, but including x0 and then matching negative powers).
We prove this by induction on k. It is true for k = 1 and 2. Suppose it is true for k-1 odd and k even. If n = 2k - 1, then 2k+1 - 1 = 2n+1, and (x + 1 + 1/x)2n+1 = (x + 1 + 1/x) (x + 1 + 1/x)2n = (x + 1 + 1/x) (x2 + 1 + 1/x2)n mod 2 = x(x2 + 1 + 1/x2)n + (x2 + 1 + 1/x2)n + (1/x)(x2 + 1 + 1/x2)n. By induction this is:
x2n+1 + x2n-1 + x2n-5 + x2n-7 + ... + x7 + x5 + x + 1/x3 + 1/x5 + 1/x9 + ... + 1/x2n-1
x2n + x2n-2 + x2n-6 + x2n-8 + ... + x6 + x4 + 1 + 1/x4 + 1/x6 + 1/x10 + ... + 1/x2n
x2n-1 + x2n-3 + x2n-7 + x2n-9 + ... + x5 + x3 + 1/x + 1/x5 + 1/x7 + 1/x11 + ... + 1/x2n+1
giving
x2n+1 + x2n + x2n-2 + x2n-3 + x2n-5 + x2n-6 + ... + x7 + x6 + x4 + x3 + x + 1 + 1/x + 1/x3 + 1/x4 + ... + 1/x2n + 1/x2n+1
So the result is true for k+1. In an exactly similar way, we deduce that the result is true for k+2 and hence for all k. It follows immediately that c(2k - 1) = (2k+2 + (-1)k+1)/3.
Now if n = 2k+1M + N with N < 2k, then putting K = 2k+1 to cope with the deficiencies of the browser (or maybe of my knowledge of HTML) we have (x2 + x + 1)n = (x2 + x + 1)KM(x2 + x + 1)N = (x2K + xK + 1)M(x2 + x + 1)N. But the highest power in (x2 + x + 1)N is x2N and 2N < K. So if A is the expansion of (x2K + xK + 1)M and B is the expansion of (x2 + x + 1)N, then each power in the product A times B occurs in only one way. Hence c(n) = c(M) c(N). Hence the answer given at the start of the solution.
© John Scholes
jscholes@kalva.demon.co.uk
30 Dec 2002
Last corrected/updated 30 Dec 02