<s>[INST] 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!!
 [/INST] 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.
</s>