Induction

Induction

then it will also be true for .

This works like the domino effect. The first statement establishes that the first domino will fall. The second statement establishes that if any domino falls, then the next one must fall as well. Hence all the dominoes fall.

Example: Prove that

Firstly, for

we have

So our formula clearly holds for

.

Now assume that

is true for a specific

.

Then

Which is exactly what the formula should say when

is substituted in for .

Thus the result is established.

Green Question: Prove by induction that

Red Question: Prove by induction that if then

for all

, where

th Fermat number is defined by

,

where

means 2 raised to the power . Calculate , , and . Show that, for , and ,

(*)

Prove, by induction, or otherwise, that (*) holds for all

. Deduce that no two Fermat numbers have a common factor greater than 1.

Hence show that there are an infinitely many prime numbers.

Purple Question: (P. Zeitz) Suppose

Use induction to prove that

for all positive integer

.

STEP 1999, Math II, #3: Let

that is a polynomial. By means of your induction argument determine the order of this polynomial and the coefficient of the highest power of

.

Show also that if for some value of , then .

STEP 2003, Math II, #3: Prove that the cube root of any irrational number is an irrational number.

Let . Given that is an irrational number, prove by induction that is an irrational number for every positive integer .

Hence, or otherwise, give an example of an infinite sequence of irrational numbers which converges to a given integer

.

[An irrational number is a number that cannot be expressed as the ratio of two integers.]

STEP 2008, Math III, #5: The functions , for satisfy the recurrence relation

( ) (*)

Show by induction that

where .

In the case , determine (with proof) an expression for in terms of (assumed to be non-zero) and ,

where

Find the two possible expressions for in terms of .

STEP 2011, Math III, #7: Let

is even, show by induction that can be written in the form

is odd, show by considering where is even, or otherwise, that can be written in the form

, can be written as the sum of the square roots of two consecutive integers.