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

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 falling dominoes

  • Assuming some domino falls

    • the assumption step

  • you need to show it causes (induces) the next domino to fall

    • the induction step

  • If you can also show that the first domino falls

    • the basic step

  • then putting together the above mean that all dominoes will fall!

    • the conclusion step

What are the steps for proof by induction with series?

• For example: prove that for all

  • 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 and show they are equal

    

• 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

    • It helps to take the last term out:

    • Now substitute in the assumption (from step 2) :

    • 

    • Expand and 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 positive 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 ."

What are the steps for proof by induction with divisibility?

• For example: prove that is divisible by 3 for all positive integers

  • 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

  • This is because rearranges to

  • So is divisible by 3 (as long as the assumption is true, i.e. that is divisible by 3)

  • This method is not always that practical

    • When it is, a hint will be given

• 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 ."

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

• You may be asked to use proof by induction in the following contexts

  • Series (see above)

    • Some useful tricks are

      • writing for the inductive step

      • writing if factorials are involved

  • Divisibility (see above)

    • A useful trick for the inductive step is using 

  • Complex numbers

    • You can prove de Moivre’s theorem by induction

  • Derivatives

    • These may involve the chain, product and quotient rule

    • A useful trick for the inductive step is using