2002 AMC 10B Problem 23

P21-25~4 minPrint

Sequences & Series Functions Compute small cases, spot the pattern, generalize Define states/recurrence and iterate

Let $\{a_k\}$ be a sequence of integers such that $a_1=1$ and $a_{m+n}=a_m+a_n+mn,$ for all positive integers $m$ and $n.$ Then $a_{12}$ is

Show solution without answering

Key insight

Put n = 1: each term is the previous one plus the next counting number. That gives 1, 3, 6, 10, ..., the triangular numbers, so a_12 = 78.

Solution

The rule works for any $m$ and $n$ , so choose values that make it simple. With $n = 1$ we can step from one term to the next.

1. Put $n = 1$ and use $a_1 = 1$ :
$a_{m+1} = a_m + a_1 + m \cdot 1 = a_m + (m + 1).$
In words: to get the next term, add the next counting number.
2. Build the terms:

$m$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
add		$+2$	$+3$	$+4$	$+5$	$+6$	$+7$	$+8$	$+9$	$+10$	$+11$	$+12$
$a_m$	$1$	$3$	$6$	$10$	$15$	$21$	$28$	$36$	$45$	$55$	$66$	$78$

3. The pattern: $a_m = 1 + 2 + \cdots + m$ . So
$a_{12} = 1 + 2 + \cdots + 12 = \frac{12 \cdot 13}{2} = 78.$

The answer is $\boxed{\textbf{(D)}\ 78}$ .

Why this works

A rule that holds "for all $m$ and $n$ " gives far more than you need. Fixing one of the letters at the smallest value turns it into a step-by-step rule, and then you just build the sequence. Recognizing $1, 3, 6, 10, \ldots$ as sums of counting numbers lets you jump straight to the $12$ th term with the formula $\frac{m(m+1)}{2}$ .

Alternative approach

Take bigger jumps. Using $m = n$ doubles the position:
$a_2 = 1 + 1 + 1 = 3, \qquad a_4 = 3 + 3 + 2 \cdot 2 = 10, \qquad a_8 = 10 + 10 + 4 \cdot 4 = 36.$
Then use $m = 8$ , $n = 4$ : $a_{12} = 36 + 10 + 8 \cdot 4 = 78$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The relation holds for every pair $(m, n)$ , so specialize to $n = 1$ :
$a_{m+1} = a_m + a_1 + m\cdot 1 = a_m + (m + 1).$
So going from index $m$ to index $m + 1$ adds $m + 1$ . Starting from $a_1 = 1$ :
$a_2 = 1 + 2 = 3,\quad a_3 = 3 + 3 = 6,\quad a_4 = 6 + 4 = 10,\quad \ldots$
In general $a_m = 1 + 2 + \cdots + m = \frac{m(m+1)}{2}$ , the triangular numbers. (Check: $\frac{(m+n)(m+n+1)}{2} - \frac{m(m+1)}{2} - \frac{n(n+1)}{2} = mn$ , so the formula really satisfies the relation.)

Therefore
$a_{12} = \frac{12 \cdot 13}{2} = 78.$

The answer is $\boxed{\textbf{(D)}\ 78}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Algebra, Chapter 16: Functions
Intermediate Counting & Probability, Chapter 10: Recursion
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)