number of $\lbrace 1,2,...,53 \rbrace$ subsets with member summation divisible by $3$ In $\lbrace 1,2,3,...,53 \rbrace$ how many subsections do we have with this condition:
the summation of subset members must be divisible by $3$.

for example $\lbrace 1,2 \rbrace$ & $\lbrace 1,2,3,4,5 \rbrace$ count.
 A: From the $8$ subsets of $[3]=\{1,2,3\}$ four have sum $0$ mod $3$, and $2$ each have sum $1$ or $2$ mod $3$. Denote by $p_m$ the probability that a random subset of $[3m]$ has sum $0$ mod $3$. Then $p_0=1$, and the first sentence of this answer  implies
$$p_{m+1}={1\over 2}p_m+{1\over4}(1-p_m)\ .$$
According to the Master Theorem the solution to this difference equation is
$$p_m={1\over3}+{2\over3}4^{-m}\ .$$
In particular the probability that a random subset of $[54]$ has sum $0$ mod $3$ is given by $p_{18}={1\over3}+{2\over3}4^{-18}$. The analogous probability for a subset of $[53]$ is the same. From this we can conclude that there are 
$$2^{53}\left({1\over3}+{2\over3}4^{-18}\right)={1\over3}\bigl(2^{53}+2^{18}\bigr)=3\,002\,399\,751\,667\,712$$
admissible subsets of $[53]$.
A: 3002399751667712
Computation in Maple:
F := proc(n,k)
        options remember;
        if n=1 then
                if k=0 or k=1 then
                        1
                else
                        0
                fi
        else
                F(n-1, k) + F(n-1, k-n mod 3)
        fi
end: F(53,0);
It is also possible to do this by hand. Say that $F(m)$ is the number of such subsets of $\{1,\ldots,3m\}$. Now find a recurrence relation for $F(m)$. Then compute $F(51/3)$. The final answer is then $2^{51} + F(51/3)$ because each subset of $\{1,\ldots,51\}$ can be extended in 2 or 1 ways to a corresponding subset of $\{1,\ldots,53\}$, depending on whether that subset has a sum congruent to $0$ mod 3 or not.
A: The generating function for these is
$$\prod_{q=1}^{53} (1+z^q)$$
and with $\zeta = \exp(2\pi i/3)$ we obtain for the answer
$$\frac{1}{3} \sum_{p=0}^2 \prod_{q=1}^{53} (1+\zeta^{pq})
= \frac{1}{3} 2^{53}
+ \frac{1}{3} \prod_{q=1}^{53} (1+\zeta^{q})
+ \frac{1}{3} \prod_{q=1}^{53} (1+\zeta^{2q}).$$
Now since $(1+\zeta)(1+\zeta^2)(1+\zeta^3)= (2+\zeta+\zeta^2) \times 2
= 2$ this becomes
$$\frac{1}{3} 2^{53}
+ \frac{1}{3} 2^{17} (1+\zeta)(1+\zeta^2)
+ \frac{1}{3} 2^{17} (1+\zeta^2)(1+\zeta)
= \frac{1}{3} 2^{53} + \frac{2}{3} 2^{17}
\\ = 3002399751667712.$$
