Intro 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 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
- In the dominoes analogy this is showing that the first domino falls down
- STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
- In the dominoes analogy this is assuming that a random domino falls down
- 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
- The assumption from STEP 2 will be needed at some point
- In the dominoes analogy this is showing that the random domino that we assumed falls down will cause the next one to fall down
- 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?
- There are 4 main applications that you could be asked
- Formulae for sums of series
- Formulae for recursive sequences
- Expression for the power of a matrix
- Showing an expression is always divisible by a specific value
- Induction is always used to prove de Moivre's theorem
- It is unlikely that you will be asked unfamiliar applications in your exam but induction is used in other areas of maths
- Proving formulae for nth derivative of functions
- Proving formulae involving factorials