Let $S={1, 2, 3, 4, ....., 2070}$ find the number of subsets of $S$ whose sum of elements in $S$ is divisible by 9 
Let $S={1, 2, 3, 4, ....., 2070}$ find the number of subsets of $S$ whose sum of elements in $S$ is divisible by 9  

In the expression $$f(x)=(1+x)(1+x^2)......(1+x^{2070})$$ 
Terms of the form $x^{9k}$ will be the subsets divisible by 9. I am not able to proceed from here.
 A: In general, if $f$ is a polynomial, and $\zeta=e^{i2\pi/n}$ is a primitive $n^{th}$ root of unity, then $\frac1n\sum_{k=0}^{n-1}f(\zeta^k)$ is equal to the sum of the coefficients of powers of $x^{n}$. In our case, let $\zeta=e^{i2\pi/9}$. The periodic nature of the powers of $\zeta$ implies
$$
f(\zeta^k)=\Big((1+\zeta)(1+\zeta^2)\cdots(1+\zeta^9)\Big)^{230}\tag 1
$$
To proceed, we use this lemma.

Lemma: If $\omega$ is a primitive $n^{th}$ root of unity, and $n$ is odd, then $$(1+\omega)(1+\omega^2)\cdots(1+\omega^n)=2.$$

Proof: It is well known that the distinct roots of the polynomial $x^n-1$ are exactly $\omega^k$, for $k=0,1,\dots,n-1$. Therefore, $x^n-1$ factors as
$$
x^n-1=(x-1)(x-\omega)(x-\omega^2)\cdots(x-\omega^{n-1})
$$
Conclude by setting $x=-1$. $\square$

Back to the problem at hand, $\zeta,\zeta^2,\zeta^4,\zeta^5,\zeta^7,\zeta^8$ are all primitive $9^{th}$ roots of unity, so applying the Lemma to $(1)$ implies
$$
f(\zeta^k)=2^{230},\qquad k\in \{1,2,4,5,7,8\}
$$
However, for $k=3,6$, $\zeta^k$ is a primitive third root of unity, and we instead have
$$
f(\zeta^3)=f(\zeta^6)=\Big((1+\zeta^3)(1+\zeta^6)(1+\zeta^9)\Big)^{690}=2^{690}
$$
Finally, we obviously have $f(\zeta^0)=f(1)=2^{2070}$. Putting this all together, we get
$$
\text{sum of coefficients of $x^{9k}$}=\frac19\sum_{k=0}^{9-1}f(\zeta^k)=\frac19\Big(2^{2070}+2\cdot 2^{690}+6\cdot 2^{230}\Big)
$$
