(Here is a useful discussion about difficulties with proofs by induction)

NEW WORKBOOK ON PROOFS BY INDUCTION (2017 syllabus, PDF)

NEW WORKBOOK ON PROOFS BY INDUCTION (2017 syllabus, .doc)

**Explore how to solve maths and logic problems problems step-by-step**

**HOTELS, YAWNS, NUMBERS ON THE BOARD** (from workbook)

**QUICKER HOMEWORK** (on whiteboards, in pairs)

This week your Further Maths homework takes you 8 hours. But then each week you become twice as quick with your homework. You want to calculate your total homework time over 5 weeks, and then a formula for total homework time over n weeks.

Do it this way: make a table

Read off the total homework time after 5 weeks from the table.

Find a pattern in the “total homework time” column, and guess a formula for total homework time over n weeks.

See if you can prove that this formula remains true however big n becomes.

**THE TOWER OF HANOI**

Equipment: four Tower of Hanoi sets

How many moves to get all the discs from one spike onto another, if you can only move one disc at a time, and you must never put a bigger disc on top of a smaller one? What’s the general rule for a Tower of Hanoi with *n* discs?

Hint: find the number of moves you need for *one* disc; then the number of moves you need for *two* discs; then the number of moves you need for *three* discs

Then a general rule to get the number of moves you need for *n+1* discs from the number of moves you need for *n* discs

Make a table of number of discs and number of moves needed. Look at patterns in the table, and make a guess for a rule to tell you directly the number of moves needed for *100* discs (without having to work it out step by step, number needed for 1 then number needed for 2 then number needed for 3 then number needed by 4…)

**OUR FIRST INDUCTION PROOF**

**Do now**: On whiteboards, in pairs. Do a table of the first five triangle numbers, 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5. Can you guess a formula for the *n*th triangle number? Can you *prove* it?

**ALGEBRA AND INDEX RULES**

**Do now:**Write down the rules for multiplying and dividing powers, and the rules for factorising in algebra.

Index rules from year 11, and methods of taking out common factors, which we will need for proofs by induction and for our work with series.

Examples: 4^{(n+1)} = ____ × 4^{n} ≠ 16^{n}

¼n^{2}(n+1)^{2} + ½n(n+1) = ¼ n(n+1) [n(n+1)+2]

Rule: never expand unless you have to, take out the common factor when you can.

Worksheet on algebra and index rules (from workbook)

Video and worksheets on taking out common factors.

**GETTING USED TO PROOF BY INDUCTION**

**Do now:** ONE: Write your “Student Response” on your homework record sheet. TWO: If you mark two points on the circumference of a circle, and join them, that creates **2 regions**. If you mark three points, and join every pair of points, that creates **4 regions**. If you mark four points and join every pair – **8 regions**. With five points – a maximum of **16 regions**. *With six points, you get 31 regions*. Write on your whiteboard a reason why is this surprising, and a thing that the surprise teaches us.

THREE: Make a table of these totals:

1^{3}

1^{3}+2^{3}

1^{3}+2^{3}+3^{3}

1^{3}+2^{3}+3^{3}+4^{3}

1^{3}+2^{3}+3^{3}+4^{3}+5^{3}

Compare the totals you get with the triangle numbers. Write on your whiteboards what pattern you see here.

**We will then go through, in class, how to prove this pattern holds for all numbers.**

Revisit algebra facts.

**Another example of proof by induction**

If we count faces, vertices, and edges, we get a rule: faces + vertices = edges + 2

For example, a Nielsen football has 32 faces and 60 vertices and 90 edges. 32+60 = 90+2

We will prove that this is true for all spheres (or shapes that can be squashed or squeezed into spheres) by induction on the number of edges.

Step 1: prove it’s true for number of edges = 1

Step 2: prove that if it’s true for number of edges = k, then it’s true for number of edges = k+1

(for example, if it’s true for every case with 1765 edges, then it’s also true for every case with 1766).

We will also learn two symbols

⇒ means “implies”, so A ⇒ B means if A is true, then B is true

It rains ⇒ things get wet

n is even and three divides exactly into n ⇒ six divides exactly into n

n is even ⇒ (n+1) is odd

▇ means “Proof finished”

**PROOFS BY INDUCTION, DOMINO EFFECTS, AND CHAIN REACTIONS**

Pdf on difference between chain reactions and induction

Video of domino chain-reaction

Proof by induction is different from everyday chain reactions in three ways.

**100% logical**. We must have 100% logically certain proof that the claim will be true for n equal to k+1*if*it is true for n equal to k. In everyday chain reactions, the disease is never quite 100% infectious, the placing of the dominos never 100% accurate, the inflammability of the trees never quite 100%, the collapsibility of the building not quite 100%. It may be 99.9%, but not 100%. In maths it is 100%.**Infinite**. Every population which catches a disease, or set of dominos, or forest, or building, is finite. In maths, the “chain reaction” is infinite. If the claim is true for n=1, it is true for n=2. If true for n=2, it is true for n=3. If true for n=3, it is true for n=4… and so on*to infinity*.**Instantaneous**. In everyday chain reactions, there is a time factor. It takes time for the disease to spread, or the dominos to fall, and so on. In mathematical induction there is no “time factor”. When we**[1]**prove the claim true for n=1, and**[2]**prove that*if*,*supposing for the sake of argument*, the claim is true for n equal to a particular number k,*then*it will be true for n equal to k+1 – once we prove those two things, it follows instantaneously that the claim is true for*all*values of n. This has the odd effect that when you prove the second step, you start not knowing at all whether the claim is true for n=k, just supposing it for the sake of argument; but when you finish proving the second step, then (as long as you’ve already proved the first step), that instantly proves that the claim was true for n=k after all.

There are *two* steps in proof by induction (not four as the textbook says). One, prove the claim true for n=1. Two, prove that *if* the claim is true for n=k, *then* it is true for n=k+1. Only both steps together give you the conclusion: *the claim is true for all n, by induction*.

It is like spaghetti bolognese. There are two steps to cooking spaghetti bolognese:

The spaghetti

And the sauce

Then, when you have completed both steps, you can put them together and you have the spaghetti bolognese.

**WHAT IS MATHEMATICAL PROOF?**

**Do now**: Write down on the whiteboard what you know about mathematical proof.

Proof is what we use for decisive evidence in maths.

It is like proof in a court of law, except it has to be beyond all doubt, not just beyond reasonable doubt.

A proof is a string of sentences, where every sentence is either something we already know to be true, or follows logically from the previous sentences, and the last sentence is what we want to prove.

What’s the difference between evidence in maths and evidence in other areas?

Do we ever use looser evidence in maths?

Do mathematical proofs include ordinary words as well as mathematical symbols?

Proving that we can’t calculate √2 exactly

**SERIES**