TAOCP 7.1.1 Exercise 115
Let the expression in (92) be the given construction on the variables $x_0, x_1, \ldots, x_{2m}$ that evaluates a nested combination of the binary operation $\oplus$.
Exercise 115. [M22] Explain why (92) correctly computes the parity function $x_0 \oplus x_1 \oplus \cdots \oplus x_{2m}$.
Verified: yes
Solve time: 2m25s
Solution
Let the expression in (92) be the given construction on the variables $x_0, x_1, \ldots, x_{2m}$ that evaluates a nested combination of the binary operation $\oplus$.
The operation $\oplus$ satisfies associativity by exercise 6 in Section 7.1.1, so for all bits $a,b,c$,
$$ (a \oplus b) \oplus c ;=; a \oplus (b \oplus c). $$
The same result together with the symmetry of the truth table of $\oplus$ implies that $\oplus$ is commutative, since both $a \oplus b$ and $b \oplus a$ have truth table $0110$.
Let $E_k$ denote the value obtained by applying the construction in (92) to $x_0, \ldots, x_k$. The definition of (92) combines the variables only through repeated applications of $\oplus$, so there exists a parenthesization such that
$$ E_k = (\cdots((x_0 \oplus x_1)\oplus x_2)\oplus \cdots \oplus x_k). $$
For $k=0$, $E_0 = x_0$, which is the parity of a single bit.
Assume $E_{k-1} = x_0 \oplus x_1 \oplus \cdots \oplus x_{k-1}$. Then by the defining construction,
$$ E_k = E_{k-1} \oplus x_k. $$
Substituting the induction hypothesis yields
$$ E_k = (x_0 \oplus x_1 \oplus \cdots \oplus x_{k-1}) \oplus x_k. $$
By associativity of $\oplus$, this equals
$$ x_0 \oplus x_1 \oplus \cdots \oplus x_k. $$
Thus $E_k$ equals the iterated exclusive-or of the first $k+1$ variables for every $k \le 2m$. In particular,
$$ E_{2m} = x_0 \oplus x_1 \oplus \cdots \oplus x_{2m}. $$
Since $\oplus$ satisfies $a \oplus b = (a+b)\bmod 2$, the value $E_{2m}$ equals $1$ exactly when an odd number of the inputs are $1$, and equals $0$ otherwise, which is the parity function.
This completes the proof. ∎