Proof by induction and proof by contradiction

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 $k$ , it’s also true for $k+1$ . 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 $k$ , it’s true for $k+1$ “). 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 $n$ (that is to say, $1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n$ ) equals $\displaystyle \frac{n(n+1)}{2}$ . I start with $n=1$ : $\displaystyle \frac{1(1+1)}{2} = \frac 2 2 = 1$ , so the base case is true.

Now, I suppose that it’s true for an arbitrary natural number $k$ that the sum of the integers from 1 to $k$ is equal to $\displaystyle \frac{k(k+1)}{2}$ , and I compute the sum of integers from 1 to $k+1$ : $1 + 2 + 3 + ... + (k-1) + k + (k+1)$ . This is equal to the sum of the integers from 1 to $k$ , plus $k+1$ . By induction hypothesis, this is equal to $\displaystyle \frac{k(k+1)}{2} + k+1 = \frac{k^2 + k + 2k + 2}{2} = \frac{k^2 + 3k + 2}{2}$ . For my proof to work out, I want the sum of integers from 1 to $k+1$ to be equal to $\displaystyle \frac{(k+1)(k+2)}{2}$ . And it so happens that $(k+1)(k+2)$ is precisely equal to $k^2 + 3k + 2$ .

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 $n$ 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 $n+1$ : 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 $n$ columns, so if I add all these results, it sums to $n(n+1)$ . But if I group the sum in a different way, the first line is equal to the sum of integers from 1 to $n$ , the second line as well… so $n(n+1)$ is two times the sum of the integers from 1 to $n$ , 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 $\sqrt 2$ is irrational, that is to say that you can’t write it as $\displaystyle \frac p q$ where $p$ and $q$ are integers.

I need a tiny preliminary lemma: I’m claiming that if an integer $n$ is even, then its square $n^2$ is even, and that if $n^2$ is even, then $n$ is even. If $n$ is even, I can write $n = 2k$ (with $k$ integer). Then $n^2 = 4k^2 = 2 \times 2k^2$ , so $n^2$ is even. If $n$ is odd, I can write $n = 2k+1$ , so $n^2 = 4k^2 + 2k + 1 = 2(2k^2 + k) + 1$ , so $n^2$ is odd. So, if $n^2$ is even, then it can’t be that $n$ would be odd (because otherwise $n^2$ would be odd as well), so $n$ is even.

Now back to the irrationality of $\sqrt{2}$ . We make the hypothesis that we can write $\displaystyle \sqrt 2 = \frac p q$ . 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 $\displaystyle \frac p q$ is irreducible if there is no integer $k \geq 2$ such that $p$ and $q$ are both divisible by $k$ . If $k$ exists, we divide $p$ and $q$ by $k$ , and we get the fraction $\displaystyle \frac{p/k}{q/k}$ ).

So: I can write that $\sqrt 2 \times q = p$ . If I square this equality, I get $2q^2 = p^2$ . Since $q$ is an integer, $q^2$ is an integer, so $p^2$ is an even number (because it’s equal to twice an integer). But then, if $p^2$ is even, then $p$ is even as well, according to my preliminary lemma. So I can write $p = 2k$ and consequently $p^2 = 4k^2$ . But then, since $2q^2 = p^2 = 4k^2$ , I can also write $q^2 = 2k^2$ , so $q^2$ is even, so $q$ is even as well. But that’s not possible: $\displaystyle \frac p q$ is irreducible, so $p$ and $q$ 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 $\sqrt{2}$ is rational. Hence, $\sqrt{2}$ is irrational. Cute, isn’t it?

	wiesmann on “What do I do with that…
	Balise on “What do I do with that…
	wiesmann on “What do I do with that…
	Scavenger Hunt #37… on Scavenger Hunt #32 –…
	wiesmann on 52Frames – 2022-49…

Proof by induction

Proof by contradiction

Partager :

Like this:

Related

Leave a Reply Cancel reply