Number theory and set theory problem 
Let $A$ be a finite set. For $0\leq i\leq 2$, let $a_i$ be the number of subsets $B$ of $A$ such that 
  $$|B|\equiv i \pmod{3}.$$
  Prove that $$|a_i - a_j| \leq 1,$$ for all $0\leq i,j\leq 2$.

Firstly I assumed that $|A|=n$. Then $a_0 = {^nC_0} + {^nC_3} + {^nC_6} +\cdots$  and $a_1 = {^nC_1}+ {^nC_4}+{^nC_7}+\cdots$  and $a_2$ in a similar manner but I am unable to show the main part.
Could anyone give a hint!!
 A: Let $a_0(n),a_1(n),a_2(n)$ be given by
$$
\begin{cases}
a_0(n) = \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots\\[4pt]
a_1(n) = \binom{n}{1} + \binom{n}{4} + \binom{n}{7} + \cdots\\[4pt]
a_2(n) = \binom{n}{2} + \binom{n}{5} + \binom{n}{8} + \cdots\\
\end{cases}
$$
We want to show that for all nonnegative integers $n$, we have $|a_i(n)-a_j(n)|\le 1$, for $0 \le i < j \le  2$.

Proceed by induction on $n$.

By direct evaluation, we have
$$
\begin{cases}
a_0(0) = 1\\[4pt]
a_1(0) = 0\\[4pt]
a_2(0) = 0\\
\end{cases}
$$
so the claim holds for the base case, $n=0$.

Next, suppose the claim holds for some nonnegative integer $n$.

Then we get
\begin{align*}
a_0(n) &= \;\;\binom{n}{0}\;\;+\;\;\binom{n}{3}\;\;+\;\;\binom{n}{6}\;\;+\;\;\cdots\\[4pt]
a_1(n) &= \;\;\binom{n}{1}\;\;+\;\;\binom{n}{4}\;\;+\;\;\binom{n}{7}\;\;+\;\;\cdots\\[4pt]
\implies\;a_0(n) + a_1(n) &= {\small{\binom{n+1}{1}}}+{\small{\binom{n+1}{4}}}+ {\small{\binom{n+1}{7}}}+\;\;\cdots\\[4pt]
\implies\;a_0(n)+a_1(n) &= a_1(n+1)\\[30pt]
a_1(n) &= \;\;\binom{n}{1}\;\;+\;\;\binom{n}{4}\;\;+\;\;\binom{n}{7}\;\;+\;\;\cdots\\[4pt]
a_2(n) &= \;\;\binom{n}{2}\;\;+\;\;\binom{n}{5}\;\;+\;\;\binom{n}{8}\;\;+\;\;\cdots\\[4pt]
\implies\;a_1(n) + a_2(n) &= {\small{\binom{n+1}{2}}}+{\small{\binom{n+1}{5}}}+ {\small{\binom{n+1}{8}}}+\;\;\cdots\\[4pt]
\implies\;a_1(n)+a_2(n) &= a_2(n+1)\\[30pt]
a_2(n) &= \;\;{\phantom{\binom{n}{0}\;\;+\;\;}}\binom{n}{2}\;\;+\;\;\binom{n}{5}\;\;+\;\;\cdots\\[4pt]
a_0(n) &= \;\;\binom{n}{0}\;\;+\;\;\binom{n}{3}\;\;+\;\;\binom{n}{6}\;\;+\;\;\cdots\\[4pt]
\implies\;a_2(n) + a_0(n) &= {\small{\binom{n+1}{0}}}+{\small{\binom{n+1}{3}}}+ {\small{\binom{n+1}{6}}}+\;\;\cdots\\[4pt]
\implies\;a_2(n)+a_0(n) &= a_0(n+1)\\[4pt]
\end{align*}
Thus, we have
\begin{align*}
a_0(n)+a_1(n) &=\; a_1(n+1)
\qquad\qquad\qquad\qquad
\\[4pt]
a_1(n)+a_2(n) &=\; a_2(n+1)\\[4pt]
a_2(n)+a_0(n) &=\; a_0(n+1)\\[4pt]
\end{align*}
hence, subtracting the above equations in pairs, we get
\begin{align*}
a_2(n+1)-a_1(n+1) &=\;a_2(n)-a_0(n)
\qquad\qquad\qquad\qquad\qquad
\\[4pt]
a_0(n+1)-a_2(n+1) &=\;a_0(n)-a_1(n)\\[4pt]
a_1(n+1)-a_0(n+1) &=\;a_1(n)-a_2(n)\\[4pt]
\end{align*}
Then applying the inductive hypothesis, it follows that the claim holds for the case $n+1$.

