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

  • <img alt=”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” data-mathml='<math ><semantics><mrow><mo>[</mo><mi>r</mi><mi> </mi><mo>(</mo><mi>cos</mi><mo>⁡</mo><mi>θ</mi><mo>+</mo><mi>isin</mi><mo>⁡</mo><mrow><mi>θ</mi><mo>)</mo><msup><mo>]</mo><mn>1</mn></msup></mrow><mo>=</mo><msup><mi>r</mi><mn>1</mn></msup><mo>(</mo><mi>cos</mi><mo>⁡</mo><mn>1</mn><mi>θ</mi><mo>+</mo><mi>isin</mi><mo>⁡</mo><mrow><mn>1</mn><mi>θ</mi><mo>)</mo><mo>=</mo><mi> </mi></mrow><mi>r</mi><mi> </mi><mo>(</mo><mi>cos</mi><mo>⁡</mo><mi>θ</mi><mo>+</mo><mi>isin</mi><mo>⁡</mo><mrow><mi>θ</mi><mo>)</mo><mi> </mi></mrow></mrow><annotation encoding=”application/vnd.wiris.mtweb-params+json”>{“language”:”en”,”fontFamily”:”Times New Roman”,”fontSize”:”18″}</annotation></semantics></math>’ height=”23″ role=”math” src=”data:image/svg+xml;charset=utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Awrs%3D%22http%3A%2F%2Fwww.wiris.com%2Fxml%2Fmathml-extension%22%20height%3D%2223%22%20width%3D%22415%22%20wrs%3Abaseline%3D%2217%22%3E%3C!–MathML%3A%20%3Cmath%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F1998%2FMath%2FMathML%22%3E%3Cmo%3E%5B%3C%2Fmo%3E%3Cmi%3Er%3C%2Fmi%3E%3Cmi%3E%26%23xA0%3B%3C%2Fmi%