CombinatorialIdentity MODBasic BasicSequence AMC10/12 Difficult
2014


Problem - 474
The number $2017$ is prime. Let $S = \sum \limits_{k=0}^{62} \dbinom{2014}{k}$. What is the remainder when $S$ is divided by $2017$?

Answer     C

First, let's simplify $\binom{2014}{k}$ as $$\begin{align*} \displaystyle\binom{2014}{k} &\displaystyle\equiv \frac{2014\times 2013\times\cdots (2014-k+1)}{k!} \\ &\equiv \displaystyle\frac{(-3)(-4)\cdots(-k-2)}{k!} \\ &\equiv (-1)^k\displaystyle\binom{k+2}{k} \\ &\equiv (-1)^k\displaystyle\binom{k+2}{2} \\ &\equiv (-1)^k\times \displaystyle\frac{(k+2)(k+1)}{2}\pmod{2017}\end{align*}$$

When $k$ is even, let $k=2m$. Then the sum of those "even" terms in the above expression equals $$\sum_{m=0}^{31} \frac{(2m+2)(2m+1)}{2}=\sum_{m=0}^{30}(2m^2 + 3m + 1)$$

When $k$ is odd, let $k=2m+1$. Then the sum of those "odd" terms above equals $$\sum_{m=0}^{30}(-1)\times\frac{(2m+3)(2m+2)}{2}=-\sum_{m=0}^{30}(2m^2 + 5n + 3)$$

Adding them together yields $$S=2\times 31^2 - 2\sum_{m=0}^{30}m + 3\times 31 + 32 - 3\times 31=\boxed{1024}$$

report an error