Proof by Induction (Edexcel International AS Further Maths)

Introduction to 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:

  • Assume one domino falls

    • The assumption step

  • Show that if this domino falls, the next domino falls

    • The inductive step

• If you want all dominoes to fall (from the beginning) then

  • Show also that the first domino falls

    • The basic step

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 or

• STEP 2
  The assumption step: Assume the result is true for where is some integer

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

• STEP 3
  The inductive step: Use the assumption to show the result is true for

  • This involves investigating and bringing in the assumption

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