Let f(n) be the number of 1s in the binary expression for n. Let g(m) = ±0m ±1m ±2m ... ±(2m - 1)m, where we take the + sign for km iff f(k) is even. Show that g(m) can be written in the form (-1)m ap(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) 0m + h(1) 1m + h(2) 2m + ... + h(2n - 1) (2n - 1)m = 0 for n > m and (-1)m m! 2m(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! 20, as required. For the case n > m the sum is just h(0) + h(1) + ... + h(2n - 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) = 2r - 1. Since h(2m + k) = - h(k) for k < 2m, we have that ∑0N(m+1) h(k) km+1 = - ∑0N(m) h(k) ( (k + 2m)m+1 - km+1) = - (m+1) 2m ∑0N(m) h(k) km + other terms which are zero by the induction hypothesis = -(m+1) 2m (-1)m m! 2m(m-1)/2 by induction = (-1)m+1 (m+1)! 2m(m+1)/2 as required.
Similarly, for the sum to N(n), where n > m+1, the binomial expansion of the summand ( (k + 2m)m+1 - km+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