MathDB

For a set with

n

elements, how many subsets are there whose cardinality is respectively

\equiv 0

(mod

3

\equiv 1

(mod

3

\equiv 2

(mod

3

)? In other words, calculate

s_{i,n}= \sum_{k\equiv i \;(\text{mod} \;3)} \binom{n}{k}

for

i=0,1,2

. Your result should be strong enough to permit direct evaluation of the numbers

s_{i,n}

and to show clearly the relationship of

s_{0,n}, s_{1,n}

and

s_{2,n}

to each other for all positive integers

n

. In particular, show the relationships among these three sums for

n = 1000

Problem Statement