Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do we show that $(a_1+...+a_n)^2=(a_1^2+...+a_n^2)\mod 2$?

I can see that this works when there are two terms, but I have trouble visualizing the left hand expansion with infinite terms. I guess this could call for a proof by induction, but once I assume this is true for some $k$, I have no clue how to proceed for the $k+1$ case.

Just some tips or ideas would be appreciated.

share|improve this question
1  
You could simply note that $x\equiv x^2 \mod 2$. –  Alex Becker Sep 27 '12 at 0:33

3 Answers 3

up vote 3 down vote accepted

Two cases to check:

(i) The number of odd $a_i$ is even.

(ii) The number of odd $a_i$ is odd.

Both cases are straightforward. In case (i), the sum of the $a_i$ is even, as is the sum of the $a_i^2$. This is because $x^2$ is odd iff $x$ is odd. Case (ii) is similar.

More algebraically, square the left-hand side. The "cross" terms are of the form $2a_ia_j$, so are congruent to $0$ modulo $2$.

share|improve this answer
1  
took me a little to properly understand the odd and even arguments, but i think they are much more elegant than the binomial expansion method! thanks for the insight. –  MSEoris Sep 27 '12 at 1:06

Use $(\sum a_i)^2=\sum a^2_i+2\sum_{i<j} a_ia_j$.

share|improve this answer

You don’t have to worry about an infinite number of terms: that’s not allowed. You mean that you don’t know how to deal with an arbitrary finite number of terms.

You can do it by induction:

$$\begin{align*} (a_1+\ldots+a_n+a_{n+1})^2&=\Big((a_1+\ldots+a_n)+a_{n+1}\Big)^2\\\\ &=(a_1+\ldots+a_n)^2+2a_{n+1}(a_1+\ldots+a_n)+a_{n+1}^2\\\\ &\equiv a_1^2+\ldots+a_n^2+a_{n+1}^2\pmod2\;, \end{align*}$$

by the induction hypothesis that $(a_1+\ldots+a_n)^2\equiv a_1^2+\ldots+a_n^2\pmod2$, since $2a_{n+1}(a_1+\ldots+a_n)\equiv0\pmod2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.