# Count the subsets of [n] whose sum is modulo $2^k$

Prove that for all $k \geq 1$ and $n \geq 2 ^{k-1}$, the number of subsets of $\{1,2,3\cdots n\}$ with sum congruent to $i$ mod $2^k$, equals the number with sum congruent to $i+1$ mod $2^k$, for all $0\leq i\lt2^k$.

P.S.

i do not know the math around it, but this is how the number of subsets with sum congruent to $i$ mod $2^k$ behaves for different values of $n$. The header row column values indicate the sum congruent to $i$ mod $2^k$ values. In each row, the first column indicates the value of $n$.

In this example, $k = 3,2^k=8$ and $n$ varies from $1$ to $6$

       0 1 2 3 4 5 6 7

1  1 1 0 0 0 0 0 0
2  1 1 1 1 0 0 0 0
3  1 1 1 2 1 1 1 0
4  2 2 2 2 2 2 2 2
5  4 4 4 4 4 4 4 4
6  8 8 8 8 8 8 8 8


Th table is constructed using the recurrence relation, $S_{n,i} = S_{n-1,i} + S_{n-1,(i-n) mod 2^k}$, if we assume $S_{n,i}$ is the number of subsets of $\{1,2,3 \cdots n\}$ with sum congruent to $i$ mod $2^k$. From the table, we can observe that for $n\geq4$ i.e. $2^{k-1}$, all the entries of the row are equal. And if we look closely, each entry is $2^{n - k}$

-

Hint: Prove it for $n = 2^{k-1}$ by using $$(1+x)(1+x^2)(1+x^3)...(1+x^{2^{k-1}}) \pmod{x^{2^k} - 1}$$ and showing it is equivalent to $2^{2^{k-1} - k}(1 + x + ... + x^{2^k-1})$ via plugging in the $2^{k}$th roots of unity. Then apply induction to get the desired result, $n = 2^{k-1}$ being your base case.