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

    • 

• STEP 2: The assumption step

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

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

• 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  is useful

  • These can be written in the form 

  • A useful trick for the inductive step is using 

• Divisibility of an expression by an integer

  • These can be written in the form  where m & q_n are integers

  • A useful trick for the inductive step is using 

• 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 

  • A useful trick for the inductive step is using 

  • You will have to use the differentiation rules