Let $p$ be a prime number, and $n$ be an integer such that $n \geq p$. Let $a_1,…,a_n$ be arbitrary integers. Let $s_0 = 1$, and for every $k \ge 1$, let $$s_k=|\{B \subset \{1,2,…,n\} : p\mid\sum_{i \in B}a_i \text{ and }|B|=k\}|.$$ Show $$p\mid\sum_{k=0}^n(-1)^ks_k.$$
Attempt so far: $\sum_{k=0}^n(-1)^ks_k$ is the number of even subsets of $\{a_1,…,a_n\}$ that is divisible by $p$ minus the number of odd subsets that is divisible by $p$.
If we view the $a_i$s in mod $p$, then clearly, all single subset that is divisible by $p$ is $o$ mod $p$.
then the subset with $2$ elements whose sum is divisible by $p$ are inverse of each other under addition mod $p$
Best Answer
Let $\sum_{i \in \emptyset} a_i = 0$ for ease. Then, $$\sum_{k=0}^n (-1)^k s_k = \sum_{k=0}^n (-1)^k \sum_{\substack{B \subseteq [n] \\ |B| = k}} 1_{p \mid \sum_{i \in B} a_i} \equiv \sum_{k=0}^n (-1)^k \sum_{\substack{B \subseteq [n] \\ |B| = k}} \left[1-(\sum_{i \in B} a_i)^{p-1}\right] \pmod{p}.$$ Since $$\sum_{k=0}^n (-1)^k\sum_{\substack{B \subseteq [n] \\ |B| = k}} 1 = \sum_{k=0}^n (-1)^k {n \choose k} = (1+(-1))^n = 0,$$ it suffices to show $$\sum_{k=0}^n (-1)^k\sum_{\substack{B \subseteq [n] \\ |B| = k}} \sum_{(i_1,\dots,i_{p-1}) \in B^{p-1}} a_{i_1}\dots a_{i_{p-1}} = 0.$$ The left hand side is $$\sum_{k=0}^n (-1)^k\sum_{\substack{1 \le t \le p-1 \\ t \le k}} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_1\dots a_{p-1} \sum_{\substack{B \subseteq [n] \\ |B| = k}} 1_{B \ni i_1,\dots,i_{p-1}}$$ $$= \sum_{k=0}^n (-1)^k\sum_{\substack{1 \le t \le p-1 \\ t \le k}} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_{i_1}\dots a_{i_{p-1}} {n-t \choose k-t}$$ $$ = \sum_{1 \le t \le p-1} \sum_{\substack{(i_1,\dots,i_{p-1}) \in [n]^{p-1} \\ |\{i_1,\dots,i_{p-1}\}| = t}} a_{i_1}\dots a_{i_{p-1}} \sum_{t \le k \le n} (-1)^k{n-t \choose k-t}.$$ And luckily, the inner sum is $$\sum_{m=0}^{n-t} (-1)^{m+t}{n-t \choose m} = (-1)^t(1+(-1))^{n-t} = 0,$$ where the last equality used $n > t$, which is true since $t \le p-1 \le n-1 < n$.