Ex7 2
$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.2}$
Prove Equation 7.1:
(1)\begin{align} \sum_{x=0}^{2^n-1} (-1)^{x \cdot y} = \left\{\begin{array}{l}2^n \mbox{ if $y = 0$}\\ 0 \mbox{ otherwise.}\end{array}\right. \end{align}
page revision: 0, last edited: 18 Nov 2012 19:30
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)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)So, $x\cdot y$ has the value $i$ as many times as $2^{n-k}\binom{k}{i}$.
(3)Then write the sum as
where we have
(4)Finally, all we have to show is that the 'even' and 'odd' binomial coefficients sum to the same:
(5)but this follows from the binomial expansion:
(6)