Find the number of odd coefficients of the polynomial (x^{2} + x + 1)^{n}.

**Answer**
In binary n is a block of a_{1} 1s, followed by a block of 0s, followed by a block of a_{2} 1s, followed by a block of 0s, ... , followed by a block of a_{k} 1s, (followed by a block of 0s). Let f(x) = (2^{x+2} + (-1)^{x+1})/3. Then the number of odd coefficients is ∏ f(a_{i}).

**Solution**

Let c(n) be the number of odd coefficients. Obviously c(1) = 3. We have (x^{2} + x + 1)^{2} = x^{4} + x^{2} + 1 mod 2. Hence by a trivial induction c(2^{k}) = 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 = 2^{k} - 1 and k odd, we have (x + 1 + 1/x)^{n} = (x^{n} + x^{n-1} + x^{n-3} + x^{n-4} + x^{n-6} + ... + x + 1 + 1/x + ... + 1/x^{n}) mod 2 (missing out every third term), and for k even we have (x + 1 + 1/x)^{n} = (x^{n} + x^{n-1} + x^{n-3} + x^{n-4} + x^{n-6} + ... + x^{2} + 1 + 1/x^{2} + ... + 1/x^{n}) mod 2 (missing out every third term for the positive powers, but including x^{0} 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 = 2^{k} - 1, then 2^{k+1} - 1 = 2n+1, and (x + 1 + 1/x)^{2n+1} = (x + 1 + 1/x) (x + 1 + 1/x)^{2n} = (x + 1 + 1/x) (x^{2} + 1 + 1/x^{2})^{n} mod 2 = x(x^{2} + 1 + 1/x^{2})^{n} + (x^{2} + 1 + 1/x^{2})^{n} + (1/x)(x^{2} + 1 + 1/x^{2})^{n}. By induction this is:

xSo 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(2^{2n+1}+ x^{2n-1}+ x^{2n-5}+ x^{2n-7}+ ... + x^{7}+ x^{5}+ x + 1/x^{3}+ 1/x^{5}+ 1/x^{9}+ ... + 1/x^{2n-1}x^{2n}+ x^{2n-2}+ x^{2n-6}+ x^{2n-8}+ ... + x^{6}+ x^{4}+ 1 + 1/x^{4}+ 1/x^{6}+ 1/x^{10}+ ... + 1/x^{2n}x^{2n-1}+ x^{2n-3}+ x^{2n-7}+ x^{2n-9}+ ... + x^{5}+ x^{3}+ 1/x + 1/x^{5}+ 1/x^{7}+ 1/x^{11}+ ... + 1/x^{2n+1}giving x^{2n+1}+ x^{2n}+ x^{2n-2}+ x^{2n-3}+ x^{2n-5}+ x^{2n-6}+ ... + x^{7}+ x^{6}+ x^{4}+ x^{3}+ x + 1 + 1/x + 1/x^{3}+ 1/x^{4}+ ... + 1/x^{2n}+ 1/x^{2n+1}

Now if n = 2^{k+1}M + N with N < 2^{k}, then putting K = 2^{k+1} to cope with the deficiencies of the browser (or maybe of my knowledge of HTML) we have (x^{2} + x + 1)^{n} = (x^{2} + x + 1)^{KM}(x^{2} + x + 1)^{N} = (x^{2K} + x^{K} + 1)^{M}(x^{2} + x + 1)^{N}. But the highest power in (x^{2} + x + 1)^{N} is x^{2N} and 2N < K. So if A is the expansion of (x^{2K} + x^{K} + 1)^{M} and B is the expansion of (x^{2} + 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