Proof by Induction (DP IB Analysis & Approaches (AA)) : Revision Note

Dan Finlay

Last updated

Did this video help you?

Proof by Induction

What is proof by induction?

  • Proof by induction is a way of proving a result is true for a set of integers by showing that if it is true for one integer then it is true for the next integer

  • It can be thought of as dominoes:

    • All dominoes will fall down if:

      • The first domino falls down

      • Each domino falling down causes the next domino to fall down

What are the steps for proof by induction?

  • 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

  • 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

What type of statements might I be asked to prove by induction?

  • Sums of sequences

    • If the terms involve factorials then open parentheses k plus 1 close parentheses factorial equals open parentheses k plus 1 close parentheses cross times open parentheses k factorial close parentheses is useful

    • These can be written in the form sum from r equals 1 to n of f open parentheses r close parentheses equals g open parentheses n close parentheses

    • A useful trick for the inductive step is using 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

  • Divisibility of an expression by an integer

    • These can be written in the form f open parentheses n close parentheses equals m cross times q subscript n where m & qn are integers

    • A useful trick for the inductive step is using a to the power of k plus 1 end exponent equals a cross times a to the power of k

  • Complex numbers

    • You can use proof by induction to prove de Moivre’s theorem

  • Derivatives

    • Such as chain rule, product rule & quotient rule

    • These can be written in the form f to the power of open parentheses n close parentheses end exponent open parentheses x close parentheses equals g open parentheses x close parentheses

    • A useful trick for the inductive step is using f to the power of open parentheses k plus 1 close parentheses end exponent open parentheses x close parentheses equals fraction numerator d over denominator d x end fraction open parentheses f to the power of open parentheses k close parentheses end exponent open parentheses x close parentheses close parentheses

    • You will have to use the differentiation rules

Examiner Tips and Tricks

  • Learn the steps for proof by induction and make sure you can use the method for a number of different types of questions before going into the exam

  • The trick to answering these questions well is practicing the pattern of using each step regularly 

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
👀 You've read 1 of your 5 free revision notes this week
An illustration of students holding their exam resultsUnlock more revision notes. It's free!

By signing up you agree to our Terms and Privacy Policy.

Already have an account? Log in

Did this page help you?

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.

Download notes on Proof by Induction