TJUSAMO07 Practice #1: Entering the World of Proofs

Haitao Mao and Jacob Steinhardt

Welcome to TJUSAMO 2007. The purpose of the TJUSAMOs is to prepare you for the USAMO,
the intermediate step between the AIME and the MOP, as well as mathematical proofs in general.
However, simply attending will not help you dramatically. Anyone who realistically wishes to get
better at this should put in significant time outside of the practices working through the problem
sets and other Olympiad problems. If you can solve or understand the solution to most, if not
every problem in our problem sets, you will greatly improve. TJUSAMO is a serious endeavor, and
everyone attending is expected to take it seriously as well. This means not fooling around during
these practices, which is defined here as not doing or thinking about math. TJ VMT derives both
pride and future success directly from the number of people that make MOP each year. Please put
in effort and do not disrupt the education of your fellow Mathletes.

If you are new here, you may be wondering what exactly the USAMO is. It is a 2-day, 4.5-
hour per day, 3-question per day, proof-based math contest where your score for each problem is an
integer from 0 to 7, inclusive. As for the problems, each day has one medium, one hard, and one
dangerous problem. When we say USAMO #1/#4 difficulty, do not think this means easy. Also, a
lot of non-standard knowledge is required for proofs, much of which we will teach you right here at
TJUSAMO. As for the scoring, the median value is usually in the teens. Overestimating scores is
common, as partial credit is not easily gained. A 1 is awarded for useful insight into the problem, a
2 for solving half the problem or finding the key step, a 6 is awarded if the problem is correct with
a slight error, and a 7 if the problem is perfect. 3-5’s are for solving 70-90% of the problem, and
are rarely given. For sophomores and juniors, a score of approximately 22 points (3+ problems) is
the cutoff for MOP. For seniors, scores of approximately 27 points (4 problems) are the cutoff. For
freshmen, a 10 (1.5 problems) is almost always sufficient. Thus, if you are a freshman, you should
be trying as hard as possible to make the USAMO, which is achieved by scoring approximately
an 8 on the AIME. Sophomores also have the advantage of an AIME cutoff of about 8. Juniors
and seniors both need USAMO indices (10*AIME + AMC) of about 220 points. If you are not
confident that you can do this, you should practice for the AIME as well. Do so by practicing
countless mid-AIME level short answer problems, as the medium difficulty AIME problems are
generally the ones that decide who makes the cutoff. Note that practicing proofs will help your
short-answer contest performance, but the converse is not necesarily true.

MOP stands for Math Olympiad Program. Its format is similar to the TJUSAMO, except it
is 3 weeks long from around the second week of June (right after ARML) to the beginning of July,
and is obviously much more fun and intense. Many TJUSAMO topics and questions come from
MOP, since both of us have exclusive content from the lectures there. Did I mention that freshmen
have their own special group, called Red MOP, that only requires 1.5 problems as opposed to 3-4
on the USAMO? This means you should try as hard as possible to make the USAMO! Although
MOP is difficult to get into (top30 overall + next25 freshman in the whole country), there are
other reasons you should practice proofs. Proofs are a more mature form of mathematics than
short answer problems. Proofs will enhance your problem solving skills. Also, a lot of math you
will encounter later in life will involve proofs, so it’s best that you start now.

Now that introductions are finished, onto the actual lecture:

1
1 Proofs
The main purpose of a proof is to convince the reader that you are right. As a general guideline,
you want to assume that your reader catches all mistakes, knows only what he should know, and
wants to give you the lowest score possible but still adhere to his rubric. So what exactly should
go into a proof, and how do we go about writing one? The following are necessary points of style
that should go in every formal proof:

1. It might be helpful to make a brief scratch-outline of your proof to give yourself a general
sense of what order to write in and organize your proof. This will also help prevent leaving
out a step.

2. If the problem asks for an answer, begin by stating your answer or claim, then proceed to
prove it.

