Mathematical Induction training for RMO

Problem 1:

There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations.

Problem 2:

Suppose that you know that a golfer plays the first hole on a golf course with an infinite number of holes and that if the golfer plays one hole, then the golfer goes on to play the next hole. Prove that the golfer plays every hole on the course.

Problem 3:

Let P(n) be the statement that n^{p}<n^{n}, where n is an integer greater than 1.

(a) What is the statement P(2)?

(b) Show that P(2) is true, completing the basis step of the proof.

(c) What is the inductive hypothesis?

(d) What do you need to prove in the inductive step?

(e) Complete the inductive step.

(f) Explain why these steps show that this inequality is true whenever n is an integer greater than 1.

Problem 4:

Prove that if h>-1, then 1+nh \leq (1+h)^{n} for all non negative integers n. This is called Bernoulli’s inequality.

Problem 5:

Suppose that a and b are real numbers with $latex 0<b<a$. Prove that if n is a positive integer, then a^{n}-b^{n} \leq na^{n-1}(a-b).

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s