Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad. November 29th, 2005

Problem: (1989 USAMO – #1) For each positive integer , let

Find, with proof, integers such that and .

Solution: Well let's start with the first condition - . We claim that

.

Consider writing as sum of the following sequences:

...
.

Notice that appears times, appears times, and more generally appears times. Then we can say

as claimed. Also, save the fact that .

So then .

Now, using , we substitute into the equation to get

.

But recall that and remember the fact we saved back up there, so our final equation becomes

.

So .

Thus our final answer is . QED.

--------------------

Comment: This was back in 1989, when the USAMO was a one-day, hour test with five problems. Not until 1996 did it become a two-day test.

--------------------

Practice Problem #1: Do the problem again with and instead, to fully understand the solution.

Practice Problem #2: Show that for all positive integers .

2 Responses to “Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad.”

1. QC Says:

2. U_n + n = T_{n+1} – 1 = T_n + S_{n+1} – 1, and the problem is to show that this is always

2. QC Says:

I keep getting cut off. X.x ln(n+1) > S_{n+1} – 1 by integrals. Q.E.D. =P