# proof by induction (HL)

**Proof by mathematical induction** is only in the HL course (not in SL) - and is the only formal proof method in the HL syllabus. Generally speaking, students do not have much experience (often none at all) in writing a formal proof for a mathematical statement. For this reason - and also since students are often confused about precisely how a mathematical induction proof works - proof by induction is very often one of the types of exam questions on which students perform poorly.

I think that this poor performance on questions involving proof by mathematical induction can be addressed by the teacher striving to teach this method of proof as clearly and consistently as possible - and to provide a wide variety of examples of proofs. It is also important to have students regularly practice mathematical induction proofs.

__3 questions__ - ‘accessible’ to ‘discriminating’

__3 questions__-

download: 3_Qs_induction_proof_1_with_solutions

#### Course planning / teaching notes:

Typically **proof by mathematical induction** is presented as a **two-step process**: (1) **initial step**, and (2) **inductive step**. In essence, this is true - the principle of mathematical induction, at its simplest, has two parts - and either part can be completed first. However, when teaching proof by induction to secondary students it is wise to keep it as simple as possible so the part usually referred to as the initial step should always be completed first. The two parts are:

**(1) The statement is shown to be true for some positive integer *** n. *For most induction proofs, the initial step consists of showing the statement is true for

*n*=1. However, it does not have to be for

*n*=1. The statement can be shown to be true for any positive integer

*n=a*, but when the proof is completed the statement is not proven for all positive integers, but only all positive integers greater than or equal to

*a.*It is rare for a Math HL exam question to require a student to determine on their own that the initial step should be for an initial value other than

*n*=1. If an initial value other than

*n*=1 is required than the instructions will make that clear and almost certainly indicate what the initial value should be.

(2) Given the assumption that the statement is true for a positive integer greater than the initial value - call this value

*n=k*- then it needs to be shown that it logically follows from this assumption that the statement must then be true for

*n=k*+1.

These two parts put together make up the principle of mathematical induction.

To help students organize a well-constructed induction proof, I always break the 2nd part (the inductive step) into two parts. Firstly, write out the assumption for some *n=k; *and, secondly, show that it then follows that the statement must be true for *n=k*+1. And then I also emphasize to students that they need to write a brief (but not too brief) concluding statement to the proof which summarizes that the requirements of mathematical induction have been satisfied which proves that the statement is true for all positive integers greater than or equal to the initial value (usually *n*=1).

Thus, I explain to students that they need to complete **four steps for a proof by mathematical induction**:

**step 1**: inductive step [show statement true for *n*=1]

**step 2**: assume the statement is true for some specific positive integer *n=k* [and write this assumption symbolically]

**step 3**: show that using this assumption it follows that the statement must be true for *n=k*+1 [always some algebra needed here]

**step 4**: write a brief concluding statement to the proof

math_induction_example_1 - thorough proof of "accessible HL question" above (#1) - student handout

math_induction_example_2 - thorough proof of **de Moivre's theorem** by induction - student handout