2022 AIME II Problem 10

Attempt Problem 10 of the 2022 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2022 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

10.

Find the remainder when

\binom{\binom{3}{2}}{2} + \binom{\binom{4}{2}}{2} + \cdots + \binom{\binom{40}{2}}{2}

is divided by

1000.

Answer

Answer: 4

Concepts:combinations summation Pascal’s Triangle

Difficulty rating: 2650

Small hint:

Expand:

\binom{\binom{n}{2}}{2}

equals

\frac{(n+1)n(n-1)(n-2)}{8},

a polynomial in

n

Big hint:

That expression is

3\binom{n+1}{4};

sum it with the hockey stick identity

Solution:

Since

\binom{n}{2} = \frac{n(n-1)}{2}

and

\binom{n}{2} - 1 = \frac{(n+1)(n-2)}{2},

\begin{aligned} \binom{\binom{n}{2}}{2} \\ &= \frac{1}{2} \cdot \frac{n(n-1)}{2} \\ &\quad {}\cdot \frac{(n+1)(n-2)}{2} \\ &= \small \frac{(n+1)n(n-1)(n-2)}{8} \\ &= 3\binom{n+1}{4}. \end{aligned}

By the hockey stick identity,

\begin{aligned} \sum_{n=3}^{40} 3\binom{n+1}{4} &= 3\sum_{k=4}^{41}\binom{k}{4} \\ &= 3\binom{42}{5} \\ &= 3 \cdot 850668 \\ &= 2552004. \end{aligned}

The remainder upon division by

1000

is

4.