Mathematics

Home > Mathematics > Extension 1 > Mathematical Induction > Categories of mathematical induction (MANSW extract)

MATHEMATICAL INDUCTION

Bobby Gaensler

Extract from Reflections - Journal of the Mathematical Association of NSW

BACKGROUND KNOWLEDGE REQUIRED

As much of the 3 Unit course as possible is desirable knowledge, because questions can be applied to just about any part of the course. It is possible, however, to teach the basic concepts, provided that the students have studied:

(a) Factorising;
(b) sigma notation; and
(c) indices.

Students, especially those in Year 11, often find the basic idea of mathematical induction a little confusing and are convinced that the teacher has cheated. Parallel this mathematical concept with methods used in science, where experiments are done, a hypothesis is formed, and then more work is done to confirm the hypothesis.

Students of mathematics, up to this stage, have probably only seen direct methods of proof, for example, Euclidean geometry. Possibly they have been shown examples of indirect proofs, for example, proving that the square root of 2 is irrational, or proving the theorem "if the opposite angles of a quadrilateral are supplementary, then the quadrilateral is cyclic".

PROOF BY INDUCTION

In the actual proof by induction, there are four steps.

Step 1 Test the rule or formula for the first allowable value of n (usually n = 1).

Step 2 Assume true for some value of n, say k.

Step 3 Having made the assumption in Step 2, show that the assumption is still true for the next value of n, that is, n = k + 1.

(This is the most important - and the most difficult - part of the proof.) This step has told us that if we can find a value for n that makes the formula or rule true, the next value of n must also make it true. The next step formally states this fact and this is where we draw our conclusion.

Step 4 (Assuming proof was for n 1 and integral). Hence, if the result is true for
n = k, then it is true for n = k + 1. Since the result is true for n = 1, it is true for
n = 1 + 1 = 2, and thus for n = 2 + 1 = 3, and so on for all positive integral values of n. Step 4 is virtually the same in all questions.

There are various types of questions which can be treated. Here are some examples:

I

1. To prove that 1 + 3 + 5 + . . . + (2n - 1) = n²

2. To prove that

3. Show that 3⁴ⁿ - 1 is divisible by 80 for all positive integral values of n.

4. Show that

5. Show that xⁿ - 1 is divisible by (x - 1).

6. Show that sin (x + 180n) = (-1)ⁿ sin x for integers n > 0.

7. Show that for n

8. Show that n ! > 2ⁿ for n > 4.

II

Year 12 HSC questions on mathematical induction

(a) By considering the sum of the terms of an arithmetic series, show that
(1 + 2 + 3 + . . . + n)² =

(b) By using the Principle of Mathematical Induction, prove that
1³ + 2³ + 3³ + . . . + n³ = (1 + 2 + 3 + . . . + n)² for all n 1.

Prove by mathematical induction that for n 1,
1² + 3² + 5² + . . . + (2n - 1)² =

Prove by mathematical induction that
1 x 2⁰ + 2 x 2¹ + 3 x 2² + . . . + n x 2^{n - 1}
= 1 + (n - 1) 2² for all integers n 1.

Use the Principle of Mathematical Induction to prove that 5ⁿ + 2 x (11ⁿ) is a multiple of 3 for all positive integers n.

III

1. The nth term of a series is given by

(a) Find u₅ and u_k+1

(b) Assuming that the sum S_k of the first k terms of this series is given by the formula

prove that

2. If Sn = 1 x 2 + 2 x 3 + . . . + n (n + 1), use the Principle of Mathematical Induction to show that
for all positive integers n.

3. Write down the formula for the sum of the first n positive odd integers. Explain the method of mathematical induction and use it to prove this formula.

4. Use the method of mathematical induction to show that the sum of the squares of the first n positive integers is