3. If you need to prove something separate from your main proof, write a lemma at the beginning
or end of your main proof. A lemma is a helper theorem which is composed of a claim and
its proof. Do not leave lemmas unproved.

4. Explain each big step you take.

5. Make it clear when you are using a special technique, such as induction, contradiction, WOP,
etc., and note when you are done using the technique.

6. Be sure to state your base case and inductive step in any induction, and end with ”the
induction is complete.”

7. When citing theorems, call them by name if they have one, or say they are well-known if not,
and if you have any doubt whether a grader will know the theorem, be sure to write what
the theorem states.

8. Concise is better, but don’t leave out steps. However, leaving out trivial algebraic manipula-
tions is OK, as long as a reader can follow it easily.

9. Do not be verbose. If you find a way to say something in a more comprehendable way, do so.

10. If you aren’t very experienced, assume that something isn’t obvious unless you can prove it
in one line.

11. If you have any doubt over whether something is obvious, prove it explicitly. If this is taking
a while, then it’s not obvious. Instead, it usually falls under the category of ”intuitive.”

12. Scratch-work/BSed solutions are less likely to get points than neat pages with possible ap-
proaches, ideas, progress, partial solutions, etc.

13. Proofs should contain sentences. You should not use mathematical symbols in place of words
when writing sentences. Readers have two modes: math mode and english mode. Try to
reduce the number of times they have to switch modes, but don’t worry excessively about
this. For example, you should not be saying that the square of a positive integer ≥ the integer.
Instead, type out ”greater than.”

14. Make a habit of writing in the first person plural form (i.e. we, our). This will help to involve
the reader in your proof.

2
2 Techniques
The following are basic techniques that you should be able to readily implement on Olympiads.
The best way to be able to do this is practice.

1. Induction: Prove it is true for some small case (usually n = 1), then prove it is true for k + 1
if it is true for k. This proves it is true for all integers greater than n as well.

2. Contradiction: Assume the statement is not true, then show that something terrible hap-
pens. This can take some getting used to, but it is an extremely powerful technique because
assuming the contrary gives you an entirely new piece of information to use.

3. WOP (Well Ordering Principle): This in a way combines both induction and contradiction.
To prove something, assume the contrary for some least n. Then show it is also false for n − 1.
This is obviously a contradiction, so the original statement must be true.

2.1 Induction
n(n+1)
Here is an example of induction to prove that the sum of the first n natural numbers is 2 .

For n = 1, the formula is quite clearly true.

Now assume
(n − 1)n
1 + 2 + 3 + . . . + (n − 1) =
2

Then
(n − 1)n n(n + 1)
1 + 2 + 3 + . . . + (n − 1) + n = +n=
2 2
so our induction is complete and we are done.
n(n+1)(2n+1)
Excercise: Prove that the sum of the first n squares is 6 .

2.2 Contradiction
“Reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest
weapons. It is a far finer gambit than any chess gambit: a chess player may offer the
sacrifice of a pawn or even a piece, but a mathematician offers the game.”
-G. H. Hardy, q.f. Geometry Revisited, Coxeter and Greitzer

Here is an example of using contradiction to show that there are infinitely many primes:

Assume for the sake of contradiction that there are only finitely many primes, p1 , p2 , . . . , pn . Then
p1 p2 p3 . . . pn + 1 has no prime factors, a clear contradiction, so we are done.

Excercise 1: Prove that n, 2n − 1, and 2n + 1 are relatively prime (Hint: if a|b and a|c, a|bx + cy).

Excercise 2: Prove that no arithmetic sequence contains only squares.

3
2.3 WOP
WOP is more sophisticated than Induction and Contradiction, so worry about mastering the other
two first. However, here is an example of WOP to show that there is no integer between 0 and 1:

Take the least integer n between 0 and 1. Any integer times another integer is yet another in-
teger, so n ∗ n is an integer, but n ∗ n < n, so we have found an integer smaller than n between 0
and 1. Thus we have contradiction and are done.

