Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2019 Mock AMC 10B Problems/Problem 25

Problem

Let $S_{n, k} = \sum_{a=0}^{n} \dbinom{a}{k}\dbinom{n-a}{k}$. Find the remainder when $\sum_{n=0}^{200} \sum_{k=0}^{200} S_{n, k}$ is divided by $1000$.


$\textbf{(A)}\ 374 \qquad\textbf{(B)}\ 375 \qquad\textbf{(C)}\ 503 \qquad\textbf{(D)}\ 750 \qquad\textbf{(E)}\ 751$


Solution 1

We are attempting to find the closed form for $S_{n, k} = \sum_{a=0}^{n} \dbinom{a}{k} \dbinom{n-a}{k}$. By properties of summations, this equals $\dbinom{0}{k} \dbinom{n}{k} + \dbinom{1}{k} \dbinom{n-1}{k} + \dbinom{2}{k} \dbinom{n-2}{k} + \dbinom{3}{k} \dbinom{n-3}{k} + … + \dbinom{n}{k} \dbinom{0}{k}$. Using repeated Hockey Stick Identity and your 200 IQ Math Skills, this becomes the sum of these expressions: $\dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \dbinom{k+3}{k} + ... + \dbinom{n-k}{k} = \dbinom{n-k+1}{k+1}$ $\dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \dbinom{k+3}{k} + ... + \dbinom{n-k-1}{k} = \dbinom{n-k}{k+1}$ $\dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \dbinom{k+3}{k} + ... + \dbinom{n-k-2}{k} = \dbinom{n-k-1}{k+1}$ $...$ $\dbinom{k}{k} = \dbinom{k+1}{k+1}$

(This equals $\dbinom{n-k+2}{k+2}$) (This is our $1$-dimensional sum.)

All other such summations after this equal $\dbinom{n-k+1}{k+2}$, $\dbinom{n-k}{k+2}$, $\dbinom{n-k-1}{k+2}$, etc. Thus, now the summation equals $\dbinom{n-k+3}{k+3}$ (This is our $2$-dimensional sum.) We now do this process repeatedly for a total of $k$ times (since then we would have our original summation). Since we need a $k$-dimensional sum, our closed form is $\dbinom{n-k+k+1}{k+k+1} = \boxed{\dbinom{n+1}{2k+1}}$

Now, we have to find $\sum_{n=0}^{200} \sum_{k=0}^{200} S_{n, k}$ by using our closed form.

It is easy to see that this equals \[\dbinom{201}{1} + \dbinom{201}{3} + \dbinom{201}{5} + \dbinom{201}{7} + \dbinom{201}{9} + ... + \dbinom{201}{201}\]\[+\]\[\dbinom{200}{1} + \dbinom{200}{3} + \dbinom{200}{5} + \dbinom{200}{7} + \dbinom{200}{9} + ... + \dbinom{200}{199}\]\[+\]\[\dbinom{199}{1} + \dbinom{199}{3} + \dbinom{199}{5} + \dbinom{199}{7} + \dbinom{199}{9} + ... + \dbinom{199}{199}\]\[+\]\[\dbinom{198}{1} + \dbinom{198}{3} + \dbinom{198}{5} + \dbinom{198}{7} + \dbinom{198}{9} + ... + \dbinom{198}{197}\]\[+\]\[...\]\[+\]\[\dbinom{1}{1}\]\[+\]It is easy to see that the above summation equals $2^{200} + 2^{199} + 2^{198} + 2^{197} + ... + 2^{0}$. By geometric series, the closed form for $2^{200} + 2^{199} + 2^{198} + 2^{197} + ... + 2^{0}$ is $2^{201} - 1$. By Euler's, we can calculate the last three digits of $2^{201} - 1$ to be $\boxed{751}$.

Solution 2 (Credit to NikoIsLife)

[b]Claim 1:[/b] $S_{n,k}=\binom{n+1}{2k+1}$ for all $n$ and $k$.

[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 $S_{n,k}=\binom{n+1}{2k+1}$ for all $n$ and $k$. [rule] [b]Claim 2:[/b] $\sum_{k=0}^\infty\binom n{2k+1}=2^{n-1}$ for all positive integers $n$.

[b]Proof:[/b] Let $P(x)=\sum_{k=0}^\infty\binom nkx^k$ where $n$ is a positive integer. We know that \[P(x)=(1+x)^n\] and \[P(-x)=(1-x)^n\] Therefore, \[\frac{P(x)-P(-x)}2=\sum_{k=0}^\infty\binom n{2k+1}x^{2k+1}\] Substituting $x=1$, \[\frac{P(1)-P(-1)}2=\sum_{k=0}^\infty\binom n{2k+1}\] \[2^{n-1}=\sum_{k=0}^\infty\binom n{2k+1}\] [rule] Therefore, \[\sum_{n=0}^{200}\sum_{k=0}^{200}S_{n,k}=\sum_{n=0}^{200}\sum_{k=0}^\infty\binom{n+1}{2k+1}=\sum_{n=0}^{200}2^n=2^{201}-1\] And, this gives us $2^{201}-1\equiv\boxed{751}\pmod{1000}$.

Solution 3(Also Credit to NikoIsLife)

Claim 1: $S_{n,k}=\binom{n+1}{2k+1}$ for all $n$ and $k$.

Proof: Consider the following problem: "How many ways are there to select $2k+1$ balls out of $n+1$?

LHS: One way to do this is first selecting the $(k+1)$th ball, and then selecting $k$ balls to the left of the $(k+1)$th ball, and $k$ balls to the right of the $(k+1)$th ball.

Suppose that out of the $n+1$ balls, the $(a+1)$th one is selected. There are now $a$ balls to the left of it, and $n-a$ balls to the right of it. The number of ways to choose the balls now is $\binom ak\binom{n-a}k$.

Therefore, summing up all possible values of $a$, we get \[\sum_{a=0}^n\binom ak\binom{n-a}k=S_{n,k}\]possible ways.

RHS: The straightforward solution to this is simply choosing $2k+1$ balls out of $n+1$. This gives $\binom{n+1}{2k+1}$ ways.

Finally, equating the LHS and RHS, we get $S_{n,k}=\binom{n+1}{2k+1}$. Claim 2: $\sum_{k=0}^\infty\binom n{2k+1}=2^{n-1}$ for all positive integers $n$.

Proof: Consider the following problem: "How many ways are there to select an odd number of balls out of $n$?"

LHS: One way to do this is by finding the number of ways to select $1$ ball, and then $3$ balls, and then $5$ balls, and so on. This gives us a total of \[\sum_{k=0}^\infty\binom n{2k+1}\]ways to do this.

RHS: Suppose that we have already chosen what to include among the first $n-1$ 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 $2^n$, the total number of ways is \[\frac12\cdot2^n=2^{n-1}\] Finally, equating the LHS and RHS, we get $\sum_{k=0}^\infty\binom n{2k+1}=2^{n-1}$. Therefore, \[\sum_{n=0}^{200}\sum_{k=0}^{200}S_{n,k}=\sum_{n=0}^{200}\sum_{k=0}^\infty\binom{n+1}{2k+1}=\sum_{n=0}^{200}2^n=2^{201}-1\]And, this gives us $2^{201}-1\equiv\boxed{751}\pmod{1000}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_Mock_AMC_10B_Problems/Problem_25&oldid=109921"