# Edexcel A Level Further Maths: Core Pure:复习笔记9.1.1 Intro to Proof by Induction

### 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

### Proving de Moivre's Theorem by Induction

#### How is de Moivre’s Theorem proved?

• When written in Euler’s form the proof of de Moivre’s theorem is easy to see:
• Using the index law of brackets:
• However Euler’s form cannot be used to prove de Moivre’s Theorem when it is in modulus-argument (polar) form
• Proof by induction can be used to prove de Moivre’s Theorem for positive integers:
• To prove de Moivre’s Theorem for all positive integers, n
• STEP 1: Prove it is true for n = 1
• So de Moivre’s Theorem is true for n = 1
• STEP 2: Assume it is true for n = k
• STEP 3: Show it is true for n = k + 1
• According to the assumption this is equal to
• Using laws of indices and multiplying out the brackets:
• =
• Letting i2 = -1 and collecting the real and imaginary parts gives:
• =
• Recognising that the real part is equivalent to cos(kθ  + θ ) and the imaginary part is equivalent to sin(kθ  + θ ) gives
• =
• So de Moivre’s Theorem is true for n = k + 1
• STEP 4: Write a conclusion to complete the proof
• The statement is true for n = 1, and if it is true for n = k it is also true for n = k + 1
• Therefore, by the principle of mathematical induction, the result is true for all positive integers, n
• De Moivre’s Theorem works for all real values of n
• However you could only be asked to prove it is true for positive integers

#### Worked Example

Show, using proof by mathematical induction, that for a complex number   and for all positive integers, n,