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

Schedule for FP1 work:

1. Proof by induction: using a “domino effect” to prove mathematical formulas

2. Series: how to calculate 13+23+33+43+… and similar

3. Numerical methods (except Newton-Raphson): how to get good approximate solutions to equations when we can’t solve them exactly

4. Matrices: arithmetic and algebra with tables of numbers in place of numbers

5. Complex numbers: extending our idea of number to include √(−1)

6. Using parameters (chapter is called “Coordinate Systems”): describing curves not by an equation connecting y and x, but by two equations, one connecting y to time t, and the other connecting x to time t

7. Newton-Raphson: another way of getting good approximate solutions, which we have to leave until late because you need to have done differentiation in C1 first.

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

Explore how to solve maths problems step-by-step

Do now (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”

Do now: page 4 of induction workbook

Scaffolded examples of proof by induction with sequences (from workbook)

Homework: Finish pages 1 to 8 from workbook.

PAST-PAPER QUESTIONS: INDUCTION (SEQUENCES)

Past-paper questions on proof by induction with sequences (from workbook)

Also look at “going-up-in-twos” induction problems with sequences (textbook Example 9, p.132, and Q.5-8 of Ex.6C, p.133).

HOW TO WORK WITH SERIES; PROOF BY INDUCTION ABOUT SERIES

Work on “how to use Σ” and scaffolded examples of proof by induction with series (from workbook)

Model series proofs

Past-paper questions on proof by induction with series

MORE PROOFS BY INDUCTION

DO NOW: ONE: write “student response” on your homework marking.

TWO: | means “divides exactly into”. So 2|4, but 4|2 is not true. 3|9, but 7|9 is not true.

On your whiteboard, write three true statements using | and three false statements using |.

THREE: Here are three mathematical guesses.

• At Vicky Neale’s session, Jetmir guessed that the square of an even number, plus 1, is always prime.
• The French mathematician Pierre de Fermat guessed that 22n+1 is prime for every n.
• 6 | 7n−1 for every n.

Which of those is most worth trying to prove by induction?

THEN: Choose one of the following paths:

• If I’ve written “please do Q.5, 6, 8 on p.127” in your book, or if you feel a bit unsure about proofs with series, do do Q.5, 6, 8 on p.127, and Q.3, 4, 10 if you need more practice
• If you’re already good with proofs with divisibility (Tegan, Bolaji, Peter, Vinh), go on to chapter 5 (Q.1 and 2 each of Ex.5B, 5C, 5D, then on to Ex.5E)
• If you’re good with proofs with series, listen to me explaining proofs with divisibility, and then do the scaffolded divisibility examples in the workbook.
• Model proofs by induction with divisibility

From workbook: scaffolded examples of proofs by induction about divisibility, and past-paper questions

If you’re proving by induction that some f(n) is divisible by a particular number for all n, then writing an equation for f(k+1) does not automatically enable you to get information about f(k+1) from your suppose-for-the-sake-of-argument information about f(k).

With a proof by induction with sequences, the recurrence relation automatically gives you an equation for uk+1 with uk on the right-hand side, so you can straight away use your suppose-for-the-sake-of-argument idea that uk is equal to the claimed formula.

With a proof by induction with series, the sum from 1 to k+1 equals the sum from 1 to k plus the (k+1)’th term, and again you can straight away use your suppose-for-the-sake-of-argument information about the sum from 1 to k.

With a proof by induction with divisibility, it’s a little more subtle. After you write m | f(k), you have to fiddle with that, either by adding something divisible by m to f(k), or, if that doesn’t work, multiplying f(k) by a number, to get m | f(k+1) ± something obviously divisible by m.

Sometimes exam questions have a first half which asks you to prove something like

f(k+1) = 6 f(k) − 4×2k

You do that just by calculating 6 f(k) − 4×2k (or whatever) and simplifying.

That bit is meant to help with the second half of the question, which will be to prove by induction that f(n) is divisible by some number for all n.

In the second step of the induction proof, you can write straight away:

f(k+1) = 6 f(k) − 4×2k

and it follows straight away that if f(k) is divisible by 4 (in this case), then f(k+1) must be, because if you add two numbers both divisible by 4, the total is also divisible by 4.

In that actual example, you’re asked to prove that f(n) is divisible by 8 for all n, not just by 4. There are other examples with a similar extra twist.

So…. you want to prove that if f(k) is divisible by 8, then f(k+1) must also be divisible by 8. To do that you need to see that 4×2k is always divisible by 8 (as long as k≥1).

Why is it always divisible by 8, as long as k≥1? Because 2k is even, and 4 times an even number is always divisible by 8.

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?

Booklet on proof