Further Links Contact Us Search Help

Syllabus | Exams | Teachers | Students | News | Communications

Mathematics

Home > Mathematics > Extension 1 > Mathematical Induction > Extension 1 - Mathematical Induction

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:

1. Factorising;
2. sigma notation; and
3. 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

1. By considering the sum of the terms of an arithmetic series, show that
   (1 + 2 + 3 + . . . + n)² =
   
   
2. By using the Principle of Mathematical Induction, prove that
   1³ + 2³ + 3³ + . . . + n³ = (1 + 2 + 3 + . . . + n)² for all n 1.
   
   
3. Prove by mathematical induction that for n 1,
   1² + 3² + 5² + . . . + (2n - 1)² =
   
   
4. 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.
   
   
5. 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
   
   
   1. Find u₅ and u_k+1
      
      
   2. Assuming that the sum S_k  of the first k  terms of this series is given by the formula
      
      
      
      prove that
   3. Explain why the sum of the first n  terms of the series is
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
   
   
   
   
5. Use mathematical induction to prove that, for any positive integer n, 5^{n - 1} - 1 is divisible by 4.
   
   
6. 1. Use mathematical induction to prove the identity:
      
      1.2.3.4 + 2.3.4.5 + 3.4.5.6 + . . . + n (n + 1) (n + 2) (n + 3)
      
      n (n + 1) (n + 2) (n + 3) (n + 4).
      
      
   2. Hence state the limit of
      
      
      
      as n increases indefinitely.
      
      
7. Prove by mathematical induction that:
   
   
   
   for all positive integers n.
   
   
8. Prove by induction that
   
   
   
   for all positive integers n and x 0, 1.
   
   
9. 1. Factorise the polynomial 2n² + 7n + 6.
      
      
   2. By use of the Principle of Mathematical Induction, prove the relation
      6(1²+ 2²+ 3² + . . . + n²) = n(n + 1) (2n + 1 ).
      
      
   3. Hence, find the value of the limit
      
      
      
      
10. Prove by mathematical induction that
    
    
    
    
11. Use mathematical induction to show that
    
    sinq + sin 2q +sin 3 q + ...+ sin nq
    
    =
    
    
12. The Fibonacci numbers are defined by
    
    Fn = Fn-1 + Fn-2 , n 3,
    
    and F1 = F2 = 1,
    
    where Fn is the nth Fibonacci number.
    
    Prove, by mathematical induction that
    
    F1 + F2 + F3 + . . . + Fn = Fn-2 - 1.
    
    
13. Use mathematical induction to prove that
    
    if
    
    then

Back