2014 AMC 12B Problem 23

The number

2017

is prime. Let

S = \sum_{k=0}^{62} \binom{2014}{k}.

What is the remainder when

S

is divided by

2017?

Show solution

Solution

Working modulo

2017,

the identity

\binom{2014}{k} \cdot k! \cdot (2014-k)! = 2014!

together with

2016 \cdot 2015 \cdots (2015-k)

\equiv (-1)^k (k+2)!

leads to

\begin{gathered} 2\binom{2014}{k} \equiv (-1)^k \\ {}\cdot (k+2)(k+1) \pmod{2017}, \end{gathered}

\binom{2014}{k} \equiv (-1)^k \binom{k+2}{2}.

Then

\begin{gathered} S \equiv \sum_{k=0}^{62} (-1)^k \binom{k+2}{2} \\ = 1 \\ {}+ \sum_{k=1}^{31}\left[\binom{2k+2}{2} - \binom{2k+1}{2}\right] \\ = 1 + \sum_{k=1}^{31}(2k+1). \end{gathered}

The remaining sum is

3 + 5 + \cdots + 63 = 1023,

S \equiv 1 + 1023

= 1024 \pmod{2017}.

Thus, the correct answer is C.