Weighted Binomial Coefficient Sum

This was a problem in the recent PACE AITS.

Let $\displaystyle S = {36 \choose 1}+ 4 {36 \choose 4} + 7 {36 \choose 7} +\ldots+34 {36 \choose 34}$

Now, using the property that,

$r{n\choose r} = n{n-1\choose r-1}$

We get,

$S = 36 {35\choose 0} + 36 {35\choose 3} + 36 {35\choose 6} + \ldots + 36 {35\choose 33}$

$S = 36\times\left({35\choose 0} + {35\choose 3} + \ldots + {35\choose 33}\right)$

$S = 36\times S'$

To evaluate $\displaystyle S'$ , we use complex numbers in the following way :

Consider,

$(1+x)^{35} = \sum_{r=0}^{35} {35\choose r}x^r$

Evaluate the sum at $\displaystyle x=1,w,w^2$

$2^{35} = {35\choose 0} + {35\choose 1} + {35\choose 2} + \ldots + {35\choose 35}$

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

$(1+w^2)^{35} = {35\choose 0} + {35\choose 1} w^2 + {35\choose 2} w^4 + \ldots + {35\choose 35} w^{70}$

Now, adding these 3 equations (use the fact that $\displaystyle w^{3n} = 1,n\in I$ )

Also, use the fact that $\displaystyle 1+w+w^2 = 0$

$2^{35} + (1+w)^{35} + (1+w^2)^{35} = 3 {35\choose 0} + 3 {35\choose 3} + 3 {35\choose 6} + \ldots + 3 {35\choose 33}$

$2^{35} - w^{70} - w^{35} = 3S'$

$2^{35} - (w+w^2) = 3S'$

$3S' = 2^{35} + 1$

Substituting this value back in the equation of $S$ ,

$S = 36\times S' = 12\times (3S') = 12\times (2^{35} + 1)$

$S = 3\cdot 2^{37} + 12$

Thus,

$a+b+c+d = 3+2+37+12 = \boxed{54}$

let the given sum be S=summation of {3r-2} (36C{3r-2})=summation of {(3r)(3r-1)(3r-2)(38C3r)/37 38}

now differentiating the expansion of (1+x)^38 thrice and putting successively x=1 then x=omega, x=omega^2

and adding the three equation..we get a final expression which when is divided by 3 37 38 yields the expression S.

the final S comes out to be 3*{(2)^37} + 12