Eric's binomial sum

Instead of finding out the value of $\sum_{k=1}^{10} {30\choose 3k}$ , we'll derive a general expression which can be easily done using the roots of unity.

By Binomial Theorem, we already have $(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2+\ldots + {n\choose n}x^n$

Now, first we see that the in the expression $\sum_{k=1}^{10} {30\choose 3k} = {30\choose 3}+{30\choose 6}+\ldots$ we have the $r$ (of ${n\choose r}$ ) at gaps of $3$ . That suggests us to use the cube root of unity $\omega$ .

We'll use the property that $1+\omega+\omega^2 = 0$ and $\omega^3=1$

So now we plug $1$ , $\omega$ and $\omega^2$ in $(1+x)^n$ successively to get -

$(1+1)^n = 2^n = {n\choose 0} + {n\choose 1} + {n\choose 2}+\ldots + {n\choose n}$

$(1+ \omega)^n = (-\omega^2)^n = {n\choose 0} + {n\choose 1} \omega + {n\choose 2} \omega^2+\ldots + {n\choose n} \omega^n$

$(1+\omega^2)^n = (-\omega)^n = {n\choose 0} + {n\choose 1}\omega^2 + {n\choose 2}\omega^4+\ldots + {n\choose n}\omega^{2n}$

Now, add these tree expressions to get the desired result -

$(2^n + (-\omega)^n + (-\omega^2)^n) = 3({n\choose 0} + {n\choose 1}(1+\omega+\omega^2) + {n\choose 2}(1+\omega+\omega^2)+\ldots + {n\choose n}(1+\omega+\omega^2))$

$= 3({n\choose 0} + {n\choose 3} + {n\choose 6} + \ldots)$

Hence,

${n\choose 3} + {n\choose 6} + \ldots = \frac{(2^n + (-\omega)^n + (-\omega^2)^n)}{3} - {n\choose 0}$

Thus for $n=30$ (as asked in problem), we get -

$\sum_{k=1}^{10} {30\choose 3k} = \frac{(2^{30} + (-\omega)^{30} + (-\omega^2)^{30})}{3} - 1$

$= \frac{1073741824 + \omega^{30} + \omega^{60}}{3} - 1 = \frac{1073741824+1+1}{3} - 1 = 357913941$

whose last three digits are $\boxed{941}$

(Note: here we had gaps of three so we used cube rots of unity, infact if we had binomial coeffeicients at gaps of n, then we had used nth roots of unity to get the result)

Plug this into Python:

 def fact(n):

     a=1

     b=0

     for i in range(n):

         a=a*(b+1)

         b=b+1

     return a

 def choose(m):

     return (fact(30)/(fact(m)*fact(30-m)))

 s=0

 for i in range(3, 31, 3):

     s=s+choose(i)

 print(s)