Standard Proofs by Induction (Edexcel International AS Further Maths)
Revision Note
Written by: Mark Curtis
Reviewed by: Dan Finlay
Proof by Induction with Series
What are the steps for proof by induction with series?
For example: prove that
It has a left-hand side,
and a right-hand side,
STEP 1
The basic step: Show result is true for
Substitute into both sides individually
STEP 2
The assumption step: Assume the LHS and RHS are equal for some where is some integer
Replace with in the statement
Write: "Assume is true"
STEP 3
The inductive step: You need to prove that the LHS and RHS are equal for
Start with the LHS for
Take the last term out:
Substitute in the assumption (STEP 2) :
Factorise:
Check if it is the same as the RHS for
So LHS = RHS for , as long as the assumption is true
STEP 4
The conclusion step: Explain in words how the above steps make the result true for all integers, using the following two sentences:
"If it is true for , then it is true for ."
"As it is true for , the statement is true for all ."
Worked Example
Prove by induction that for .
STE P 1: The basic step
Find the LHS when
Find the RHS when
The LHS and RHS are equal, which shows the statement is true for
State this
LHS = RHS, so it is true for
STEP 2: The assumption step
Assume the statement is true for some where is a positive integer
Assume that
STEP 3: The inductive step
Find the RHS when
Find the LHS when
Prove that the LHS when equals the RHS when
Start by pulling out the final term in the sum
Now use the assumption in STEP 2 to replace the sum from 1 to with its answer
Now factorise the right-hand side
Expand inside the square brackets then continue to factorise
This is the same as the RHS when
The LHS and RHS are equal, which shows that the statement is true for
State this
LHS = RHS, so it is true for
STEP 4: The conclusion
We have just proved that if the case when is true, then the case when is true
We have also shown that the case when is true
Those two parts come together to mean that is true, so is true, so is true, ... and so on
If it is true for , then it is true for .
As it is true for , the statement is true for all .
Proof by Induction with Divisibility
What are the steps for proof by induction with divisibility?
For example: prove that is divisible by 3 for all positive integers n
Being divisible by 3 is the same as being a multiple of 3
STEP 1
The basic step: Show result is true for
Substitute into the function
which is divisible by 3
STEP 2
The assumption step: Assume is divisible by 3 for some where is some integer
Replace with in the statement
Write "divisible by 3" as "" where is a positive integer
So where
It helps to make the subject:
STEP 3
The inductive step (method 1): You need to show that the case is divisible by 3
Substitute into the function
Use index laws to substitute in the assumption (STEP 2)
which is a multiple of 3
So is divisible by 3 (as long as the assumption is true)
STEP 3
The inductive step (method 2): An alternative method is to show that the difference is a multiple of 3
i.e.
Making the subject gives
So is divisible by 3 (as long as the assumption is true, i.e. that is divisible by 3)
This method does not always work
When it does, a hint will be given in the question
STEP 4
The conclusion step: Explain in words how the above steps make the result true for all integers, using the following two sentences:
"If it is true for , then it is true for ."
"As it is true for , the statement is true for all ."
Worked Example
Prove by induction that is divisible by 7 for all integers satisfying .
STE P 1: The basic step
Prove that it is true for
State that it is true for
14 is divisible by 7, so it is true for
STEP 2: The assumption step
Assume the statement is true for some where is a positive integer
Assume that is divisible by 7
Replace "being divisible by 7" with being equal to , where is a positive integer
STEP 3: The inductive step
Substitute into the function
Now make either or the subject of STEP 2 and substitute it in
It helps to use index laws first
Simplify the terms, using index laws to group the terms
The goal is to show that this result is divisible by 7
Factorise out a 7 to show this
State that it is true for
is divisible by 7, so it is true for
STEP 4: The conclusion
We have just proved that if the case when is true, then the case when is true
We have also shown that the case when is true
Those two parts come together to mean that is true, so is true, so is true, ... and so on
If it is true for , then it is true for .
As it is true for , the statement is true for all integers .
Proof by Induction with Sequences
What are the steps for proof by induction with sequences?
For example: prove that the sequence given recursively by where has the nth term formula for
STEP 1
The basic step: Show result is true for
Substitute into the formulae separately
from the recursive formula
from the nth term formula
STEP 2
The assumption step: Assume that the term satisfies for some where is some integer
Replace with in the statement
The assumption is on the nth term formula
(not on the recursive formula)
STEP 3
The inductive step: Show that the nth term formula is true for
Use the recursive formula to write
Substitute in the assumption (STEP 2) and simplify
Check this is the same as the nth term formula when
It is the same
STEP 4
The conclusion step: Explain in words how the above steps make the result true for all integers, using the following two sentences:
"If it is true for , then it is true for ."
"As it is true for , the statement is true for all ."
Examiner Tips and Tricks
If the recursive formula involves the previous two terms, then the basic step must be done for both and .
Worked Example
A sequence is defined by where and .
Prove by mathematical induction that , where .
STE P 1: The basic step
Find from the recursive sequence
Find from the nth term formula
These two terms are equal
State that it is true for
It is true for
STEP 2: The assumption step
Assume the formula is true for some where is a positive integer
Assume that
STEP 3: The inductive step
Use the recursive sequence to write in terms of
Replace with the assumption in STEP 2 and simplify
Check that this is the same as substituting into the nth term formula
State that the result is true for
It is true for
STEP 4: The conclusion
We have just proved that if the case when is true, then the case when is true
We have also shown that the case when is true
Those two parts come together to mean that is true, so is true, so is true, ... and so on
If it is true for , then it is true for .
As it is true for , the statement is true for all .
Proof by Induction with Matrices
What are the steps for proof by induction with matrices?
For example: prove that where for all integers .
STEP 1
The basic step: Show result is true for
Substitute into formula
STEP 2
The assumption step: Assume is true for some where is some integer
Replace with in the statement
STEP 3
The inductive step: You need to show that the case is true
Use index laws to write
Substitute in the assumption:
Multiply the matrices
Check if it is the same as the formula with
It is the same
STEP 4
The conclusion step: Explain in words how the above steps make the result true for all integers, using the following two sentences:
"If it is true for , then it is true for ."
"As it is true for , the statement is true for all ."
Worked Example
The matrix is given by .
Prove, using mathematical induction, that for all integers satisfying .
STE P 1: The basic step
Prove that it is true for
State that it is true for
It is true for
STEP 2: The assumption step
Assume the formula is true for some where is a positive integer
Assume that
STEP 3: The inductive step
Look at the power of
Use index laws, then substitute in the assumption from STEP 2
Use matrix multiplication to work out the right-hand side
Simplify the terms
Check that this is the same as substituting into the formula for
State that the result is true for
It is true for
STEP 4: The conclusion
We have just proved that if the case when is true, then the case when is true
We have also shown that the case when is true
Those two parts come together to mean that is true, so is true, so is true, ... and so on
If it is true for , then it is true for .
As it is true for , the statement is true for all .
Last updated:
You've read 0 of your 10 free revision notes
Unlock more, it's free!
Did this page help you?