This completes the proof.
A: Here's a simple induction proof. The claim clearly holds if $|A|=0$, so suppose $|A|>0$. Pick an element $a\in A$ and let $A':=A-\{a\}$. Let $a_i$ and $a_i'$ be the number of subsets of $A$ and $A'$, respectively, of cardinality congruent to $i$ mod $3$. As every subset of $A$ is either a subset of $A'$ or the union of a subset of $A'$ with $\{a\}$ (exclusive or), we find that
$$a_0=a_0'+a_2'\qquad a_1=a_1'+a_0'\qquad a_2=a_2'+a_1'.$$
so
$$a_0-a_1=a_2'-a_1'\qquad a_1-a_2=a_0'-a_2'\qquad a_2-a_0=a_1'-a_0',$$
and by induction we are done.
A: Hint : 
Let $j$ be a complex number different from $1$ such that $j^3 = 1$, $$a_0 + a_1j + a_2j^2 = (1+j)^n = (-1)^nj^{2n}$$ And we know if $P\in \mathbb Z [X]$ such that $P(j) = 0$ then $1+X+X^2 | P(X)$
If $n \equiv 0 ~[3]$. Then $(a_2-a_0)j^2 + (a_1-a_0)j - (-1)^n = 0$. So $$1 + X + X^2 | (a_2 - a_0)X^2 + (a_1 - a_0) X - (-1)^n$$ this is possible only if $|a_2 - a_0| = |a_1- a_0| = |- (-1)^n| = 1$.
If $n \equiv 1 ~[3]$. Then $(a_2-a_0- (-1)^n)j^2 + (a_1-a_0 )j = 0$. So $$1 + X + X^2 | (a_2 - a_0 - (-1)^n)X^2 + (a_1 - a_0) X$$ this is possible only if $|a_2 - a_0 - (-1)^n| = |a_1- a_0| = 0 \Rightarrow |a_1- a_0| = 0 \text{ and } |a_2 - a_0| = |(-1)^n| = 1$.
If $n \equiv 2 ~[3]$. Then $(a_2-a_0)j^2 + (a_1-a_0 - (-1)^n)j = 0$. So $$1 + X + X^2 | (a_2 - a_0)X^2 + (a_1 - a_0 - (-1)^n) X$$ this is possible only if $|a_2 - a_0| = |a_1- a_0  - (-1)^n| = 0 \Rightarrow |a_2- a_0| = 0 \text{ and } |a_1- a_0| = |(-1)^n| = 1$.
A: Okay here's a hint. Define the congruence class of a set to be its cardinality modulo 3. 
You can split the set of subsets of $A$ into a disjoint union of sets $B_i$ each of size 3, plus another set $E$ of size strictly less than 3. You need to choose the sets of size 3 such that each element belongs to a different congruence class. ( notice that if a set $C$ is in one of the congruence classes, then removing/adding an element to $C$ produces a set in a different congruence class)
EDIT: in case I wasn't clear, if $A=\{1,2,3,4\}$ then for example
$B_1=\{ \{1\},\{1,2\},\{1,2,3\}\}$
$B_2=\{ \{2\},\{2,3\},\{2,3,4\}\}$
$B_3=\{\{3\},\{3,4\},\{1,3,4\}\}$
$B_4=\{\{4\},\{1,4\},\{1,3,2\}\}$
$B_5=\{\{2,4\},\{1,2,4\},\{1,2,4,3\}\}$
And $E$ is the empty set.
