Full of ( summations combinations ) \binom{\text{summations}}{\text{combinations}}

The sum ( 2014 1565 ) + k = 1 333 ( k + 2013 k + 1565 ) + k = 1 48 ( k + 2346 1897 ) \binom{2014}{1565}+\sum_{k=1}^{333} \binom{k+2013}{k+1565}+\sum_{k=1}^{48} \binom{k+2346}{1897} can be expressed in the form ( x y ) \binom{x}{y} , where x x and y y are four-digit integers. Find the value of x y . x-y.


The answer is 497.

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

Ariel Gershon
May 2, 2014

I will use the Symmetry Identity a lot in this proof, so here it is for reference:

If b a 0 b \ge a \ge 0 , then ( b a ) = ( b b a ) \binom {b} {a} = \binom {b} {b-a}

Let's first simplify the first sum:

k = 1 333 ( k + 2013 k + 1565 ) = k = 1 333 ( k + 2013 448 ) = x = 2014 2346 ( x 448 ) = x = 448 2346 ( x 448 ) x = 448 2013 ( x 448 ) \sum_{k=1}^{333} \binom {k+2013} {k+1565} = \sum_{k=1}^{333} \binom {k+2013} {448} = \sum_{x=2014}^{2346} \binom {x} {448} = \sum_{x=448}^{2346} \binom {x} {448} - \sum_{x=448}^{2013} \binom {x} {448}

Now we use the "Hockey Stick Identity" which says that for b a 0 b \ge a \ge 0 , we have x = a b ( x a ) = ( b + 1 a + 1 ) \sum_{x=a}^{b} \binom {x} {a} = \binom {b+1} {a+1} I won't prove it here, but it's easy to prove by induction.

Applying this formula to the above gives us: k = 1 333 ( k + 2013 k + 1565 ) = ( 2347 449 ) ( 2014 449 ) \sum_{k=1}^{333} \binom {k+2013} {k+1565} = \binom {2347} {449} - \binom {2014} {449}

We use the Hockey Stick Identity again to simplify the second sum: k = 1 48 ( k + 2346 1897 ) = x = 2347 2394 ( x 1897 ) = x = 1897 2394 ( x 1897 ) x = 1897 2346 ( x 1897 ) = ( 2395 1898 ) ( 2347 1898 ) \sum_{k=1}^{48} \binom {k+2346} {1897} = \sum_{x=2347}^{2394} \binom {x} {1897} = \sum_{x=1897}^{2394} \binom {x} {1897} - \sum_{x=1897}^{2346} \binom {x} {1897} = \binom {2395} {1898} - \binom {2347} {1898}

Now we put everything together, and cancel things out:

( 2014 1565 ) + ( ( 2347 449 ) ( 2014 449 ) ) + ( ( 2395 1898 ) ( 2347 1898 ) ) \binom {2014} {1565} + \left( \binom {2347} {449} - \binom {2014} {449} \right) + \left( \binom {2395} {1898} - \binom {2347} {1898} \right)

= ( 2014 1565 ) + ( 2347 1898 ) ( 2014 1565 ) + ( 2395 1898 ) ( 2347 1898 ) = \binom {2014} {1565} + \binom {2347} {1898} - \binom {2014} {1565} + \binom {2395} {1898} - \binom {2347} {1898}

= ( 2395 1898 ) = \binom {2395} {1898}

Thus, x y = 497 x - y = 497

Wow!!! :D I thought only Pascal's identity can answer this problem, but now, I have learned a new thing. Thanks. :) Btw, why is it called a Hockey Stick Identity?

Jaydee Lucero - 7 years, 1 month ago

Log in to reply

There could be several possibilities for the answer. For example, if N = ( 2395 1898 ) N = { 2395 \choose 1898} , we could have ( N N 1 ) { N \choose N-1} which would give a value of x y = 1 x-y = 1 .

Can you edit the question to avoid such cases?

Calvin Lin Staff - 7 years, 1 month ago

Log in to reply

Oh, I see. And it could also be that ( 2395 1898 ) = ( 2395 2395 1898 ) = ( 2395 497 ) \binom{2395}{1898}=\binom{2395}{2395-1898}=\binom{2395}{497} , so that x y = 1898 x-y=1898 . Also, from ( N N 1 ) \binom{N}{N-1} , we could as well have ( N N ( N 1 ) ) = ( N 1 ) \binom{N}{N-(N-1)}=\binom{N}{1} , so that x y = N 1 = ( 2395 1898 ) 1 x-y=N-1=\binom{2395}{1898}-1 .

Does restricting x x and y y to four-digit numbers yield a unique solution?

Jaydee Lucero - 7 years, 1 month ago

Log in to reply

@Jaydee Lucero Well no because you can still do the N choose N-1...i think you might have to say y x 2 y\le \frac{x}{2}

Nathan Ramesh - 7 years, 1 month ago

Well, the Hockey Stick Identity does rely on Pascal's Identity :) It's called that because if you look at Pascal's Triangle, the ( x a ) \binom {x} {a} coefficients together with ( b + 1 a + 1 ) \binom {b+1} {a+1} looks like a hockey stick

Ariel Gershon - 7 years, 1 month ago

Log in to reply

Oh, nice! :D

Jaydee Lucero - 7 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...