Difference between revisions of "2014 AMC 12B Problems/Problem 23"

(Sidenote)
m (Solution)
Line 12: Line 12:
 
<cmath>\dbinom{2014}{k}\equiv \frac{(-3)(-4)(-5)....(-2-k)}{k!}\mod 2017</cmath>  
 
<cmath>\dbinom{2014}{k}\equiv \frac{(-3)(-4)(-5)....(-2-k)}{k!}\mod 2017</cmath>  
 
<cmath>\equiv (-1)^k\dbinom{k+2}{k} \mod 2017</cmath>
 
<cmath>\equiv (-1)^k\dbinom{k+2}{k} \mod 2017</cmath>
<cmath>\equiv (-1)^k\dbinom{k+2}{2} \mod 2017</cmath>
 
 
Therefore  
 
Therefore  
 
<cmath>\sum \limits_{k=0}^{62} \dbinom{2014}{k}\equiv \sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2} \mod 2017</cmath>
 
<cmath>\sum \limits_{k=0}^{62} \dbinom{2014}{k}\equiv \sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2} \mod 2017</cmath>
Line 24: Line 23:
  
 
===Sidenote===
 
===Sidenote===
Another way to finish, using the fact that <math>\dbinom{k+2}{2} = 1 + 2 + \dots + (k+1)</math> (Hockey-Stick Identity):
+
Another way to finish, using the fact that <math>\dbinom{k+2}{2} = 1 + 2 + \dots + (k+1)</math>:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
 
\sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2}
 
\sum \limits_{k=0}^{62}(-1)^k\dbinom{k+2}{2}

Revision as of 23:31, 31 October 2021

Problem

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?$

$\textbf{(A) }32\qquad \textbf{(B) }684\qquad \textbf{(C) }1024\qquad \textbf{(D) }1576\qquad \textbf{(E) }2016\qquad$

Solution

Note that $2014\equiv -3 \mod2017$. We have for $k\ge1$ \[\dbinom{2014}{k}\equiv \frac{(-3)(-4)(-5)....(-2-k)}{k!}\mod 2017\] \[\equiv (-1)^k\dbinom{k+2}{k} \mod 2017\] Therefore \[\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: $1-3+6-10+15-21....$ After finding the first few sums of the series, it becomes apparent that \[\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 \[\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, $62$ falls in the second category, so our desired value is \[\left(\frac{62}{2}+1 \right)^2 = 32^2 = \boxed{\textbf{(C)}\ 1024}\]

Sidenote

Another way to finish, using the fact that $\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 + 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*}

See also

2014 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 22
Followed by
Problem 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png