Revision NotesExam QuestionsPast Papers
A LevelFurther MathsEdexcelCore PureRevision NotesProofProof by InductionCommon Cases of Proof by Induction

Common Cases of Proof by Induction (Edexcel A Level Further Maths): Revision Note

Dan Finlay

Last updated

Proof by Induction - Sequences

What are the steps for proof by induction with sequences?

  • STEP 1: The basic step

    • Show the result is true for the base case

      • If the recursive relation formula for the next term involves the previous two terms then you need to show the position-to-term formula works the first two given terms which will be given as part of the definition of the sequence

    • This is normally n = 1 or 0 but it could be any integer

      • For example: To prove u subscript n equals 3 to the power of n minus 2 is the position-to-term formula for the recursive sequence u subscript n plus 1 end subscript equals 3 u subscript n plus 4 comma space u subscript 1 equals 1: 

      • u subscript 1 equals 3 to the power of 1 minus 2 equals 1

  • STEP 2: The assumption step

    • Assume the result is true for n = k for some integer k

      • For example: Assume u subscript k equals 3 to the power of k minus 2 is true

    • There is nothing to do for this step apart from writing down the assumption

  • STEP 3: The inductive step

    • Using the assumption show the result is true for n = k + 1

    • It can be helpful to write down what you want to show

    • The assumption from STEP 2 will be needed at some point

      • For example:  Want to show u subscript k plus 1 end subscript equals 3 to the power of k plus 1 end exponent minus 2

    • The trick to this step is to use the recursive relation formula:

      • u subscript k plus 1 end subscript equals 3 u subscript k plus 4

  • STEP 4: The conclusion step

    • State the result is true

    • Explain in words why the result is true

    • It must include:

      • If true for n = k then it is true for n = k + 1

      • Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1  by mathematical induction

    • The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

A sequence is defined by u subscript n plus 1 end subscript equals 5 u subscript n minus 4 comma space u subscript 1 equals 2 for 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 for n greater or equal than 1.

9-1-2-edexcel-al-fm-cp-proof-by-induction-sequences-we

Proof by Induction - Series

What are the steps for proof by induction with series?

  • STEP 1: The basic step

    • Show the result is true for the base case

    • This is normally n = 1 or 0 but it could be any integer

      • For example: To prove 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 is true for all integers n ≥ 1 you would first need to show it is true for n = 1: 

      • sum from r equals 1 to 1 of r squared equals 1 over 6 left parenthesis 1 right parenthesis left parenthesis left parenthesis 1 right parenthesis plus 1 right parenthesis left parenthesis 2 left parenthesis 1 right parenthesis plus 1 right parenthesis

  • STEP 2: The assumption step

    • Assume the result is true for n = k for some integer k

      • For example: 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

    • There is nothing to do for this step apart from writing down the assumption

  • STEP 3: The inductive step

    • Using the assumption show the result is true for n = k + 1

    • It can be helpful to simplify LHS & RHS separately and show they are identical

    • The assumption from STEP 2 will be needed at some point

      • For example: L H S equals sum from r equals 1 to k plus 1 of r squared and R H S equals 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

    • The trick to this step is to use:

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

  • STEP 4: The conclusion step

    • State the result is true

    • Explain in words why the result is true

    • It must include:

      • If true for n = k then it is true for n = k + 1

      • Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1  by mathematical induction

    • The sentence will be the same for each proof just change the base case from n = 1 if necessary

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.

1-5-1-ib-aa-hl-proof-by-induction-we-solution

Proof by Induction - Divisibility

What are the steps for proof by induction with series?

  • STEP 1: The basic step

    • Show the result is true for the base case

    • This is normally n = 1 or 0 but it could be any integer

      • For example: To prove f left parenthesis n right parenthesis equals 4 to the power of n minus 1 is divisible by 3 for all integers n ≥ 1 you would first need to show it is true for n = 1: 

      • f left parenthesis 1 right parenthesis equals 4 minus 1 equals 3 equals 3 left parenthesis 1 right parenthesis

  • STEP 2: The assumption step

    • Assume the result is true for n = k for some integer k

      • For example: Assume f left parenthesis k right parenthesis equals 4 minus 1 is divisible by 3

    • There is nothing to do for this step apart from writing down the assumption

    • The trick for this step is to write the expression as a multiple of the number

      • For example: 4 to the power of k minus 1 equals 3 p for some integer p

  • STEP 3: The inductive step

    • Using the assumption show the result is true for n = k + 1

    • The assumption from STEP 2 will be needed at some point

      • For example: Show that f left parenthesis k plus 1 right parenthesis equals 4 to the power of k plus 1 end exponent minus 1 is divisible by 3

    • The trick to this step is to use:

a to the power of k plus 1 end exponent equals a cross times a to the power of k

  • For example: f left parenthesis k plus 1 right parenthesis equals 4 left parenthesis 4 to the power of k right parenthesis minus 1 equals 4 left parenthesis 1 plus 3 p right parenthesis minus 1 equals 3 left parenthesis p plus 1 right parenthesis

    • Another trick is to show that f left parenthesis k plus 1 right parenthesis minus f left parenthesis k right parenthesis is divisible by the number

    • Be careful with numbers like 6 as for these you can instead show it is divisible by both 3 and 2

  • STEP 4: The conclusion step

    • State the result is true

    • Explain in words why the result is true

    • It must include:

      • If true for n = k then it is true for n = k + 1

      • Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1  by mathematical induction

    • The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

Prove by induction that 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 n greater or equal than 0.

9-1-2-edexcel-al-fm-cp-proof-by-induction-divisibility-we

Proof by Induction - Matrices

What are the steps for proof by induction with matrices?

  • STEP 1: The basic step

    • Show the result is true for the base case

    • This is normally n = 1 but it could be any integer

      • For example: To prove bold italic 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 italic M equals open parentheses table row 2 0 row cell negative 1 end cell 1 end table close parentheses for n greater or equal than 1: 

      • 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

  • STEP 2: The assumption step

    • Assume the result is true for n = k for some integer k

      • For example: Assume bold italic 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

    • There is nothing to do for this step apart from writing down the assumption

  • STEP 3: The inductive step

    • Using the assumption show the result is true for n = k + 1

    • It can be helpful to write down what you want to show

    • The assumption from STEP 2 will be needed at some point

      • For example:  Want to show bold italic M to the power of k 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

    • The trick to this step is to use write:

      • bold italic M to the power of k plus 1 end exponent equals bold italic M bold italic M to the power of bold k

      • The entries in the matrix can get messy so it can be clearer to write bold italic M to the power of k plus 1 end exponent equals open parentheses table row a b row c d end table close parentheses and then find expressions for a, b, c, d on separate lines

  • STEP 4: The conclusion step

    • State the result is true

    • Explain in words why the result is true

    • It must include:

      • If true for n = k then it is true for n = k + 1

      • Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1  by mathematical induction

    • The sentence will be the same for each proof just change the base case from n = 1 if necessary

Worked Example

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

Prove, using mathematical induction, that bold italic 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.

9-1-2-edexcel-al-fm-cp-proof-by-induction-matrices-we

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

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

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:Intro to Proof by Induction
    Dan Finlay

    Author: Dan Finlay

    Expertise: Maths Lead

    Dan graduated from the University of Oxford with a First class degree in mathematics. As well as teaching maths for over 8 years, Dan has marked a range of exams for Edexcel, tutored students and taught A Level Accounting. Dan has a keen interest in statistics and probability and their real-life applications.