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

Revision Note

Test yourself
Dan

Author

Dan

Last updated

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: open parentheses r straight e to the power of straight i theta end exponent close parentheses to the power of n equals blank r to the power of n straight e to the power of straight i n theta end exponent
  • 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 square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of n equals r to the power of n left parenthesis cos invisible function application n theta plus isin invisible function application n theta right parenthesis
  • STEP 1: Prove it is true for n = 1
    • left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of 1 equals r to the power of 1 left parenthesis cos invisible function application 1 theta plus isin invisible function application 1 theta right parenthesis equals blank r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis blank
    • So de Moivre’s Theorem is true for n = 1
  • STEP 2: Assume it is true for n = k
    • left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of k equals r to the power of k left parenthesis cos invisible function application k theta plus isin invisible function application k theta right parenthesis blank
  • STEP 3: Show it is true for n = k + 1
    • left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of k plus blank 1 end exponent equals left parenthesis left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of k right parenthesis left parenthesis left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of 1 right parenthesis blank
    • According to the assumption this is equal to
      • left parenthesis r to the power of k left parenthesis cos invisible function application k theta plus isin invisible function application k theta right parenthesis right parenthesis blank left parenthesis r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right parenthesis
    • Using laws of indices and multiplying out the brackets:
      • equals blank r to the power of k plus 1 end exponent left square bracket cos invisible function application k theta cos invisible function application theta plus icos space k theta space sin invisible function application theta plus isin invisible function application k theta cos invisible function application theta plus straight i squared sin invisible function application k theta sin invisible function application theta right square bracket
    • Letting i2 = -1 and collecting the real and imaginary parts gives:
      • equals blank r to the power of k plus 1 end exponent left square bracket cos invisible function application k theta cos invisible function application theta minus sin invisible function application k theta sin invisible function application theta plus straight i left parenthesis cos space k theta space sin invisible function application theta plus sin invisible function application k theta cos invisible function application theta right parenthesis right square bracket
    • Recognising that the real part is equivalent to cos( + θ ) and the imaginary part is equivalent to sin( + θ ) gives
      • r to the power of k plus 1 end exponent left square bracket cos invisible function application open parentheses k plus 1 close parentheses theta plus isin invisible function application invisible function application open parentheses k plus 1 close parentheses theta right square bracket blank
    • 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 z equals r left parenthesis cos theta plus isin theta right parenthesis  and for all positive integers, n,

z to the power of n space equals space left square bracket r blank left parenthesis cos invisible function application theta plus isin invisible function application theta right parenthesis right square bracket to the power of n blank equals r to the power of n left parenthesis cos invisible function application n theta plus isin invisible function application n theta right parenthesis

1-9-3-ib-aa-hl-proof-of-de-moivres-theorem-we-solution

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

Dan

Author: Dan

Expertise: Maths

Dan graduated from the University of Oxford with a First class degree in mathematics. As well as teaching maths for over 8 years, Dan has marked a range of exams for Edexcel, tutored students and taught A Level Accounting. Dan has a keen interest in statistics and probability and their real-life applications.