The problem goes as follows:
Define the intersection of binary vectors $x,y$ to be the vector: $x*y = (x_1y_1,\ldots , x_n y_n ) $ which has 1's only where both $x$ and $y$ do. Show that $$wt(x+y) = wt(x) + wt(y)-2wt(x* y).$$ Where $wt$ is Hamming weight, defined as the number of non zero entries in the vector.
I want to show this identity then I thought of the following proof, let me know if it's ok or need some tweaking.
$$wt(x+y) = \# \text{of non 0's in (x+y)}=\#\text{of non zero in x and zero in y}+\#\text{of zero in x and non-zero in y}=wt(x)-wt(x*y)+wt(y)-wt(x*y)$$
Now obviously they are symmetric so I thought to myself it's enough to prove for the first term above.
If we subtract from $\# \text{of non zeros in x}$, $wt(x*y)$, we get $\# \text{of non zero in x and zero in y}$. If there's a $0$ in $y$ and a nonzero in $x$ then subtract from $wt(x)$ the $\# \text{ of nonzeros in x the # of nonzeros in $x*y$}$. And this justifies the claim.
Is this right, or there's another subtler justification?
Thanks.
Your reasoning is correct. You want to prove that $w(x+y)=w(x)+w(y)-2 w(x*y)$, where $w(x)$ denotes the number of 1's in the vector $x$ and $x*y := (x_1 y_1, \ldots, x_n y_n)$. The left hand side $w(x+y)$ counts the number of coordinates $i$ where exactly one of $x_i$ or $y_i$ is 1. On the right hand side, $w(x)+w(y)$ overestimates the left hand side when both $x_i$ and $y_i$ are equal to 1: these coordinates $i$ contribute 0 to the left hand side but 2 to $w(x)+w(y)$. So we need to subtract $2w(x*y)$ to get equality.