2019 Mock AMC 10B Problems/Problem 25
Contents
[hide]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
[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 .