Lets analyze a smaller case: $ \{1,2,3,4,5\}$ S(0)={{},{5},{1,4},{2,3},{1,4,5},{2,3,5},{1,2,3,4},{1,2,3,4,5}} S(1)={ {1},{1,5},{2,4},{1,2,3},{2,4,5},{1,2,3,5}} S(2)={ {2},{3,4},{2,5},{1,2,4},{3,4,5},{1,2,4,5}} S(3)={ {3},{1,2},{3,5},{1,2,5},{1,3,4},{1,3,4,5}} S(4)={ {4},{1,3},{4,5},{1,3,5},{2,3,4} {2,3,4,5}} Let $ f(n)$ be the amount of all the subsets of $ \{1,2,...,n\}$ that add to a multiple of $ 5$ Let $ g(n)$ be the amount of all the subsets of $ \{1,2,...,n\}$ that do not add to a multiple of $ 5$ then $ g(n) = 2^n - f(n)$ Initial values: $ f(5) = 8$ then $ g(5) = 2^5 - 8 = 32 - 8 = 24$ Recursion: $ f(5k + 5) = 8 f(5k) + 6 g(5k)$ using that $ g(5k) = 2^{5k} - f(5k)$ to get $ f(5k + 5) = 2 f(5k) + 6\times 2^{5k}$ the formula should follows, is it ok?

But it is still difficult to find $ f(2000)$. Can you find a closed-form formula of $ f(n)$?

$ f(5m) =\frac{2^{5m} + 2^{m + 2}}{5}$

an alternative approach: Let $ \epsilon ^{5} = 1$ and $ x_i$ be the amount of subsets whose sum = $ i$ modulo $ 5$ Then $ \sum _{i = 1}^{5}\epsilon^{i}x_i = \sum_{k = 0}^{2000}\sum_{1\le a_1 < ... < a_k\le 2000}\epsilon^{a_1 + ... + a_k}$ $ (*)$ but $ f(x) = (x + \epsilon)(x + \epsilon^2)...(x + \epsilon^{2000}) = (x^5 + 1)^{400}$ the $ RHS$ of $ *$ is obviouly $ f(1)$ We obtain $ \sum _{i = 1}^{5}\epsilon^{i}x_i = 2^{400}$ combining with $ \sum _{i = 1}^{5}x_i = 2^{2000}$ We conclude $ x_5 = \frac {2^{2000} + 2^{402}}{5}$ QED

Albanian Eagle wrote: $ f(5m) =\frac{2^{5m} + 2^{m + 2}}{5}$ Why is it true, Albanian Eagle?