International A LevelFurther Maths: Further Pure 1EdexcelRevision NotesProofProof by InductionStandard Proofs by Induction

Standard Proofs by Induction (Edexcel International A Level Further Maths)

Revision Note

Mark Curtis

Expertise

Maths

Proof by Induction with Series

What are the steps for proof by induction with series?

  • For example: prove that sum from r equals 1 to n of r squared equals 1 over 6 n left parenthesis n plus 1 right parenthesis left parenthesis 2 n plus 1 right parenthesis 

    • It has a left-hand side, L H S equals sum from r equals 1 to n of r squared

    • and a right-hand side, R H S equals 1 over 6 n left parenthesis n plus 1 right parenthesis left parenthesis 2 n plus 1 right parenthesis

  • STEP 1

    The basic step: Show result is true for bold italic n bold equals bold 1

    • Substitute n equals 1 into both sides individually

      L H S equals space sum from r equals 1 to 1 of r squared equals 1 squared equals 1 R H S equals 1 over 6 cross times 1 cross times left parenthesis 1 plus 1 right parenthesis left parenthesis 2 cross times 1 plus 1 right parenthesis equals 1 over 6 cross times 2 cross times 3 equals 1

  • STEP 2

    The assumption step: Assume the LHS and RHS are equal for some bold italic n bold equals bold italic k where k is some integer

    • Replace n with k in the statement

    • Write: "Assume sum from r equals 1 to k of r squared equals 1 over 6 k left parenthesis k plus 1 right parenthesis left parenthesis 2 k plus 1 right parenthesis is true"

  • STEP 3

    The inductive step: You need to prove that the LHS and RHS are equal for n equals k plus 1

    • Start with the LHS for n equals k plus 1

      • Take the last term out: sum from r equals 1 to k plus 1 of r to the power of 2 space end exponent equals sum from r equals 1 to k of r squared space plus open parentheses k plus 1 close parentheses squared

      • Substitute in the assumption (STEP 2) :

      • sum from r equals 1 to k plus 1 of r to the power of 2 space end exponent equals 1 over 6 k left parenthesis k plus 1 right parenthesis left parenthesis 2 k plus 1 right parenthesis space plus open parentheses k plus 1 close parentheses squared

      • Factorise:
        1 over 6 open parentheses k plus 1 close parentheses left square bracket k left parenthesis 2 k plus 1 right parenthesis plus 6 open parentheses k plus 1 close parentheses right square bracket equals 1 over 6 open parentheses k plus 1 close parentheses left square bracket 2 k squared plus 7 k plus 6 right square bracket equals 1 over 6 open parentheses k plus 1 close parentheses open parentheses k plus 2 close parentheses open parentheses 2 k plus 3 close parentheses

    • Check if it is the same as the RHS for n equals k plus 1

      table row cell R H S end cell equals cell 1 over 6 open parentheses k plus 1 close parentheses open parentheses open parentheses k plus 1 close parentheses plus 1 close parentheses open parentheses 2 open parentheses k plus 1 close parentheses plus 1 close parentheses end cell row blank equals cell 1 over 6 open parentheses k plus 1 close parentheses open parentheses k plus 2 close parentheses open parentheses 2 k plus 3 close parentheses end cell end table

    • So LHS = RHS for n equals k plus 1, 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 n equals k, then it is true for n equals k plus 1."

    • "As it is true for bold italic n bold equals bold 1, the statement is true for all n element of straight integer numbers to the power of plus."

Worked Example

Prove by induction that sum from r equals 1 to n of r open parentheses r minus 3 close parentheses equals 1 third n open parentheses n minus 4 close parentheses open parentheses n plus 1 close parentheses for n element of straight integer numbers to the power of plus.

STE P 1: The basic step
Find the LHS when n equals 1

sum from r equals 1 to 1 of r open parentheses r minus 3 close parentheses equals 1 open parentheses 1 minus 3 close parentheses equals negative 2

Find the RHS when n equals 1

1 third cross times 1 cross times open parentheses 1 minus 4 close parentheses open parentheses 1 plus 1 close parentheses equals 1 third cross times open parentheses negative 6 close parentheses equals negative 2

