Maths Olympiad Prep

Library / /466 of 520

Combinatorics Difficulty 4.1 AIME Find the answer

The number 20172017 is prime. Let S=k=062(2014k)S = \sum \limits_{k=0}^{62} \dbinom{2014}{k}. What is the remainder when SS is divided by 2017?2017?

Pick one

Solution

Note that 20143mod20172014\equiv -3 \mod2017. We have for k1k\ge1
(2014k)(3)(4)(5)....(2k)k!mod2017\dbinom{2014}{k}\equiv \frac{(-3)(-4)(-5)....(-2-k)}{k!}\mod 2017
(1)k(k+2k)mod2017\equiv (-1)^k\dbinom{k+2}{k} \mod 2017
Therefore
k=062(2014k)k=062(1)k(k+22)mod2017\sum \limits_{k=0}^{62} \dbinom{2014}{k}\equiv \sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2} \mod 2017
This is simply an alternating series of triangular numbers that goes like this: 13+610+1521....1-3+6-10+15-21....
After finding the first few sums of the series, it becomes apparent that
k=1n(1)k(k+22)(n+12)(n+12+1)mod2017 if n is odd\sum \limits_{k=1}^{n}(-1)^k\dbinom{k+2}{2}\equiv -\left(\frac{n+1}{2} \right) \left(\frac{n+1}{2}+1 \right) \mod 2017 \textnormal{ if n is odd}
and
k=1n(1)k(k+22)(n2+1)2mod2017 if n is even\sum \limits_{k=1}^{n}(-1)^k\dbinom{k+2}{2}\equiv \left(\frac{n}{2}+1 \right)^2 \mod 2017 \textnormal{ if n is even}
Obviously, 6262 falls in the second category, so our desired value is
(622+1)2=322=(C) 1024\left(\frac{62}{2}+1 \right)^2 = 32^2 = \boxed{\textbf{(C)}\ 1024}

Sidenote
Another way to finish, using the fact that (k+22)=1+2++(k+1)\dbinom{k+2}{2} = 1 + 2 + \dots + (k+1):
\begin{align*} \sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2} &\equiv \sum \limits_{k=1}^{63}(-1)^{k-1} (1 + 2 + \dots + k) \\ &\equiv 1 - (1+2) + (1+2+3) - (1+2+3+4) + \dots + (1 + \dots + 63) \\ &\equiv 1 + 3 + 5 + \dots + 63 \\ &\equiv \boxed{1024} \mod 2017 \end{align*}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.