# FP1: proof, and proof by induction; and series

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

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

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 nth 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) = ____ × 4n ≠ 16n

¼n2(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)

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:
13
13+23
13+23+33
13+23+33+43
13+23+33+43+53

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

F+V=E+2

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 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?

Lesson and homework on proof