Intro to Proof by Induction (Edexcel A Level Further Maths: Core Pure): Revision Note

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: ${{\left(r{\mathrm{e}}^{\mathrm{i}\theta }\right)}^n= r}^n{\mathrm{e}}^{\mathrm{i}n\theta }$

• 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

  • $\left[r \right(\cos \theta +\mathrm{isin}\theta ){]}^n=r^n(\cos n\theta +\mathrm{isin}n\theta )$

• STEP 1: Prove it is true for n = 1

  • $\left[r \right(\cos \theta +\mathrm{isin}\theta ){]}^1=r^1(\cos 1\theta +\mathrm{isin}1\theta )= r (\cos \theta +\mathrm{isin}\theta )$

  • So de Moivre’s Theorem is true for n = 1

• STEP 2: Assume it is true for n = k

  • $\left[r \right(\cos \theta +\mathrm{isin}\theta ){]}^k=r^k(\cos k\theta +\mathrm{isin}k\theta )$

• STEP 3: Show it is true for n = k + 1

  • $\left[r \right(\cos \theta +\mathrm{isin}\theta ){]}^{k+ 1}=\left(\right[r (\cos \theta +\mathrm{isin}\theta ){]}^k\left)\right(\left[r \right(\cos \theta +\mathrm{isin}\theta \left){]}^1\right)$

  • According to the assumption this is equal to

    • $\left(r^k\right(\cos k\theta +\mathrm{isin}k\theta \left)\right) \left(r \right(\cos \theta +\mathrm{isin}\theta \left)\right)$

  • Using laws of indices and multiplying out the brackets:

    • $= r^{k+1}[\cos k\theta \cos \theta +\mathrm{icos}k\theta \sin \theta +\mathrm{isin}k\theta \cos \theta +{\mathrm{i}}^2\sin k\theta \sin \theta ]$

  • Letting i² = -1 and collecting the real and imaginary parts gives:

    • $= r^{k+1}[\cos k\theta \cos \theta -\sin k\theta \sin \theta +\mathrm{i}(\cos k\theta \sin \theta +\sin k\theta \cos \theta )]$

  • Recognising that the real part is equivalent to cos(kθ  + θ ) and the imaginary part is equivalent to sin(kθ  + θ ) gives

    • $r^{k+1}[\cos \left(k+1\right)\theta +\mathrm{isin}\left(k+1\right)\theta ]$

  • 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