Binomial Coefficients modulo 2017 2017

Algebra Level 4

Given that n = 0 62 ( 2014 n ) ( m o d 2017 ) \displaystyle \sum_{n = 0}^{62} {2014 \choose n} \pmod {2017} can be written in the form a 2 a^2 where a a is a positive integer, find a a .

2017 2017 is prime.

This is from the AMC 12B given yesterday.


The answer is 32.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Josh Rowley
Feb 20, 2014

Since 2014 is so close to 2017, we may think to write out the formula for the binomial coefficients directly ( m o d 2017 ) \pmod{2017} : ( 2014 k ) ( 3 ) × ( 4 ) × . . . × ( ( k + 2 ) ) k ! ( m o d 2017 ) \dbinom{2014}{k} \equiv \dfrac{(-3)\times(-4)\times...\times(-(k+2))}{k!} \pmod{2017} So in fact almost all of the terms will cancel out, leaving us with: ( 2014 k ) ( k + 1 ) ( k + 2 ) 2 ( m o d 2017 ) \dbinom{2014}{k} \equiv \dfrac{(k+1)(k+2)}{2} \pmod{2017} if k is even and ( 2014 k ) ( k + 1 ) ( k + 2 ) 2 ( m o d 2017 ) \dbinom{2014}{k} \equiv - \dfrac{(k+1)(k+2)}{2} \pmod{2017} if k is odd. Therefore n = 0 62 ( 2014 n ) 1 3 + 6 10 + . . . 62 × 63 2 + 63 × 64 2 ( m o d 2017 ) \displaystyle\sum_{n=0}^{62} \dbinom{2014}{n} \equiv 1-3+6-10+...-\dfrac{62 \times 63}{2}+\dfrac{63 \times 64}{2} \pmod{2017} . Considering the consecutive pairs of terms we can evaluate this by noting that it is just an arithmetic series with 31 terms, first term -2 and common difference -2. We must also remember to add on the final term 63 × 64 2 \dfrac{63 \times 64}{2} which is not in a pair. As a side note, again to evaluate all the terms except the final one, there is a beautiful proof without words here: http://www.maa.org/sites/default/files/Plaza2007-236990.pdf

However we evaluate it, we get that n = 0 62 ( 2014 n ) 1024 ( m o d 2017 ) \displaystyle\sum_{n=0}^{62} \dbinom{2014}{n} \equiv 1024 \pmod{2017} so a = 32 a = 32

Here's another way you could evaluate it (at this point it doesn't really matter how you go about it as long as you get the right answer)

Think of ( k + 1 ) ( k + 2 ) 2 \frac{(k+1)(k+2)}{2} as the sum of the first k + 1 k+1 integers. Then we have

1 ( 1 + 2 ) + ( 1 + 2 + 3 ) ( 1 + 2 + 3 + 4 ) + + ( 1 + 2 + 3 + + 63 ) 1 - (1 + 2) + (1 + 2 + 3) - (1 + 2 + 3 + 4) + \dots + (1 + 2 + 3 + \dots + 63)

2 4 6 8 62 + ( 1 + 2 + 3 + + 63 ) - 2 - 4 - 6 - 8 - \dots - 62 + (1 + 2 + 3 + \dots + 63)

1 + 3 + 5 + 7 + + 63 = 3 2 2 1 + 3 + 5 + 7 + \dots + 63 = 32^2

Michael Tong - 7 years, 3 months ago

Log in to reply

Hey man, great problem! I had a bunch of fun solving it, but I think it would be better to post the source in the solution, because anybody can look up the answer to the AMC 12B 2014. So... maybe change that? Thanks!

Finn Hulse - 7 years, 3 months ago

Oh God!

A Former Brilliant Member - 7 years, 2 months ago

Josh - I didnt quite understand your first step in the proof. If you dont mind could you please elaborate on it? Thank you very much!

Surajit Rajagopal - 7 years, 2 months ago

Log in to reply

( 2014 k ) = 2014 × 2013 × . . . × ( 2015 k ) k ! \dbinom{2014}{k} = \dfrac{2014\times2013\times...\times(2015-k)}{k!} . This is the defintion of ( a b ) \dbinom{a}{b} . But 2014 2014 2017 3 ( m o d 2017 ) 2014 \equiv 2014 - 2017 \equiv -3 \pmod{2017} and 2013 2013 2017 4 ( m o d 2017 ) 2013 \equiv 2013 - 2017 \equiv -4 \pmod{2017} And so on. Therefore the numerator of that fraction becomes 3 × 4 × 5 × . . . × ( k + 2 ) ( m o d 2017 ) -3\times-4\times-5\times...\times-(k+2) \pmod{2017} . Therefore ( 2017 k ) 3 × 4 × 5 × . . . × ( k + 2 ) k ! ( m o d 2017 ) \dbinom{2017}{k} \equiv \dfrac{-3\times-4\times-5\times...\times-(k+2)}{k!} \pmod{2017} I hope that helps. Please say if you want any further clarification

Josh Rowley - 7 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...