Prove that if binary words $x$ and $y$ have even weight, then so does $x+y$.

Question

I am stuck on an exercise from "A Book of Abstract Algebra" by Charles C. Pinter, and there are technically three parts to the question:

Given that the weight of a binary word $x$ is the number of $1$s in the word and is denoted by $w(x)$, prove the following:

a) If words $x$ and $y$ have even weight, so does $x+y$.

b) If words $x$ and $y$ have odd weight, then $x+y$ has even weight.

c) If word $x$ has odd and $y$ has even weight, then $x+y$ has odd weight.

Note that both $x$ and $y$ must be of the same length.

My attempt of proving these statements was along the line of using the identity $w(x+y) = d(x,y)$ where $d(x,y)$ refers to the distance between the words $x$ and $y$. I then noticed that if both $x$ and $y$ have the same parity, suppose at the $i$-th digit we have $x_i \neq y_i$, then there exists another digit $j$ such that $x_j \neq y_j$. This shows that the resulting $x+y$ has even weight. However, I cannot prove this. I just needed a hint and not the whole solution to the given problems.

---

To clarify some of the terminologies used in this post:

1. If a word $x=x_1x_2...x_n$ and a word $y=y_1y_2...y_n$, then the resulting sum $x+y$ is $z=z_1z_2...z_n$, where

$$\ z_i = \begin{cases} 0 & \text{if } a_i = b_i \\ 1 & \text{if } a_i \neq b_i \end{cases} \\$$

2. The distance $d(x,y)$ refers to the number of position in which the words $x$ and $y$ differ.

Answer 1

It is easy to show that w(a+b) = w(a) + w(b) - 2w(a&b), where the operator '&' is the bitwise AND operator. Now, w(a) and w(b) are both even, so we can express them as 2x and 2y, respectively, where x and y are non-negative integers. That gives us w(a+b) = 2x + 2y - 2w(a&b) or w(a+b) = 2(x+y-w(a&b)) that is always even. That proves (a). You can do a similar approach for (b) and (c) knowing that the sum of 2 odd numbers is even, and the sum of an odd number and an even number is an odd number.

Answer 2

Firstly, I'd like to thank everyone for their constructive replies, which enabled me to write this answer.

We define set $S_1$, $S_2$, and $S_3$ as the following:
$$S_1 := \{i \in \mathbb{N}\mid x_i \neq y_i \text{ for } i \leq n\}$$ $$S_2 := \{i \in \mathbb{N}\mid x_i \neq 0 \text{ for } i \leq n\}$$ $$S_3 := \{i \in \mathbb{N}\mid y_i \neq 0 \text{ for } i \leq n\}$$

where $x_i$ and $y_i$ are the $i$-th digit of binary words $x$ and $y$ respectively, and $n$ is the length of the words. Since $w(x+y) = d(x,y)$, where $d(x,y)$ refers to the number of positions of which the words $x$ and $y$ differ, it follows that $|S_1|=d(x,y)=w(x+y)$, $|S_2|=d(x,0)=w(x)$, and $|S_3|=d(y,0)=w(y)$. Furthermore, if there exists $k$ such that $x_k = y_k = 1$, then $k \notin S_1$. Therefore,
$$|S_1| = |S_2| + |S_3| - 2|S_2 \ \cap \ S_3|$$
From this, we can deduce:
$$\text{ a) If $2 \ \mid w(x)$ and $2 \ \mid w(y)$, then $2 \ \mid w(x+y)$. }$$ $$\text{ b) If $2 \ \nmid w(x)$ and $2 \ \nmid w(y)$, then $2 \ \mid w(x+y)$. }$$ $$\text{ c) If $2 \ \nmid w(x)$ and $2 \ \mid w(y)$, then $2 \ \nmid w(x+y)$. }$$