The parity of the sum of a multiset (of integers) and of the cardinality of the odd submultiset are equal

This is a fairly simple concept, yet surprisingly difficult [for me] to state simply.

Given a multiset of integers, $M$, of finite (but arbitrary) cardinality.

And, $S_m$ is the sum over the elements of $M$, $S_m=\Sigma M$

And, $O_m$ is a submultiset of $M$ containing only the elements of $M$ that are odd.

Is there a formal proof that shows that $parity(S_m) = parity(|O_m|)$ ?

A few years ago I mentioned to a colleague that if all he wanted to do was compute the parity of the sum of (large integer) values in a distributed data source then it would not be necessary to first collect all the values, one could just sum the sums. It then struck me that even this was not necessary as the parity of the sum would be even if the collected multiset had an even number of odd numbers, and odd otherwise.

This might not sound like much of a win, but it has a few advantages:

1. You only need to check, and keep track of, the parity of a list by flipping a bit if a new number is odd.
2. Due to the self-similar nature each distributed system needs only report whether it is itself even or odd.

Since the time this idea first sprung to mind I have periodically searched the internet for a formal proof, without success.

I know that a proof must either exist, or should be easily constructed given the following:

1. The sum of a finite number of even integers is even.

2. The sum of two integers is odd $iff$ one summand is odd, and even otherwise.

I can think of at least three, rather inelegant, informal proofs, with the simplest being:

Successive odd values can be paired together, if all pair up (even number of odd values) then the sum would be even (from 1). If one value remains unpaired then it is odd (from 2).

I would like to see an elegant, or at least formal, proof of this rather simple idea.

Solution 1:

Yes, arithmetic $\!\bmod 2\,$ shows a sum has parity = number $\rm\color{#c00}N$ of odd summands:

$$\begin{align}\bmod 2\!:\,\ \overbrace{E_{\:\!i} \equiv 0}^{\large \rm evens},\ \overbrace{O_i\equiv 1}^{\large\rm odds}\ \Rightarrow\ & E_1\!+\cdots +E_k\!+O_1+\cdots+ O_{\color{#c00}N}\\[.2em] \equiv\,\ &\ 0\,+\cdots+\ 0\ +\ 1\,\ +\cdots+\ 1\\[.2em] \equiv \,\ &\rm\: \color{#c00}N \end{align}\qquad$$

Remark $ $ To be 'formal' per you request: we used the Congruence Sum Rule multiple times above, to replace a summand by a congruent summand, viz. evens $\, E_{\:\!i}\equiv 0,\,$ and odds $\,O_i\equiv 1.\,$ Even more formally we can recast the above into a rigorous induction on the the number of summands.