Let f(n) be the number of 1s in the binary expression for n. Let g(m) = ±0^{m} ±1^{m} ±2^{m} ... ±(2^{m} - 1)^{m}, where we take the + sign for k^{m} iff f(k) is even. Show that g(m) can be written in the form (-1)^{m} a^{p(m)} (q(m))! where a is an integer and p(x) and q(x) are polynomials.

**Solution**

Answer: a = 2, p(m) = m(m-1)/2, q(m) = m.

Put h(n) = (-1)^{f(n)}. We show that h(0) 0^{m} + h(1) 1^{m} + h(2) 2^{m} + ... + h(2^{n} - 1) (2^{n} - 1)^{m} = 0 for n > m and (-1)^{m} m! 2^{m(m-1)/2} for n = m. We use induction on m. This answers the question since the case n = m is just g(m).

For m=0 in the case n = m the sum is just h(0) = 1 which is (-1)^{0} 0! 2^{0}, as required. For the case n > m the sum is just h(0) + h(1) + ... + h(2^{n} - 1). But we always have f(2r+1) = f(2r) + 1 and hence h(2r) + h(2r+1) = 0, so the sum is zero as required.

Now assume the result is true for values ≤ m. Put N(r) = 2^{r} - 1. Since h(2^{m} + k) = - h(k) for k < 2^{m}, we have that ∑_{0}^{N(m+1)} h(k) k^{m+1} = - ∑_{0}^{N(m)} h(k) ( (k + 2^{m})^{m+1} - k^{m+1}) = - (m+1) 2^{m} ∑_{0}^{N(m)} h(k) k^{m} + other terms which are zero by the induction hypothesis = -(m+1) 2^{m} (-1)^{m} m! 2^{m(m-1)/2} by induction = (-1)^{m+1} (m+1)! 2^{m(m+1)/2} as required.

Similarly, for the sum to N(n), where n > m+1, the binomial expansion of the summand ( (k + 2^{m})^{m+1} - k^{m+1}) gives a series of terms all of which sum to zero. So the case m+1 is established.

© John Scholes

jscholes@kalva.demon.co.uk

7 Jan 2002