Note: not all sets of numbers are well-ordered, but every finite set is, as is the set of integers
(the real numbers are also well-ordered, but not in any way that is useful for proving stuff about
them). Thus, you need to be careful when you use WOP that it is actually applicable. A good
example would be trying to use WOP to prove that there is no real number between 0 and 1 (such
a proof would be obviously bogus).

3 Metatechniques
These are general problem solving techniques that can be basically applied to many different things.
More of these will be described in later lectures, but these tend to some of the broadest ones.

1. Try small/special cases. Also don’t be afraid to go back to trying examples if you get stuck.

2. Prove the statement for some easy case, then show that it is still true if you change things.

3. Prove that two quantities change the same way (for example, they have the same recurrence
relation).

4. Use wishful thinking – what would make the problem easier if it were true?

5. Find the limiting cases of a statement. This gives you insight into how ”true” the statement
is and how much information you can give up before you will be unable to prove it.

6. Make sure you are using all of the information. Proof problems generally don’t give extraneous
information, but there are a few exceptions.

7. Try(and fail) to disprove the problem statement. This will help you understand why the
problem statement is true.

8. To check your progress, occasionally check if your most recent progress is still true. Sometimes
you will think you have solved a hard problem very easily - only to find that you actually
made a mistake back in the beginning that caused everything after that to be false.

9. Find ways to use tricky conditions in problems. Also, ask yourself what is making the problem
hard.

10. Always consider special techniques, such as induction, contradiction, WOP, etc., as well as
being clever.

11. Make sure you carry enough information with you in inductions (i.e., a statement that is very
strong for small values of n but gets very weak as n grows larger will usually not give you
enough information by itself to use induction; you should either try a different approach or
strengthen the inductive step).

4
 12. If you feel like you are forcing an idea, try something else. Don’t be afraid to try many
different techniques.

13. Don’t be afraid to try something silly. Also try solving slightly easier problems, or proving
loose bounds on quantities. Even if they don’t immediately lead to the answer, they can give
you insight into the problem and might be an important part of the solution.

4 Problems
Yay! We will present solutions on the board at the end. If a problem seems hard, don’t give up.
After all, you’ll be given 4 and a half hours on the USAMO. Also, when solutions are presented,
keep in mind that how someone came up with the answer is much more important than the answer
itself (this goes for both the presenter and audience).

1. Do all the exercises in the previous sections. These should be easy if you understand the
techniques involved, but you should write out actual proofs to practice putting the techniques
to paper.
n
2. (Geometric Series) Prove that a + ar + ar2 + . . . + arn = a 1−r
1−r .

3. (Hockey Stick Identity) Prove that nk = n−1 n−2 k−1

k−1 + k−1 + . . . + k−1 .
21n+4
4. (*1st IMO Problem Ever*, 1959) Prove that 14n+3 is in lowest terms for any natural number
n. (Don’t worry, this isn’t as hard as you think an IMO problem would be)
√
5. Prove that 2 is irrational.
√ √
( 1+2 ) −( 1−2 5 )n )
5 n
6. Prove that Fn = √
5
, where Fn is the nth Fibonacci number and F0 = 0.

7. Show that any set of n integers has some subset whose sum is divisible by n.

8. Prove that nk = n−1 + n−1

k k−1 .

9. (MOP 2006) Let n be an integer greater than 3. Prove that the roots of the polynomial

P (x) = xn − 5xn−1 + 12xn−2 − 15xn−3 + an−4 xn−4 + . . . + a0

cannot all be both real and positive.

10. (MOP 2006) Let a, b, and c be real numbers in the interval (0,1]. Prove that

a b c
+ + ≤2
bc + 1 ca + 1 ab + 1
1 1 1
(Hint: the substitution a = x+1 , b= y+1 , c= z+1 removes the constraint on the interval).

11. (MOP 2006) Let S be a set of rational numbers with the following properties: 21 is in S; if x
1 x
is in S, then both x+1 and x+1 are in S. Prove that S contains all rational numbers in the
interval (0,1).