Prove through induction that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd I am trying to prove the following claim through induction:
Assume $A_1,\ldots,A_n$ series of Sets.
Prove that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd
My questions:


*

*The base case starts here from one or from zero?  

*Should I prove this claim in two ways? right to left and left to right? i.e do two inductions?

 A: You can start from $0$, because one can define the multiple symmetric difference by
$$
\mathop{\large\triangle}_{i=0}^0 A_i=\emptyset, \qquad
\mathop{\large\triangle}_{i=0}^{n+1} A_i=
\biggl(\mathop{\large\triangle}_{i=0}^{n} A_i\biggr)\mathbin{\triangle}A_{n+1}
$$
Here, associativity of symmetric difference is important.
Now the base step of the induction is clear: for $n=0$, we have $|\{i\mid a\in A_i\}|=0$ and $a\notin\emptyset$.
Now suppose that the statement holds for $n$ sets and set, for simplicity,
$$
B=\mathop{\large\triangle}_{i=0}^{n} A_i
$$
We have that $a\in B\mathbin{\triangle}A$ if and only if $a\in B$ or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$. This is equivalent, by the induction hypothesis, to

$|\{i\mid a\in A_i\}|$ is odd or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$.

Check the cases and you're done.
A: Base case is for $n=1$:
$$a \in A_1 \iff |\{i \in \{1\} : a \in A_i\}| = 1 \iff |\{i\in \{1\} : a \in A_i\}| \text{ is odd}$$
since $|\{i \in \{1\} : a \in A_i\}| \in \{0,1\}$.
Assume that $a \in A_1 \Delta\, \cdots \Delta\,A_n \iff |\{i \in \{1, \ldots, n\}: a \in A_i\}|$ is odd.
For $n+1$ we have
\begin{align}
a \in A_1 \Delta\, \cdots \Delta\,A_n \Delta\,A_{n+1} &\iff \vee\begin{cases} \big(a \in A_1 \Delta\, \cdots \Delta\,A_n\big)  \wedge (a \notin A_{n+1}), \\
\big(a \notin A_1 \Delta\, \cdots \Delta\,A_n\big)  \wedge (a \in A_{n+1})\end{cases}\\
&\iff \vee\begin{cases} \big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is odd}\big)  \wedge (a \notin A_{n+1}), \\
\big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is even}\big)  \wedge (a \in A_{n+1})\end{cases}\\
&\iff \vee\begin{cases} |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}, \\
|\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}\end{cases}\\
&\iff |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}|\text{ is odd}
\end{align}
