Proof Writing for Beginners

A lot of students first meet proof as a wall of formal language.

That is unfortunate, because proof is really just the act of answering one question:

How do you know this always works?

COSMO teaches proof as explanation before formality. The goal is not to sound like a textbook. The goal is to make the reason unavoidable.

Examples Are Not Proofs

If you test a statement for 5, 10, and 100 examples, you have evidence. You do not have proof.

For example, try this claim:

The sum of two even numbers is even.

Testing $2+4$, $8+10$, and $100+222$ helps you see the pattern, but it does not prove every case.

A proof explains why the pattern has no choice but to continue.

Direct Proof

A direct proof starts with what you know and walks forward.

Claim: The sum of two even numbers is even.

If a number is even, it can be written as $2a$ for some integer $a$.

Let the two even numbers be $2a$ and $2b$.

Their sum is:

$2a + 2b = 2(a+b)$

Since $a+b$ is an integer, $2(a+b)$ is even.

That is the whole proof.

Proof by Contradiction

Contradiction works by assuming the opposite of what you want, then showing that assumption breaks something.

Classic example: There are infinitely many prime numbers.

Suppose there are only finitely many primes: $p_1, p_2, \ldots, p_n$.

Now create:

$N = p_1p_2\cdots p_n + 1$

When you divide $N$ by any prime on the list, the remainder is 1. So $N$ is either prime itself or has a prime factor not on the list.

Either way, the original list was incomplete. Contradiction.

Therefore, there are infinitely many primes.

Induction

Induction is useful when a claim depends on a positive integer: $n = 1, 2, 3, \ldots$

It has two moves:

1. Prove the first case.
2. Prove that if one case works, the next one must work too.

It is like dominoes. You knock over the first domino, then prove each domino knocks over the next.

COSMO Proof Habit

Before writing a formal proof, ask three questions:

1. What definitions are involved?
2. What would make the claim fail?
3. Is there a smaller version of the problem I can understand first?

These questions turn proof from a performance into a search.

Takeaway

A proof is not fancy language. It is a chain of reasons.

When students understand that, they stop asking, “What do I write?” and start asking, “What has to be true?”