Difference between revisions of "2019 Mock AMC 10B Problems/Problem 25"
(Created page with "===Solution 1=== We are attempting to find the closed form for <math>S_{n, k} = \sum_{a=0}^{n} \dbinom{a}{k} \dbinom{n-a}{k}</math>. By properties of summations, this equals...") |
|||
Line 1: | Line 1: | ||
+ | ===Problem=== | ||
+ | |||
+ | Let <math>S_{n, k} = \sum_{a=0}^{n} \dbinom{a}{k}\dbinom{n-a}{k}</math>. Find the remainder when <math>\sum_{n=0}^{200} \sum_{k=0}^{200} S_{n, k}</math> is divided by <math>1000</math>. | ||
+ | |||
+ | |||
+ | <math>\textbf{(A)}\ 374 \qquad\textbf{(B)}\ 375 \qquad\textbf{(C)}\ 503 \qquad\textbf{(D)}\ 750 \qquad\textbf{(E)}\ 751</math> | ||
+ | |||
+ | |||
===Solution 1=== | ===Solution 1=== | ||
Latest revision as of 17:09, 22 September 2019
Contents
Problem
Let . Find the remainder when
is divided by
.
Solution 1
We are attempting to find the closed form for .
By properties of summations, this equals
.
Using repeated Hockey Stick Identity and your 200 IQ Math Skills, this becomes the sum of these expressions:
(This equals ) (This is our
-dimensional sum.)
All other such summations after this equal ,
,
, etc.
Thus, now the summation equals
(This is our
-dimensional sum.)
We now do this process repeatedly for a total of
times (since then we would have our original summation).
Since we need a
-dimensional sum, our closed form is
Now, we have to find by using our closed form.
It is easy to see that this equals
It is easy to see that the above summation equals
.
By geometric series, the closed form for
is
.
By Euler's, we can calculate the last three digits of
to be
.
Solution 2 (Credit to NikoIsLife)
[b]Claim 1:[/b] for all
and
.
[b]Proof:[/b] We have
\begin{align*}
\sum_{n=0}^\infty S_{n,k}x^n&=\sum_{n=0}^\infty\sum_{a=0}^n\binom ak\binom{n-a}kx^n\\
&=\left(\sum_{n=0}^\infty\binom nkx^n\right)\left(\sum_{n=0}^\infty\binom nkx^n\right)\\
&=\left(\sum_{n=0}^\infty\binom nkx^n\right)^2\\
&=\left(\sum_{n=0}^\infty\binom{n+k}kx^{n+k}\right)^2\\
&=\left(x^k(1-x)^{-k-1}\right)^2\\
&=x^{2k}(1-x)^{-2k-2}\\
&=\left(\sum_{n=0}^\infty\binom{n+2k+1}{2k+1}x^{n+2k}\right)^2\\
&=\sum_{n=0}^\infty\binom {n+1}{2k+1}x^n\\\end{align*}
This shows that for all
and
.
[rule]
[b]Claim 2:[/b]
for all positive integers
.
[b]Proof:[/b] Let where
is a positive integer. We know that
and
Therefore,
Substituting
,
[rule]
Therefore,
And, this gives us
.
Solution 3(Also Credit to NikoIsLife)
Claim 1: for all
and
.
Proof: Consider the following problem: "How many ways are there to select balls out of
?
LHS: One way to do this is first selecting the th ball, and then selecting
balls to the left of the
th ball, and
balls to the right of the
th ball.
Suppose that out of the balls, the
th one is selected. There are now
balls to the left of it, and
balls to the right of it. The number of ways to choose the balls now is
.
Therefore, summing up all possible values of , we get
possible ways.
RHS: The straightforward solution to this is simply choosing balls out of
. This gives
ways.
Finally, equating the LHS and RHS, we get .
Claim 2:
for all positive integers
.
Proof: Consider the following problem: "How many ways are there to select an odd number of balls out of ?"
LHS: One way to do this is by finding the number of ways to select ball, and then
balls, and then
balls, and so on. This gives us a total of
ways to do this.
RHS: Suppose that we have already chosen what to include among the first balls. Now, the last ball would determine the parity of the number of balls we have chosen. If we decide to choose or not to choose the last ball, the number of balls would be either odd or even.
This means, exactly half of the number of ways would give us an odd number of balls, while the other half gives us an even number of balls.
Therefore, since the number of ways to choose the balls without restrictions is , the total number of ways is
Finally, equating the LHS and RHS, we get
.
Therefore,
And, this gives us
.