# Mathematical induction · Grade 11 · 5 units

> Mathematical induction, Grade 11 · 5 units: The base case and more. Explanation, worked examples and free practice following the Israeli curriculum.

In Mathematical induction (Grade 11 · 5 units) you practise 6 skills: The base case · The induction hypothesis and the claim · The inductive step · Arguments that are not a proof · Sequences given by a recurrence · Induction in a picture.

Mathematical induction is a third method of proof, after the direct proof and the proof by contradiction. It suits a claim about every natural number, and it proves two things: that the claim holds for the number one, which is the base case, and that if it holds for some natural number, it holds for the next one too, which is the inductive step. From the two together the claim holds for every natural number, like a row of dominoes: the first one falls, and each domino knocks the next one over.

A sequence is a function on the natural numbers, so the term in a given place can also be written as the value of a function at that place. A sequence can be given by place or by a recurrence, and induction proves that the two give the same sequence.

The step proves a sentence of the form “if this, then that”: assume the claim holds for some natural number, and show it holds for the next one too. Proving such a sentence does not need the assumption to be true: the hypothesis is a working tool, not a claim already proved. The claim for every natural number is never assumed: it is the conclusion.

A model proof: the sum of the squares of the numbers from one to n equals n times n plus one times two n plus one, divided by six. The base case: for one, the left side is one, and the right side is one times two times three divided by six, which is one as well. The inductive step: assume the claim holds for some natural number k, and add k plus one squared to both sides. On the right, take k plus one out as a common factor, and what is left is two k squared plus seven k plus six, divided by six. That is k plus two times two k plus three, divided by six, which is exactly the claim for k plus one. And so the claim holds for every natural number n.

A model proof: one sequence is given by place, and its term in place n is n squared plus two n. A second sequence is given by a recurrence: its first term is three, and each term is the one before plus twice the place before plus three. The claim is that they are the same sequence. The base case: in the first place, the first sequence gives one plus two, which is three, and the second gives three. The inductive step: assume that in some place k the term of the second sequence is k squared plus two k. By the recurrence, its next term is k squared plus four k plus three, which is k plus one squared plus twice k plus one: the term of the first sequence in place k plus one. And so the claim holds for every place n, and the two sequences are the same.

A model proof: a sequence has first term six, and each term is the one before plus two n cubed plus three n squared plus n, where n is the place before. The claim is that every term of the sequence is divisible by six. The base case: the first term is six, which is divisible by six. The inductive step: assume the term in some place k is divisible by six. The difference between it and the next term is two k cubed plus three k squared plus k, which is k times k plus one times two k plus one: by the first proof, six times the sum of the squares from one to k. So the difference is divisible by six too, and the sum of two numbers divisible by six is divisible by six. And so the claim holds for every term of the sequence.

A model proof: n lines in the plane, no two of them parallel and no three through one point. The claim is that they cut the plane into one plus n times n plus one divided by two parts. The base case: one line cuts the plane into two parts, and one plus one times two divided by two is two. The inductive step: assume that k such lines cut the plane into one plus k times k plus one divided by two parts. A new line crosses each of them at a different point, so it passes through k plus one parts and cuts each of them into two. That adds k plus one parts, giving one plus k plus one times k plus two divided by two: the claim for k plus one. And so the claim holds for every natural number of lines.

Induction also proves the power rule: the derivative of x to the power n is n times x to the power n minus one. For one, the derivative of x is one. In the step, write x to the power k plus one as x to the power k times x, and use the product rule: k times x to the power k minus one, times x, plus x to the power k. That is k plus one times x to the power k.

The claim that n cubed minus n is divisible by six can be proved in two ways. By induction: for one it gives zero, and in the step the difference between two consecutive cases is three times k times k plus one. The product of two consecutive numbers is even, so the difference is divisible by six. Without induction: n cubed minus n is the product of three consecutive numbers, n minus one, n and n plus one, and among three consecutive numbers there is always an even number and a number divisible by three.

A wrong argument: the claim is that the sum of the numbers from one to n equals n squared plus n plus one, divided by two. The inductive step is correct: adding k plus one to both sides gives the claim for k plus one. But for one the left side is one and the right side is three halves. Without a base case the step proves nothing, and the claim is false for every n.

