Proof
Anders B Madsen 02 Apr 2022 13:06
Let $x,y$ be $n$-bit strings and let $x\cdot y$ denote the number of common 1-bits (cross sum of bitwise product).
For $y=0$ the claim follows straight away:
(1)\begin{align} \sum_{x=0}^{2^n-1} (-1)^0 = 2^n\,. \end{align}
Now, assume $y$ has $k$ bits set where $1 \leq k \leq n$. The number of $x$, $0 \leq x \leq 2^n-1$, that has $i$ bits in common with the $k$ 1-bits in $y$ is
(2)\begin{align} 2^{n-k}\binom{k}{i}\,. \end{align}
So, $x\cdot y$ has the value $i$ as many times as $2^{n-k}\binom{k}{i}$.
Then write the sum as
\begin{align} \sum_{x=0}^{2^n-1} (-1)^{x\cdot y} = \sum_{x\cdot y \text{ even}} (-1)^{x\cdot y} + \sum_{x\cdot y \text{ odd}} (-1)^{x\cdot y}\,. \end{align}
where we have
(4)\begin{align} \sum_{x\cdot y \text{ even}} &= 2^{n-k} \left[ \binom{k}{0} + \binom{k}{2} + \binom{k}{4} + \ldots \right] \\ \sum_{x\cdot y \text{ odd}} &= -2^{n-k} \left[ \binom{k}{1} + \binom{k}{3} + \binom{k}{5} + \ldots \right]\,. \end{align}
Finally, all we have to show is that the 'even' and 'odd' binomial coefficients sum to the same:
(5)\begin{align} \binom{k}{0} + \binom{k}{2} + \binom{k}{4} + \ldots = \binom{k}{1} + \binom{k}{3} + \binom{k}{5} + \ldots\,, \end{align}
but this follows from the binomial expansion:
(6)\begin{align} 0 = (1-1)^k = \sum_{i=0}^{k}\binom{k}{i}1^i(-1)^{k-i}\,. \end{align}