# Does this theorem have a name?

Let P(x) be a polynomial of degree n. Let H(i) represent the number of 1's in the binary expansion of the integer i. Although reasonably easy to prove, it may seem surprising that the following identity holds:

$\sum_{i=0}^{2^{n+1}-1} (-1)^{H(i)}P(i) = 0$

This was asked here on the "Complex Projective 4-Space" blog by apgoucher.

• This question has been handled in Math.SE at least here. I have seen the result in a number theory book. My copy of that book is in my office (if not with a student), so can't check before Monday, whether the author attributes the theorem to somebody. IOW, I'm not sure that coding theory is the best tag for this. – Jyrki Lahtonen Aug 23 '13 at 18:44
• I added "coding theory" because apgoucher titled his post "Polynomials and Hamming Weights". – Ross Presser Aug 24 '13 at 19:28
• There has to be a typo in the summation. The range should be either from $0$ to $2^{n+1}-1$ or from $1$ to $2^{n+1}$. Both work, I think. – Jyrki Lahtonen Aug 26 '13 at 7:35
• You are correct, the lower bound is zero. I will fix it. – Ross Presser Aug 26 '13 at 20:41