Mathematics Learning Centre
Mathematical Induction
Mary Barnes
Sue Gordon
1987
c University of Sydney
,Contents
1 Mathematical Induction 1
1.1 Why do we need proof by induction? . . . . . . . . . . . . . . . . . . . . . 1
1.2 What is proof by induction? . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Finding the formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Further exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Solutions to Exercises 11
, Mathematics Learning Centre, University of Sydney 1
1 Mathematical Induction
Mathematical Induction is a powerful and elegant technique for proving certain types of
mathematical statements: general propositions which assert that something is true for all
positive integers or for all positive integers from some point on.
Let us look at some examples of the type of result that can be proved by induction.
Proposition 1. The sum of the first n positive integers (1, 2, 3, . . .) is 12 n(n + 1).
Proposition 2. In a convex polygon with n vertices, the greatest number of diagonal
that can be drawn is 12 n(n − 3).
Note, we give an example of a convex polygon together with one that is not convex in
Figure 1.
This is a convex polygon This polygon is not convex
Figure 1: Examples of polygons
A polygon is said to be convex if any line joining two vertices lies within the polygon or
on its boundary.
By a diagonal, we mean a line joining any two non-adjacent vertices.
As you see, the subject matter of the statements can vary widely. It can include algebra,
geometry and many other topics. What is common to all the examples is the number n
that appears in the statement. In all cases it is either stated, or implicitly assumed, that
n can be any positive integer.
1.1 Why do we need proof by induction?
A natural starting point for proving many mathematical results is to look at a few simple
cases. This helps us understand what is being claimed and may even give us some pointers
for finding a proof.
Let’s do this with Proposition 1. The results are recorded in the following table.
Mathematical Induction
Mary Barnes
Sue Gordon
1987
c University of Sydney
,Contents
1 Mathematical Induction 1
1.1 Why do we need proof by induction? . . . . . . . . . . . . . . . . . . . . . 1
1.2 What is proof by induction? . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Finding the formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Further exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Solutions to Exercises 11
, Mathematics Learning Centre, University of Sydney 1
1 Mathematical Induction
Mathematical Induction is a powerful and elegant technique for proving certain types of
mathematical statements: general propositions which assert that something is true for all
positive integers or for all positive integers from some point on.
Let us look at some examples of the type of result that can be proved by induction.
Proposition 1. The sum of the first n positive integers (1, 2, 3, . . .) is 12 n(n + 1).
Proposition 2. In a convex polygon with n vertices, the greatest number of diagonal
that can be drawn is 12 n(n − 3).
Note, we give an example of a convex polygon together with one that is not convex in
Figure 1.
This is a convex polygon This polygon is not convex
Figure 1: Examples of polygons
A polygon is said to be convex if any line joining two vertices lies within the polygon or
on its boundary.
By a diagonal, we mean a line joining any two non-adjacent vertices.
As you see, the subject matter of the statements can vary widely. It can include algebra,
geometry and many other topics. What is common to all the examples is the number n
that appears in the statement. In all cases it is either stated, or implicitly assumed, that
n can be any positive integer.
1.1 Why do we need proof by induction?
A natural starting point for proving many mathematical results is to look at a few simple
cases. This helps us understand what is being claimed and may even give us some pointers
for finding a proof.
Let’s do this with Proposition 1. The results are recorded in the following table.
