This is the translation of an older post in French: Raisonnement par récurrence et raisonnement par l’absurde.
Let’s have a pretty short post so that I can refer to it later – I have another monster-post in the works, and I realized I needed the following elements to make it work, so here’s another post! I’m going to talk about two fundamental tools in the “proof toolbox”: the proof by induction and the proof by contradiction. These are tools that are explained in high school (well, they were in my French high school 20+ years ago 😉 ), and that you’ll see everywhere all the time, so let’s explain how it works.
Proof by induction
The idea of the induction proof is dominoes. Not the ones with the dots on them, the ones that you topple. You know that if you topple a domino, it falls. And if a domino falls, the next one falls as well. And you topple the first domino. Hence, all the dominoes fall.
Proofs by induction work in the same way. Suppose you have a property that depends on an natural number (positive integer), and you want to prove that it’s true for any natural number. First, you show that it’s true for a small natural number, say 0, 1 or 2 (sometimes the property doesn’t make much sense for 0 or 1). Then, you show that, if it’s true for a natural number , it’s also true for . So you have the “start” of the dominoes, the toppling (“it’s true for 0”), and the “chain” of dominoes (“if it’s true for , it’s true for “). If these two conditions are true, all the dominoes fall (“the property is true for all natural numbers greater than 0”).
Now this is where I’m a bit annoyed, because I have a an example that works, but the induction proof kind of sucks compared to another, which is much prettier. So I’m going to show both 😉
Suppose that I want to prove that the sum of all integers from 1 to (that is to say, ) equals . I start with : , so the base case is true.
Now, I suppose that it’s true for an arbitrary natural number that the sum of the integers from 1 to is equal to , and I compute the sum of integers from 1 to : . This is equal to the sum of the integers from 1 to , plus . By induction hypothesis, this is equal to . For my proof to work out, I want the sum of integers from 1 to to be equal to . And it so happens that is precisely equal to .
So I have my base case, my induction step, and I proved exactly what I wanted to prove.
Now for the alternative, prettier proof. You consider a table with two lines and columns:
1 2 3 4 ... n-2 n-1 n
n n-1 n-2 n-3 3 2 1
and you compute the sum of all the numbers in the table. You can add up, for each column, both lines. Every column sums to : it’s the case for the first column, and at each step, you remove 1 from the first line, and you add 1 to the second line, so the sum stays the same (there’s actually a “hidden” induction proof in there!) There are columns, so if I add all these results, it sums to . But if I group the sum in a different way, the first line is equal to the sum of integers from 1 to , the second line as well… so is two times the sum of the integers from 1 to , which concludes the proof.
Proof by contradiction
Proofs by contradiction are sometimes dangerous, because they’re often misused or overused. I know some mathematicians who argue that a proof by contradiction is not very elegant, and that when one arises, it’s usually worth it to make the extra effort to try to turn it around in a non-contradiction proof. I still like the reasoning behind it, and it sometimes makes life much easier.
We want to prove that a proposition A is true. To prove A by contradiction, you make the hypothesis that A is false, you unroll a series of consequences that would be implied by the fact that A is false, and you arrive at something that you know is impossible. And if the fact that A is false implies an impossibility, it means that A is true, otherwise the universe collapses and it’s messy.
My favorite example is to prove that is irrational, that is to say that you can’t write it as where and are integers.
I need a tiny preliminary lemma: I’m claiming that if an integer is even, then its square is even, and that if is even, then is even. If is even, I can write (with integer). Then , so is even. If is odd, I can write , so , so is odd. So, if is even, then it can’t be that would be odd (because otherwise would be odd as well), so is even.
Now back to the irrationality of . We make the hypothesis that we can write . We can also make the assumption that the fraction is irreducible, because if it’s not, you can reduce it so that it is, so let’s assume that it’s the one we took from the beginning. (Note: a fraction is irreducible if there is no integer such that and are both divisible by . If exists, we divide and by , and we get the fraction ).
So: I can write that . If I square this equality, I get . Since is an integer, is an integer, so is an even number (because it’s equal to twice an integer). But then, if is even, then is even as well, according to my preliminary lemma. So I can write and consequently . But then, since , I can also write , so is even, so is even as well. But that’s not possible: is irreducible, so and cannot be both even! So something is wrong in my reasoning, and the only thing that can be wrong is my initial hypothesis, that is is rational. Hence, is irrational. Cute, isn’t it?