The LHS and RHS are equal, which shows the statement is true for n equals 1
State this

LHS = RHS, so it is true for n equals 1

STEP 2: The assumption step
Assume the statement is true for some n equals k where k is a positive integer

Assume that sum from r equals 1 to k of r open parentheses r minus 3 close parentheses equals 1 third k open parentheses k minus 4 close parentheses open parentheses k plus 1 close parentheses

STEP 3: The inductive step
Find the RHS when n equals k plus 1

1 third open parentheses k plus 1 close parentheses open parentheses k plus 1 minus 4 close parentheses open parentheses k plus 1 plus 1 close parentheses equals 1 third open parentheses k plus 1 close parentheses open parentheses k minus 3 close parentheses open parentheses k plus 2 close parentheses

Find the LHS when n equals k plus 1

sum from r equals 1 to k plus 1 of r open parentheses r minus 3 close parentheses

Prove that the LHS when n equals k plus 1 equals the RHS when n equals k plus 1
Start by pulling out the final term in the sum

table row cell sum from r equals 1 to k plus 1 of r open parentheses r minus 3 close parentheses end cell equals cell sum from r equals 1 to k of r open parentheses r minus 3 close parentheses plus open parentheses k plus 1 close parentheses open parentheses k plus 1 minus 3 close parentheses end cell row blank equals cell sum from r equals 1 to k of r open parentheses r minus 3 close parentheses plus open parentheses k plus 1 close parentheses open parentheses k minus 2 close parentheses end cell end table

Now use the assumption in STEP 2 to replace the sum from 1 to k with its answer

table row cell sum from r equals 1 to k plus 1 of r open parentheses r minus 3 close parentheses end cell equals cell 1 third k open parentheses k minus 4 close parentheses open parentheses k plus 1 close parentheses plus open parentheses k plus 1 close parentheses open parentheses k minus 2 close parentheses end cell end table

Now factorise the right-hand side

table row cell sum from r equals 1 to k plus 1 of r open parentheses r minus 3 close parentheses end cell equals cell open parentheses k plus 1 close parentheses open square brackets 1 third k open parentheses k minus 4 close parentheses plus open parentheses k minus 2 close parentheses close square brackets end cell row blank equals cell 1 third open parentheses k plus 1 close parentheses open square brackets k open parentheses k minus 4 close parentheses plus 3 open parentheses k minus 2 close parentheses close square brackets end cell end table

Expand inside the square brackets then continue to factorise

table row cell sum from r equals 1 to k plus 1 of r open parentheses r minus 3 close parentheses end cell equals cell 1 third open parentheses k plus 1 close parentheses open square brackets k squared minus 4 k plus 3 k minus 6 close square brackets end cell row blank equals cell 1 third open parentheses k plus 1 close parentheses open square brackets k squared minus k minus 6 close square brackets end cell row blank equals cell 1 third open parentheses k plus 1 close parentheses open parentheses k minus 3 close parentheses open parentheses k plus 2 close parentheses end cell end table

This is the same as the RHS when n equals k plus 1
The LHS and RHS are equal, which shows that the statement is true for n equals k plus 1
State this

LHS = RHS, so it is true for n equals k plus 1

STEP 4: The conclusion
We have just proved that if the case when n equals k is true, then the case when n equals k plus 1 is true
We have also shown that the case when n equals 1 is true
Those two parts come together to mean that n equals 1 is true, so n equals 2 is true, so n equals 3 is true, ... and so on

If it is true for n equals k, then it is true for n equals k plus 1.
As it is true for n equals 1, the statement is true for all n element of straight integer numbers to the power of plus.

Proof by Induction with Divisibility

