Lesson 1 of 16 · about 12 min

What is a proof?

A proof is an argument that leaves no room for doubt. You'll see a pattern that works for 40 numbers in a row and then breaks, learn why examples alone can't prove anything, and put together your first real proof.

🧭 What you need first: Making decisions

The story

Imagine a friend shows you a magic formula: take any whole number $n$ , work out $n^2 + n + 41$ , and you always get a prime number. You try 0: 41, prime. 1: 43, prime. 2: 47, prime. You try ten more. All prime. Twenty more. Still prime!

Is the formula magic? Your gut says yes. But at $n = 40$ it gives $1681$ , which is $41 \times 41$ . Not prime. The pattern simply stops.

This is why mathematicians, and computer scientists, don’t stop at “it worked every time I tried.” Programs run on inputs nobody tried. A proof is how you know something works for all of them, including the billionth one. The good news: proofs follow a handful of recipes, and you’ll learn every one of them in this course.

Another way: a bridge inspector

Driving 1,000 cars over a bridge without it collapsing is encouraging. An engineer’s calculation that shows it holds any load up to 40 tonnes is a proof. The calculation covers truck number 1,001 too.

Another way: a recipe with no guessing

A proof is like a recipe where every step is forced by the one before. Anyone who follows it carefully reaches the same dish, and nobody can argue about the result.

Play with it

Try the magic formula

Run this to test $n^2 + n + 41$ for the first 10 numbers. Then change range(10) to range(45) and run it again. Where does the magic stop?

or Ctrl/⌘ + Enter

Name it

The real words

A statement (or proposition) is a sentence that’s either true or false: “7 is prime”, “every even number is a sum of two primes”. “Close the door” isn’t a statement.
A proof is a chain of steps, each one justified by a definition, an earlier step or something already proven, ending at the statement. A proven statement is called a theorem.
A definition pins down exactly what a word means, so a proof has something solid to stand on:
- $n$ is even if $n = 2k$ for some integer $k$ . It’s odd if $n = 2k + 1$ .
- A whole number greater than 1 is prime if its only divisors are 1 and itself.
Examples aren’t proofs. Checking cases is how you find a likely truth (and a single failure disproves a claim, lesson 11). Proving it takes an argument that works for every case at once.
Why programmers care: an algorithm has to be right for every input, including ones nobody tested. Proofs are how we know sorting, encryption and compilers really work.

Build it

Find where the pattern breaks

Write first_failure() so it returns the first whole number n (starting from 0) for which n*n + n + 41 is NOT prime.

or Ctrl/⌘ + Enter

Challenge

Your first proof

Here’s a real proof that the sum of any two even numbers is even. The steps are scrambled. Put them in order. Notice how it never picks specific numbers: it works for any two even numbers at once.

🧩 Prove: the sum of two even numbers is even.

Use the arrows to put the steps of the proof in order, then check.

j + k is an integer, so a + b is 2 times an integer.
Then a + b = 2j + 2k.
Let a and b be any two even numbers.
Factor out the 2: a + b = 2(j + k).
So by the definition of even, a + b is even. ∎
By the definition of even, a = 2j and b = 2k for some integers j and k.

Remember it

You test a claim on the first million whole numbers and it's true every time. What do you know?

Got it?

Finish the lesson to color it in on your map and collect its concept cards.

Did this lesson click?