Unit 28: Prove It

A pattern that lies

Try n^2 + n + 41 and ask whether it is prime.

For n = 0 it gives 41, prime. For 1, 43, prime. For 2, 47. It keeps giving primes — for forty values in a row.

Then n = 41 gives 41 × 43. Not prime at all.

Forty examples proved nothing. That is the whole problem with checking.

One counterexample is enough

Proving something false is much easier than proving it true. You only need one example that breaks it — a counterexample.

"Every prime is odd" dies instantly: 2 is prime and even. Done.

So the two jobs are completely different sizes. To disprove: find one. To prove: cover every case at once.

Why algebra is the tool for proof

To prove something about every even number, do not test them one at a time. Give them a name.

Every even number is 2n for some whole number n. Now anything you show about 2n is true of all of them at once.

That is what algebra is *for*. Not finding x — covering infinitely many cases in one line.

An odd plus an odd

Odd numbers are 2n + 1. Add two of them:

(2a + 1) + (2b + 1) = 2a + 2b + 2 = 2(a + b + 1)

That is 2 times a whole number, so it is even. Always. No exceptions, none left to check.

That is a proof.

The three-consecutive-numbers trick

Call three numbers in a row n - 1, n and n + 1. Add them:

(n - 1) + n + (n + 1) = 3n

So the sum of any three consecutive numbers is a multiple of 3, and it is three times the middle one.

Choosing to call the *middle* one n is what made it fall out so cleanly. Good notation is half of a good proof.

A conjecture is a guess you take seriously

Add the first few odd numbers: 1, then 4, then 9, then 16.

Those are the square numbers. So you might conjecture: the first n odd numbers always add to n^2.

A conjecture is not a proof. It is a guess precise enough to be tested — and that precision is what makes it useful rather than a vague feeling.

Test it hard, and try to break it

Testing a conjecture means genuinely trying to break it, not gathering friendly examples.

Try negatives. Try zero. Try one. Try something enormous. Those are where claims fall over.

"Every prime is odd" survives 3, 5, 7, 11 — and dies instantly at 2, the very first case anybody skipped.

Write down what the words mean

To prove something about multiples of 3, write a multiple of 3 as 3n.

That one step does most of the work, because now the claim is about algebra rather than about examples.

Add two of them: 3a + 3b = 3(a + b). Three times a whole number, so a multiple of 3. Proved, for every pair there will ever be.

Consecutive numbers, and what they guarantee

Among any two numbers in a row, one is even. Among any three, one divides by 3.

So n(n + 1) is always even, and n(n + 1)(n + 2) always divides by 6.

That is a proof, not a pattern: it does not matter which of them is even, only that one of them must be.

The converse is a different claim

"If it is a square, then it has four equal sides." True.

Turn it round — the converse — "if it has four equal sides, then it is a square." False: a pushed-over rhombus.

A statement and its converse are separate claims. Proving one says nothing at all about the other, and mixing them up is the most common mistake in reasoning.

When both directions hold

Sometimes a statement and its converse are both true. Then we say if and only if.

"A number is even if and only if it ends in 0, 2, 4, 6 or 8." Both ways round.

That is the strongest kind of statement, because it says the two things are really the same condition wearing different clothes. And proving it means proving two things, not one.

Induction, one rung at a time

To prove 1 + 2 + … + n = n(n + 1)/2 for every n, do two things.

Base: check n = 1. The sum is 1, and 1 × 2/2 = 1. True.

Step: assume it works for some n, then show it must work for n + 1. Adding the next number gives n(n+1)/2 + (n+1), which tidies to (n+1)(n+2)/2 — exactly the formula with n + 1 in it.

Base plus step, and every rung is reachable.

Both parts are essential

Without the base, the step proves nothing — you can show each rung leads to the next and still never get on the ladder.

"If n is the biggest number then n + 1 is bigger" is a perfectly good step, and the claim is nonsense because no base exists.

Without the step, you have only checked one case. Both, together, or neither.

Proof by contradiction

Suppose the thing you want to disprove is true, and follow it until it says something impossible.

That is how unit 8 showed sqrt(2) is not a fraction: assume it is a/b in lowest terms, and out comes "a and b are both even" — which contradicts "lowest terms".

The assumption broke, so it was false. Nothing else it could be.

There is no biggest prime

Euclid, two thousand years ago. Suppose there were only finitely many primes. Multiply them all together and add 1.

That new number leaves a remainder of 1 when divided by every prime on the list. So either it is prime itself, or it has a prime factor nobody listed.

Either way the list was incomplete. So no finite list can hold them all.

Proof by induction: the ladder

To show something is true for every whole number, you do not need infinitely many proofs. You need two.

Show it is true for 1. Then show that whenever it is true for a number, it must be true for the next one.

That is a ladder: you can reach the first rung, and from any rung you can reach the next. So you can reach every rung.

What you have learned to do

You started twenty-eight units ago by counting how many 3s are in 3^4.

Since then you have solved equations, invented a number that could not exist, measured circles, chased angles round a diagram, counted things too numerous to list, and finished by proving something true for every number there will ever be.

That last one is the difference between doing sums and doing mathematics. Well done.