On the number of subsets of a finite set with size in different congruence class of $3$

Question

Let $A$ be a finite set. Let $0\le i \le 2$ . Let $a_i:=|\{B : B \subseteq A$ and $ |B|=i \pmod 3 \}|$ .

How to show that $|a_i-a_j|\le 1, \forall\; 0\le i,j\le 2$ ?

Answer 1

I think this should help:

Put $n=|A|$ and let $$a ={n \choose 0}+{n\choose 3}+...=a_0$$

$$b ={n \choose 1}+{n\choose 4}+... =a_1$$

$$c ={n \choose 2}+{n\choose 5}+...=a_2$$

and let $$\epsilon = -{1\over 2}+{\sqrt{3}\over 2}i\;\;\;\Longrightarrow \;\;\;\epsilon ^3=1$$

Then by binomial theorem we have:

$$ (\cos {\pi\over 3}+i\sin{\pi \over 3})^n = (1+\epsilon )^n = a+b\epsilon +c\epsilon^2$$

So we have $$\cos {\pi n\over 3} = a-{b\over 2}-{c\over 2}\;\;\;\;\;\;\;\;(1)$$

and $$\sin {\pi n\over 3} = {b\sqrt{3}\over 2}-{c\sqrt{3}\over 2}\;\;\;\;\;\;\;\;(2)$$

From $(2)$ we have $$ |b-c| = |{2\over \sqrt{3}}\sin {\pi n\over 3}|\leq |{2\over \sqrt{3}}\cdot {\sqrt{3}\over 2}| =1 \;\;\;\Longrightarrow \;\;\; |b-c|\leq 1$$

Now we have from $(1)$ three cases:

1. case: if $b=c$ then:

$$|a-b| = |\cos {\pi n\over 3}| \leq 1$$

2. case: if $b=c+1$ then:

$$|a-c| = |\cos {\pi n\over 3}+{1\over 2}| \leq 1$$

3. case: if $b=c-1$ then:

$$|a-c| = |\cos {\pi n\over 3}-{1\over 2}| \leq 1$$

Answer 2

Since the value of $a_i$ depends on $|A|$ as well as $i,$ let's define $$a_i(n):=|B:B\subseteq\{1,\dots,n\}\text{ and }|B|\equiv i\pmod3\}|.$$

One way to solve your problem is by using the binomial theorem, as in the accepted solution by ChristianF. In this way you can derive the formulas: $$a_0(n)=\frac{2^n}3+\frac23\cos\frac{n\pi}3;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$ $$a_1(n)=\frac{2^n}3-\frac13\cos\frac{n\pi}3+\frac1{\sqrt3}\sin\frac{n\pi}3;$$ $$a_2(n)=\frac{2^n}3-\frac13\cos\frac{n\pi}3-\frac1{\sqrt3}\sin\frac{n\pi}3.$$

Alternatively, start by observing that$$a_0(n+1)=a_0(n)+a_2(n),$$$$a_1(n+1)=a_1(n)+a_0(n),$$$$a_2(n+1)=a_2(n)+a_1(n),$$

the$\mod3\ $ versions of Pascal's identity $\binom{n+1}k=\binom nk+\binom n{k-1}.$ It follows that $$a_0(n+1)-a_1(n+1)=a_2(n)-a_1(n),$$ $$a_0(n+1)-a_2(n+1)=a_0(n)-a_1(n),$$ $$a_1(n+1)-a_2(n+1)=a_0(n)-a_2(n).$$ Now your inequality $|a_i(n)-a_j(n)|\le1$ is easily proved by induction on $n.$