A wrong argument: one sequence has first term two, and each term is twice the one before. A second sequence has first term two, and each term is the one before plus twice the place before. In both, the first three terms are two, four and eight, so it was concluded that the sequences are the same. But the fourth term of the first is sixteen, and of the second fourteen. Some cases that agree are not a proof: the inductive step is missing.

A wrong argument: the claim is that in every group of horses, all the horses are the same colour. For the base case, one horse is one colour. For the step, take one horse out of a group of k plus one horses, and the rest are the same colour. Put it back and take out another, and again the rest are the same colour, and the two groups share horses. The step breaks in going from one horse to two: then each group is a single horse, and the two share none. A step must hold for every k, the first one included.

**Tip:** In every proof by induction, write the three parts by name: the base case, the step and the conclusion. In the step, say clearly what is assumed and what is shown.

## What you learn

### The base case

- Example: The claim that 1 + 2 + … + n equals n(n + 1) ÷ 2 for every natural number n is proved by induction. What is the value of the right side when n = 1 ?
- Answer: 1
- Solution: The left side: 1 = 1 . The right side: 1 × 2 ÷ 2 = 1 . The two sides are equal. Checking the base case is a part of the proof, not just an example.

### The induction hypothesis and the claim

- Example: It is proved by induction that 1 + 2 + … + n = n(n + 1) ÷ 2 for every natural number n . What is the induction hypothesis in the step?
- Options: The claim holds for every natural number n · The claim holds for k + 1 · The claim holds for n = 1 · The claim holds for some natural number k
- Answer: The claim holds for some natural number k
- Solution: The induction hypothesis is that the claim holds for some natural number k . Assume that, and show the claim holds for k + 1 too. The claim for every n is not assumed: it is what is proved, the conclusion. The hypothesis is only a part of the step.

### The inductive step

- Example: A sequence has b₁ = 2 and bₖ₊₁ = bₖ + 2k + 2 . It is proved by induction that bₙ = n² + n , and the step assumes bₖ = k² + k . What is bₖ₊₁ equal to?
- Options: k² + k + 2 · k² + 3k · k² + k · k² + 3k + 2
- Answer: k² + 3k + 2
- Solution: Put it in: bₖ₊₁ = k² + k + 2k + 2 = k² + 3k + 2 . That is exactly (k + 1)² + (k + 1) : the claim for k + 1 .

### Arguments that are not a proof

- Example: A proof by induction that 1 + 2 + … + n equals (n² + n + 1) ÷ 2 for every natural number n assumed the claim for k , showed with correct working that it holds for k + 1 too, and concluded it holds for every n . What is missing from the proof?
- Options: The inductive step · The conclusion · Nothing: the proof is complete · The base case
- Answer: The base case
- Solution: The base case is missing, and without it the step proves nothing. Indeed, for n = 1 : the left side is 1 and the right side 3/2 , so the claim fails at the very first case.

### Sequences given by a recurrence

- Example: A sequence has a₁ = 2 and aₙ₊₁ = aₙ + 2n³ + 2n . What is a₄ ?
- Answer: 86
- Solution: One term at a time: a₂ = 2 + 4 = 6 , a₃ = 6 + 20 = 26 , a₄ = 26 + 60 = 86 .

### Induction in a picture

- Example: The picture shows one line. How many parts does it cut the plane into? (one line on a grid)
- Answer: 2
- Solution: Line k crosses the k − 1 lines before it, so it passes through k parts and adds k parts: Lₖ = Lₖ₋₁ + k . So L₁ = 1 + 1 = 2 .

## Not on the site yet

- Writing a proof by induction yourself (guided reading: four model proofs in the explanation)
- Proving the power rule by induction (reading)
- De Moivre’s theorem

The exercises are made by rules and the answers are worked out in code. The topic follows the Israeli Ministry of Education’s high school maths curriculum at 5 units (grades 10 to 12).

[Practise on the site](https://kixplo.com/il/en/) · [All Grade 11 · 5 units topics](https://kixplo.com/il/en/math/grade-11-5u/)