1/11
ADMATHS GRADE 12
SECTION: ALGEBRA
LESSON A22: MATHEMATICAL INDUCTION
______________________________________________________________
“In maths proof beyond reasonable doubt proves nothing; we need to
prove beyond any doubt at all!!!”
Mathematical induction is a method which we use to prove that a statement
is true, without any doubt.
Consider the statement:
1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2
Is this statement true for all natural numbers 𝑛?
Let us test:
𝑛 = 1: 𝐿𝐻𝑆 = 1 𝑅𝐻𝑆 = 12 = 1 ∴ 𝐿𝐻𝑆 = 𝑅𝐻𝑆
𝑛 = 2: 𝐿𝐻𝑆 = 1 + 3 = 4 𝑅𝐻𝑆 = 22 = 4 ∴ 𝐿𝐻𝑆 = 𝑅𝐻𝑆
𝑛 = 3: 𝐿𝐻𝑆 = 1 + 3 + 5 = 9 𝑅𝐻𝑆 = 32 = 9 ∴ 𝐿𝐻𝑆 = 𝑅𝐻𝑆
You are almost 100% sure because of your gut feel... But it would be
impossible to substitute every natural number and therefore prove the
statement!
This is where we use mathematical induction.
Mathematical induction works on the same principle as when dominoes fall...
If the first domino falls, the second one will fall, this will cause the third one to
fall, which causes the fourth one to fall, ..., etc. Of course, every domino will
fall.
©AdMaths SA A22
2/11
With mathematical induction we first prove that the statement is true for the
first one. Thereafter we assume that it will be true for a certain given one
(let’s call this given one 𝑘). The proof involves that from this assumption the
next one (𝑘 + 1) will always be true.
Therefore, if it is true for the first one, and it was proven that it will always be
true for the next one, it means that (like dominoes) it will hold for the next one
and the next one and the next one... and therefore it will hold for all of them.
MATHEMATICAL INDUCTION HAS 4 STEPS
1. Prove that the statement is true for the first value of 𝑛:
𝑛=1
2. Assume that the statement is true for any given value of 𝑛:
𝑛=𝑘
3. Prove that the statement will be true for the next value of 𝑛:
𝑛 =𝑘+1
4. Deduction is that if the statement is true for the first and then for every
successive one, it will be true ∀ 𝑛 ∈ ℕ.
ABBREVIATIONS USED
∀ For all values of...
𝑛 ∈ ℕ 𝑛 where 𝑛 will be a natural number.
©AdMaths SA A22
3/11
Example 1
Prove that 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 ∀ 𝑛∈ℕ
Solution
1. Prove that the statement is true for 𝑛 = 1.
𝐿𝐻𝑆: 2(1) − 1 = 1
(It will always be only the first term.)
𝑅𝐻𝑆: (1)2 = 1
Thus 𝐿𝐻𝑆 = 𝑅𝐻𝑆.
Thus the statement is true for 𝑛 = 1.
2. Suppose the statement is true for a certain number 𝑛 = 𝑘.
Thus: 1 + 3 + 5 + ⋯ + (2𝑘 − 1) = 𝑘 2 (*)
Why is it possible to say this? Because we know that at this stage there is at
least one value for which the statement is true, namely 𝑛 = 1. Thus 𝑘 = 1.
(Do you understand that you merely substitute 𝑛 with 𝑘?)
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1.
I.e. prove that: 1 + 3 + 5 + ⋯ + (2(𝑘 + 1) − 1) = (𝑘 + 1)2
(Do you understand that you now replace 𝑛 with (𝑘 + 1)?)
HERE FOLLOWS THE REAL PROOF:
𝐿𝐻𝑆: 1 + 3 + 5 + ⋯ + (2𝑘 − 1) + (2(𝑘 + 1) − 1)
= 𝑘2 + 2𝑘 + 2 − 1 From (*)
= 𝑘 2 + 2𝑘 + 1
= (𝑘 + 1)2 = 𝑅𝐻𝑆
Thus the statement is true for 𝑛 = 𝑘 + 1, if the statement is true for 𝑛 = 𝑘.
But the statement is true for 𝑛 = 1.
4. Thus the statement is true ∀ 𝑛 ∈ ℕ by the principle of mathematical
induction.
©AdMaths SA A22
4/11
Example 2
Prove that
𝑛(𝑛 + 1)
1+ 2 +3+⋯+𝑛 = ∀ 𝑛∈ℕ
2
Solution
1. Prove that the statement is true for 𝑛 = 1.
1(1+1)
LHS: = 1 RHS: = =1
2
Thus LHS = RHS.
Thus the statement is true for 𝑛 = 1.
2. Suppose the statement is true for a certain number 𝑛 = 𝑘.
𝑘(𝑘 + 1)
1 + 2 + 3 + ⋯+ 𝑘 =
2
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1.
I.e. prove that:
(𝑘 + 1)((𝑘 + 1) + 1)
1 + 2 + 3 + ⋯ + (𝑘 + 1) =
2
LHS: 1 + 2 + 3 + ⋯ + (𝑘 + 1)
= 1 + 2 + 3 + ⋯ + 𝑘 + (𝑘 + 1) [substitute the term 𝑘]
𝑘(𝑘 + 1)
= + (𝑘 + 1)
2
𝑘(𝑘 + 1) + 2(𝑘 + 1)
=
2
𝑘 2 + 𝑘 + 2𝑘 + 2 𝑘 2 + 3𝑘 + 2
= =
2 2
(𝑘 + 1)(𝑘 + 2)
= = RHS
2
Thus the statement is true for 𝑛 = 𝑘 + 1.
4. Thus the statement is true ∀ 𝑛 ∈ ℕ by the principle of mathematical
induction.
©AdMaths SA A22
5/11
EXERCISE 1
Prove by mathematical induction that the following statements are true for all
𝑛 ∈ ℕ:
3 3 3
𝑛2 (𝑛 + 1)2
3
1. 1 + 2 + 3 + ⋯+ 𝑛 =
4
𝑛(𝑛 + 3)
2. 2 + 3 + 4 + ⋯ + (𝑛 + 1) =
2
3. 1 + 2 + 22 + 23 + ⋯ + 2𝑛−1 = 2𝑛 − 1
THE SIGMA NOTATION: 𝜮
In mathematics we always have a shorter way to write things, which
sometimes makes mathematics easier and sometimes more difficult.
Mathematicians have a short way to represent the sum of a series. They use
the Greek capital letter for s, named sigma: Σ
Eg.
7
∑ 2(𝑛 + 3)
𝑛=1
Reads as follows: The sum of the series 2(𝑛 + 3) from 𝑛 = 1 up to 𝑛 = 7
It is expanded as follows:
2(𝟏 + 3) + 2(𝟐 + 3) + 2(𝟑 + 3) + 2(𝟒 + 3) + 2(𝟓 + 3) + 2(𝟔 + 3) + 2(𝟕 + 3)
Another example:
𝑘
∑ 5𝑛 = 5(𝟏) + 5(𝟐) + 5(𝟑) + ⋯ + 5(𝒌)
𝑛=1
THUS:
𝑘+1
∑ 5𝑛 = 5(𝟏) + 5(𝟐) + 5(𝟑) + ⋯ + 5(𝒌 + 𝟏)
𝑛=1
= 5(𝟏) + 5(2) + 5(3) + ⋯ + 5(𝒌) + 5(𝒌 + 𝟏)
𝑘
= ∑ 5𝑛 + 5(𝑘 + 1)
𝑛=1
©AdMaths SA A22
6/11
Another example:
𝑘+1 𝑘
∑ 𝑝(𝑝 + 3)2 = ∑ 𝑝(𝑝 + 3)2 + (𝒌 + 𝟏)(𝒌 + 𝟏 + 3)2
𝑝=1 𝑝=1
Example 3
Prove by mathematical induction that
𝑛
𝑛
∑[𝑎 + (𝑖 − 1)𝑑] = [2𝑎 + (𝑛 − 1)𝑑] ∀ 𝑛 ∈ ℕ
2
𝑖=1
Solution
1. Prove that the statement is true for 𝑛 = 1:
1 1
𝐿𝐻𝑆 = 𝑎 + (1 − 1)𝑑 = 𝑎 𝑅𝐻𝑆 = [2𝑎 + (1 − 1)𝑑] = (2𝑎) = 𝑎
2 2
∴ 𝐿𝐻𝑆 = 𝑅𝐻𝑆 Thus the statement is true for 𝑛 = 1.
2. Assume the statement is true for a certain 𝑛 = 𝑘:
𝑘
𝑘
∑[𝑎 + (𝑖 − 1)𝑑] = [2𝑎 + (𝑘 − 1)𝑑]
2
𝑖=1
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1:
𝒌+𝟏
𝐿𝐻𝑆: ∑[𝑎 + (𝑖 − 1)𝑑]
𝑖=1
= 𝑎 + (𝑎 + 𝑑 ) + (𝑎 + 2𝑑) + ⋯ + [𝑎 + (𝒌 + 𝟏 − 1)𝑑]
= 𝑎 + (𝑎 + 𝑑 ) + (𝑎 + 2𝑑) + ⋯ + [𝑎 + (𝒌 − 1)𝑑] + [𝑎 + (𝒌 + 𝟏 − 1)𝑑]
𝒌
= ∑[𝑎 + (𝑖 − 1)𝑑 ] + 𝑎 + (𝑘)𝑑 (From assumption)
𝑖=1
𝑘
= [2𝑎 + (𝑘 − 1)𝑑] + 𝑎 + (𝑘)𝑑
2
𝑘[2𝑎 + (𝑘 − 1)𝑑] + 2[𝑎 + 𝑘𝑑] (𝐿𝐶𝑀 = 2)
=
2
2𝑎𝑘 + 𝑘 2 𝑑 − 𝑘𝑑 + 2𝑎 + 2𝑘𝑑 2𝑎𝑘 + 2𝑎 + 𝑘 2 𝑑 + 𝑘𝑑
= =
2 2
©AdMaths SA A22
7/11
2𝑎(𝑘 + 1) + 𝑘𝑑(𝑘 + 1) (𝑘 + 1)[2𝑎 + 𝑘𝑑]
= =
2 2
𝑘+1
𝑅𝐻𝑆: [2𝑎 + (𝑘 + 1 − 1)𝑑]
2
𝑘+1
= [2𝑎 + 𝑘𝑑]
2
(𝑘 + 1)[2𝑎 + 𝑘𝑑]
=
2
Thus the statement is true for 𝑛 = 𝑘 + 1
4. The statement is true for all 𝑛 ∈ ℕ by the principle of mathematical
induction.
Example 4
Prove by mathematical induction that
𝑛
𝑛2 (𝑛 + 1)2
3
∑𝑎 = ∀ 𝑛∈ℕ
4
𝑎=1
Solution
1. Prove that the statement is true for 𝑛 = 1:
3
12 (1 + 1)2 1(4)
𝐿𝐻𝑆 = 1 = 1 𝑅𝐻𝑆 = = =1
4 4
∴ 𝐿𝐻𝑆 = 𝑅𝐻𝑆 Thus the statement is true for 𝑛 = 1.
2. Assume the statement is true for 𝑛 = 𝑘:
𝑘
𝑘 2 (𝑘 + 1)2
3
∑𝑎 =
4
𝑎=1
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1:
𝑘+1
𝐿𝐻𝑆: ∑ 𝑎3 = 13 + 23 + 33 + ⋯ + 𝑘 3 + (𝑘 + 1)3
𝑎=1
𝑘
= ∑ 𝑎3 + (𝑘 + 1)3
𝑎=1
𝑘 2 (𝑘 + 1)2
= + (𝑘 + 1)3
4
©AdMaths SA A22
8/11
𝑘 2 (𝑘 + 1)2 + 4(𝑘 + 1)3
= (𝐿𝐶𝑀 = 4)
4
(𝑘 + 1)2 (𝑘 2 + 4(𝑘 + 1))
= (Factorise)
4
(𝑘 + 1)2 (𝑘 2 + 4𝑘 + 4) (𝑘 + 1)2 (𝑘 + 2)2
= =
4 4
2
(𝑘 + 1)2 ((𝑘 + 1) + 1) (𝑘 + 1)2 (𝑘 + 2)2
𝑅𝐻𝑆: =
4 4
Thus the statement is true for 𝑛 = 𝑘 + 1.
4. Thus the statement is true for all 𝑛 ∈ ℕ by the principle of
mathematical induction.
EXERCISE 2
Prove by mathematical induction that the following statements are true for all
𝑛 ∈ ℕ:
𝑛
1. ∑ 2𝑟 = 𝑛(𝑛 + 1)
𝑟=1
𝑛
𝑖−1
𝑎(𝑟 𝑛 − 1)
2. ∑𝑎 𝑟 =
𝑟−1
𝑖=1
𝑛
𝑛(𝑛 + 1)(2𝑛 + 7)
3. ∑ 𝑝(𝑝 + 2) =
6
𝑝=1
𝑛
𝑛(𝑛 + 1)(2𝑛 + 1)
4. ∑ 𝑖2 =
6
𝑖=1
DIVISIBILITY BY INDUCTION
Divisibility can also be proved by mathematical induction.
You must first understand what is meant by the term “divisible”.
12
The number 12 is divisible by 4 because = 3 remainder 0.
4
Thus 12 = 4(3) remainder 0.
©AdMaths SA A22
9/11
Consider the following. If an expression eg. (5𝑛 − 1) is divisible by 4, it can
be written as:
5𝑛 − 1
= 𝑝; 𝑝 ∈ ℕ
4
Thus we will have: 5𝑛 − 1 = 4𝑝
So, if 5𝑛 − 1 is divisible by 4, we can write 5𝑛 − 1 as 4𝑝 where 𝑝 ∈ ℕ.
Mathematical induction can be used to prove that an expression is always
divisible by a certain integer.
Example 5
Prove that 3𝑛 − 1 is divisible by 2 ∀ 𝑛 ∈ ℕ.
Solution
1. Prove that the statement is true for 𝑛 = 1.
31 − 1 = 2 is divisible by 2.
NOTE: We do not have a
Thus the statement is true for 𝑛 = 1. LHS and a RHS here - it is
not a series.
2. Assume the statement is true for 𝑛 = 𝑘.
Thus: 3𝑘 − 1 is divisible by 2.
3𝑘 − 1
=𝑝
2
∴ (3𝑘 − 1) = 2𝑝
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1.
I.e. prove that: (3𝑘+1 − 1) is divisible by 2.
3𝑘+1 − 1
= 3 ∙ 3𝑘 − 1
= 2 ∙ 3𝑘 + 3𝑘 − 1
= 2 ∙ 3𝑘 + 2𝑝 (From assumption)
= 2(3𝑘 + 𝑝) which is divisible by 2
Thus the statement is true for 𝑛 = 𝑘 + 1.
4. Thus the statement is true ∀ 𝑛 ∈ ℕ, by the principle of
mathematical induction.
©AdMaths SA A22
10/11
Example 6
Use mathematical induction to prove that 3𝑛 + 3𝑛+1 + 3𝑛+2 is divisible by 13
for all 𝑛 ∈ ℕ. (IEB 2009)
Solution
Prove that 3𝑛 + 3𝑛+1 + 3𝑛+2 is divisible by 13 ∀ 𝑛 ∈ ℕ.
1. Prove that the statement is true for 𝑛 = 1.
31 + 31+1 + 31+2
3 + 9 + 27 = 39 which is divisible by 13.
Statement is true for 𝑛 = 1.
2. Assume the statement is true for 𝑛 = 𝑘.
I.e. that 3𝑘 + 3𝑘+1 + 3𝑘+2 is divisible by 13.
3𝑘 + 3𝑘+1 + 3𝑘+2
∴ = 𝑝; 𝑝 ∈ ℕ
13
3𝑘 + 3𝑘+1 + 3𝑘+2 = 13𝑝
3. Now prove that the statement is true for 𝑛 = 𝑘 + 1.
3𝑘+1 + 3𝑘+1+1 + 3𝑘+1+2
= 3 ∙ 3𝑘 + 3 ∙ 3𝑘+1 + 3 ∙ 3𝑘+2
= 3(3𝑘 + 3𝑘+1 + 3𝑘+2 )
= 3(13𝑝) is divisible by 13
Thus the statement is true for 𝑛 = 𝑘 + 1.
4. Thus the statement is true ∀ 𝑛 ∈ ℕ, by the principle of
mathematical induction.
EXERCISE 3
1. Prove that 7𝑛 − 4𝑛 is divisible by 3 if 𝑛 ∈ ℕ.
2. Prove that 𝑛3 − 𝑛 is divisible by 3 for all 𝑛 ≥ 2 if 𝑛 ∈ ℕ.
3. Prove that 𝑎2𝑛+1 − 𝑏 2𝑛+1 is divisible by 𝑎 − 𝑏 for all 𝑛 ∈ ℕ.
©AdMaths SA A22
11/11
HOMEWORK
𝑛(𝑛 + 3)
1. Prove that for all 𝑛 ∈ ℕ: 2 + 3 + 4 + ⋯ + (𝑛 + 1) =
2
2 3 𝑛−1
𝑟𝑛 − 1
2. Prove that for all 𝑛 ∈ ℕ: 1 +𝑟 +𝑟 +𝑟 +⋯+𝑟 =
𝑟−1
3. Prove that for all 𝑛 ∈ ℕ: ∑ (2𝑝 − 1) = 𝑛2
𝑝=1
𝑛
𝑛
4. Prove that for all 𝑛 ∈ ℕ: ∑(2𝑟 − 1)2 = (2𝑛 + 1)(2𝑛 − 1)
3
𝑟=1
5. Prove that 13𝑛 − 2𝑛 is divisible by 11 for all 𝑛 ∈ ℕ.
6. Prove by induction that 𝑦 𝑛 − 𝑥 𝑛 is divisible by 𝑦 − 𝑥 for all 𝑛 ∈ ℕ.
7. Prove by induction that 9𝑛 − 8𝑛 − 1 is divisible by 8 for all natural
numbers 𝑛 where 𝑛 > 1.
8.1 Prove by mathematical induction that 𝑛2 + 𝑛 will be an even number for
all natural numbers 𝑛.
8.2 Hence, prove that 𝑛3 − 𝑛 is divisible by 6 for all 𝑛 ∈ ℕ.
©AdMaths SA A22
