2014 AMC 12B Problem 23

Attempt Problem 23 of the 2014 AMC 12B below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2014 AMC 12B solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

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?

32

684

1024

1576

2016

Answer: C

Concepts:combinations modular arithmetic telescoping

Difficulty rating: 2560

Small hint:

Modulo

2017,

reduce

\binom{2014}{k}

using

2016 \equiv -1,

2015 \equiv -2,

and so on

Big hint:

This gives

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

and the alternating sum telescopes

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}

so

\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,

so

S \equiv 1 + 1023

= 1024 \pmod{2017}.

Thus, the correct answer is C.

Problem 23 in other years