Induction to prove parity

Question

Let x1,…,xn be binary variables, i.e. they can be either 0 or 1. Prove by induction that parity(x1,…,xn) = x1 ⊕⋅⋅⋅⊕ xn, where ⊕ is exclusive or. The parity function returns 1 when the number of 1s in the input is odd and 0 when the number of 1s in the input is even.

Answer 1

Checking the statement for n=1 and for n=2 is trivial.

Let's assume that
(1) $parity(x_1,…,x_n) = x_1 ⊕⋅⋅⋅⊕ x_n$
where $⊕$ denotes exclusive or. This (1) is the induction hypothesis.

Next, it's easy to see that:
(2) $parity(x_1,…,x_n, x_{n+1}) = (parity(x_1,…,x_n)) ⊕ x_{n+1}$

How do we prove that? We just check directly all the 4 cases for $x_{n+1}$ and for $parity(x_1,…,x_n)$. Each of these can be either 0 or 1 so we have 4 cases in total. We observe that the equality (2) holds true.

Now from (2), using the induction hypothesis (1), we get:

(3) $parity(x_1,…,x_{n+1}) = x_1 ⊕⋅⋅⋅⊕ x_{n+1}$

But this is exactly what we wanted to prove to complete the induction step.
Thus the induction step is now complete.