What are the steps for proof by induction with divisibility?

  • For example: prove that straight f left parenthesis n right parenthesis equals 4 to the power of n minus 1 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 bold italic n bold equals bold 1

    • Substitute n equals 1 into the function

    • straight f open parentheses 1 close parentheses equals 4 to the power of 1 minus 1 equals 3which is divisible by 3

  • STEP 2

    The assumption step: Assume straight f left parenthesis k right parenthesis equals 4 to the power of k minus 1 is divisible by 3 for some bold italic n bold equals bold italic k where k is some integer

    • Replace n with k in the statement

    • Write "divisible by 3" as "equals 3 m" where m is a positive integer

    • Sostraight f open parentheses k close parentheses equals 4 to the power of k minus 1 equals 3 m where m element of straight integer numbers to the power of plus 

    • It helps to make 4 to the power of k the subject: 4 to the power of k equals 1 plus 3 m 

  • STEP 3

    The inductive step (method 1): You need to show that the n equals k plus 1 case is divisible by 3

    • Substitute n equals k plus 1 into the function

      • straight f left parenthesis k plus 1 right parenthesis equals 4 to the power of k plus 1 end exponent minus 1

    • Use index laws to substitute in the assumption (STEP 2) 4 to the power of k equals 1 plus 3 m 

      • straight f left parenthesis k plus 1 right parenthesis equals 4 open parentheses 4 to the power of k close parentheses minus 1 equals 4 open parentheses 1 plus 3 m close parentheses minus 1 equals 3 open parentheses 4 m plus 1 close parentheseswhich is a multiple of 3

    • So straight f left parenthesis k plus 1 right parenthesisis 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 straight f left parenthesis k plus 1 right parenthesis minus straight f left parenthesis k right parenthesis is a multiple of 3

    • i.e. straight f left parenthesis k plus 1 right parenthesis minus straight f left parenthesis k right parenthesis equals 3 cross times...

    • Making straight f left parenthesis k plus 1 right parenthesisthe subject gives straight f left parenthesis k plus 1 right parenthesis equals straight f open parentheses k close parentheses plus 3 cross times...

    • So straight f left parenthesis k plus 1 right parenthesis is divisible by 3 (as long as the assumption is true, i.e. that straight f left parenthesis k right parenthesisis 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 n equals k, then it is true for n equals k plus 1."

    • "As it is true for bold italic n bold equals bold 1, the statement is true for all n element of straight integer numbers to the power of plus."

Worked Example

Prove by induction that straight f left parenthesis n right parenthesis equals 6 to the power of n plus 13 to the power of n plus 1 end exponent is divisible by 7 for all integers satisfying n greater or equal than 0.

STE P 1: The basic step
Prove that it is true for n equals 0

table row cell straight f open parentheses 0 close parentheses end cell equals cell 6 to the power of 0 plus 13 to the power of 0 plus 1 end exponent end cell row blank equals cell 1 plus 13 end cell row blank equals 14 row blank equals cell 7 cross times 2 end cell end table

State that it is true for n equals 0

14 is divisible by 7, so it is true for n equals 0

STEP 2: The assumption step
Assume the statement is true for some n equals k where k is a positive integer

Assume that straight f left parenthesis k right parenthesis equals 6 to the power of k plus 13 to the power of k plus 1 end exponent is divisible by 7

Replace "being divisible by 7" with being equal to 7 m, where m is a positive integer

6 to the power of k plus 13 to the power of k plus 1 end exponent equals 7 m

STEP 3: The inductive step
Substitute n equals k plus 1 into the function

table row cell straight f left parenthesis k plus 1 right parenthesis end cell equals cell 6 to the power of k plus 1 end exponent plus 13 to the power of open parentheses k plus 1 close parentheses plus 1 end exponent end cell row blank equals cell 6 to the power of k plus 1 end exponent plus 13 to the power of k plus 2 end exponent end cell end table

Now make either 6 to the power of k or 13 to the power of k plus 1 end exponent the subject of STEP 2 and substitute it in
It helps to use index laws first

table row cell straight f left parenthesis k plus 1 right parenthesis end cell equals cell 6 to the power of k cross times 6 plus 13 to the power of k plus 2 end exponent end cell row blank equals cell open parentheses 7 m minus 13 to the power of k plus 1 end exponent close parentheses cross times 6 plus 13 to the power of k plus 2 end exponent end cell end table

Simplify the terms, using index laws to group the 13 to the power of k plus 1 end exponent terms

table row cell straight f left parenthesis k plus 1 right parenthesis end cell equals cell 42 m minus 6 cross times 13 to the power of k plus 1 end exponent plus 13 to the power of k plus 2 end exponent end cell row blank equals cell 42 m minus 6 cross times 13 to the power of k plus 1 end exponent plus 13 cross times 13 to the power of k plus 1 end exponent end cell row blank equals cell 42 m plus left parenthesis negative 6 plus 13 right parenthesis cross times 13 to the power of k plus 1 end exponent end cell row blank equals cell 42 m plus 7 cross times 13 to the power of k plus 1 end exponent end cell end table

The goal is to show that this result is divisible by 7
Factorise out a 7 to show this

table row cell straight f left parenthesis k plus 1 right parenthesis end cell equals cell 7 cross times open parentheses 6 m plus 13 to the power of k plus 1 end exponent close parentheses end cell end table

State that it is true for n equals k plus 1

straight f open parentheses k plus 1 close parentheses is divisible by 7, so it is true for n equals k plus 1

STEP 4: The conclusion
We have just proved that if the case when n equals k is true, then the case when n equals k plus 1 is true
We have also shown that the case when n equals 0 is true
Those two parts come together to mean that n equals 0 is true, so n equals 1 is true, so n equals 2 is true, ... and so on

If it is true for n equals k, then it is true for n equals k plus 1.
As it is true for n equals 0, the statement is true for all integers n greater or equal than 0.

Proof by Induction with Sequences

What are the steps for proof by induction with sequences?

  • For example: prove that the sequence given recursively by u subscript n plus 1 end subscript equals 3 u subscript n plus 4 where u subscript 1 equals 1 has the nth term formula u subscript n equals 3 to the power of n minus 2 for n greater or equal than 1

  • STEP 1

    The basic step: Show result is true for bold italic n bold equals bold 1

    • Substitute n equals 1 into the formulae separately

    • u subscript 1 equals 1 from the recursive formula

    • u subscript 1 equals 3 to the power of 1 minus 2 equals 1 from the nth term formula

  • STEP 2

    The assumption step: Assume that the term u subscript k satisfies u subscript k equals 3 to the power of k minus 2 for some bold italic n bold equals bold italic k where k is some integer

    • Replace n with k 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 n equals k plus 1

    • Use the recursive formula to write u subscript k plus 1 end subscript equals 3 u subscript k plus 4

    • Substitute in the assumption (STEP 2) and simplify

      • u subscript k plus 1 end subscript equals 3 open parentheses 3 to the power of k minus 2 close parentheses plus 4 equals 3 to the power of k plus 1 end exponent minus 2

    • Check this is the same as the nth term formula when n equals k plus 1

      • u subscript k plus 1 end subscript equals 3 to the power of k plus 1 end exponent minus 2

      • 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 n equals k, then it is true for n equals k plus 1."

    • "As it is true for bold italic n bold equals bold 1, the statement is true for all n element of straight integer numbers to the power of plus."

Exam Tip

  • If the recursive formula involves the previous two terms, then the basic step must be done for both n equals 1 and n equals 2.

Worked Example

A sequence is defined by u subscript n plus 1 end subscript equals 5 u subscript n minus 4 where u subscript 1 equals 2 and n greater or equal than 1.

Prove by mathematical induction that u subscript n equals 5 to the power of n minus 1 end exponent plus 1, where n greater or equal than 1.

STE P 1: The basic step
Find u subscript 1 from the recursive sequence

u subscript 1 equals 2

Find u subscript 1 from the nth term formula

table row cell u subscript 1 end cell equals cell 5 to the power of 1 minus 1 end exponent plus 1 end cell row blank equals cell 5 to the power of 0 plus 1 end cell row blank equals cell 1 plus 1 end cell row blank equals 2 end table

These two terms are equal
State that it is true for n equals 1

It is true for n equals 1

STEP 2: The assumption step
Assume the formula is true for some n equals k where k is a positive integer

Assume that u subscript k equals 5 to the power of k minus 1 end exponent plus 1

STEP 3: The inductive step
Use the recursive sequence to write u subscript k plus 1 end subscript in terms of u subscript k

table row cell u subscript k plus 1 end subscript end cell equals cell 5 u subscript k minus 4 end cell end table

Replace u subscript k with the assumption in STEP 2 and simplify

table row cell u subscript k plus 1 end subscript end cell equals cell 5 open parentheses 5 to the power of k minus 1 end exponent plus 1 close parentheses minus 4 end cell row blank equals cell 5 to the power of k plus 5 minus 4 end cell row blank equals cell 5 to the power of k plus 1 end cell end table

Check that this is the same as substituting n equals k plus 1 into the nth term formula

table row cell u subscript k plus 1 end subscript end cell equals cell 5 to the power of open parentheses k plus 1 close parentheses minus 1 end exponent plus 1 end cell row blank equals cell 5 to the power of k plus 1 end cell end table

State that the result is true for n equals k plus 1

It is true for n equals k plus 1

STEP 4: The conclusion
We have just proved that if the case when n equals k is true, then the case when n equals k plus 1 is true
We have also shown that the case when n equals 1 is true
Those two parts come together to mean that n equals 1 is true, so n equals 2 is true, so n equals 3 is true, ... and so on

If it is true for n equals k, then it is true for n equals k plus 1.
As it is true for n equals 1, the statement is true for all n element of straight integer numbers to the power of plus.

Proof by Induction with Matrices

What are the steps for proof by induction with matrices?

  • For example: prove that bold M to the power of n equals open parentheses table row cell 2 to the power of n end cell 0 row cell 1 minus 2 to the power of n end cell 1 end table close parentheses where bold M equals open parentheses table row 2 0 row cell negative 1 end cell 1 end table close parentheses for all integers n greater or equal than 1.

  • STEP 1

    The basic step: Show result is true for bold italic n bold equals bold 1

    • Substitute n equals 1 into formula

    • bold M to the power of 1 equals end exponent open parentheses table row cell 2 to the power of 1 end cell 0 row cell 1 minus 2 to the power of 1 end cell 1 end table close parentheses equals open parentheses table row 2 0 row cell negative 1 end cell 1 end table close parentheses equals bold M

  • STEP 2

    The assumption step: Assume bold M to the power of k equals open parentheses table row cell 2 to the power of k end cell 0 row cell 1 minus 2 to the power of k end cell 1 end table close parentheses is true for some bold italic n bold equals bold italic k where k is some integer

    • Replace n with k in the statement

  • STEP 3

    The inductive step: You need to show that the n equals k plus 1 case is true

    • Use index laws to write bold M to the power of k plus 1 end exponent equals bold MM to the power of k

    • Substitute in the assumption: bold M to the power of k plus 1 end exponent equals bold M open parentheses table row cell 2 to the power of k end cell 0 row cell 1 minus 2 to the power of k end cell 1 end table close parentheses equals open parentheses table row 2 0 row cell negative 1 end cell 1 end table close parentheses open parentheses table row cell 2 to the power of k end cell 0 row cell 1 minus 2 to the power of k end cell 1 end table close parentheses

    • Multiply the matrices

      • bold M to the power of k plus 1 end exponent equals open parentheses table row cell 2 to the power of k plus 1 end exponent end cell 0 row cell 1 minus 2 cross times 2 to the power of k end cell 1 end table close parentheses equals open parentheses table row cell 2 to the power of k plus 1 end exponent end cell 0 row cell 1 minus 2 to the power of k plus 1 end exponent end cell 1 end table close parentheses

    • Check if it is the same as the formula with n equals k plus 1

      • bold M to the power of k plus 1 end exponent equals open parentheses table row cell 2 to the power of k plus 1 end exponent end cell 0 row cell 1 minus 2 to the power of k plus 1 end exponent end cell 1 end table close parentheses

      • 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 n equals k, then it is true for n equals k plus 1."

    • "As it is true for bold italic n bold equals bold 1, the statement is true for all n element of straight integer numbers to the power of plus."

Worked Example

The matrix bold M is given by bold M equals open parentheses table row 2 2 row 0 1 end table close parentheses.

Prove, using mathematical induction, that bold M to the power of n equals open parentheses table row cell 2 to the power of n end cell cell 2 left parenthesis 2 to the power of n minus 1 right parenthesis end cell row 0 1 end table close parentheses for all integers satisfying n greater or equal than 1.

STE P 1: The basic step
Prove that it is true for n equals 1

table row cell bold M to the power of 1 end cell equals cell open parentheses table row cell 2 to the power of 1 end cell cell 2 open parentheses 2 to the power of 1 minus 1 close parentheses end cell row 0 1 end table close parentheses end cell row blank equals cell open parentheses table row 2 2 row 0 1 end table close parentheses end cell row blank equals bold M end table

State that it is true for n equals 1

It is true for n equals 1

STEP 2: The assumption step
Assume the formula is true for some n equals k where k is a positive integer

Assume that bold M to the power of k equals open parentheses table row cell 2 to the power of k end cell cell 2 left parenthesis 2 to the power of k minus 1 right parenthesis end cell row 0 1 end table close parentheses

STEP 3: The inductive step
Look at the power of n equals k plus 1

table row blank blank cell bold M to the power of k plus 1 end exponent end cell end table

Use index laws, then substitute in the assumption from STEP 2

table row cell bold M to the power of k plus 1 end exponent end cell equals cell bold M to the power of k bold M to the power of bold 1 end cell row blank equals cell open parentheses table row cell 2 to the power of k end cell cell 2 left parenthesis 2 to the power of k minus 1 right parenthesis end cell row 0 1 end table close parentheses open parentheses table row 2 2 row 0 1 end table close parentheses end cell end table

Use matrix multiplication to work out the right-hand side
Simplify the terms

table row cell bold M to the power of k plus 1 end exponent end cell equals cell open parentheses table row cell 2 to the power of k cross times 2 plus 0 end cell cell space space 2 to the power of k cross times 2 plus 2 left parenthesis 2 to the power of k plus 1 end exponent minus 1 right parenthesis cross times 1 end cell row cell 0 plus 0 end cell cell 0 plus 1 end cell end table close parentheses end cell row blank equals cell open parentheses table row cell 2 to the power of k plus 1 end exponent end cell cell space space 2 cross times 2 to the power of k plus 1 end exponent minus 2 end cell row 0 1 end table close parentheses end cell end table

Check that this is the same as substituting n equals k plus 1 into the formula for bold M to the power of n

table row cell bold M to the power of k plus 1 end exponent end cell equals cell open parentheses table row cell 2 to the power of k plus 1 end exponent end cell cell 2 left parenthesis 2 to the power of k plus 1 end exponent minus 1 right parenthesis end cell row 0 1 end table close parentheses end cell row blank equals cell open parentheses table row cell 2 to the power of k plus 1 end exponent end cell cell 2 cross times 2 to the power of k plus 1 end exponent minus 2 end cell row 0 1 end table close parentheses end cell end table

State that the result is true for n equals k plus 1

It is true for n equals k plus 1

STEP 4: The conclusion
We have just proved that if the case when n equals k is true, then the case when n equals k plus 1 is true
We have also shown that the case when n equals 1 is true
Those two parts come together to mean that n equals 1 is true, so n equals 2 is true, so n equals 3 is true, ... and so on

If it is true for n equals k, then it is true for n equals k plus 1.
As it is true for n equals 1, the statement is true for all n element of straight integer numbers to the power of plus.

You've read 0 of your 0 free revision notes

Get unlimited access

to absolutely everything:

  • Downloadable PDFs
  • Unlimited Revision Notes
  • Topic Questions
  • Past Papers
  • Model Answers
  • Videos (Maths and Science)

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Did this page help you?

    Mark Curtis

    Author: Mark Curtis

    Mark graduated twice from the University of Oxford: once in 2009 with a First in Mathematics, then again in 2013 with a PhD (DPhil) in Mathematics. He has had nine successful years as a secondary school teacher, specialising in A-Level Further Maths and running extension classes for Oxbridge Maths applicants. Alongside his teaching, he has written five internal textbooks, introduced new spiralling school curriculums and trained other Maths teachers through outreach programmes.