Lecture notes on Induction
These notes span 4 different lectures:
They are all related to induction, a proof technique that we will use throughout the course.
Lecture Notes Monday (scanned PDF) on invariants
Lecture Notes Thursday (scanned PDF) on induction
Lecture Notes Friday (scanned PDF) on strong induction and sums
Lecture Notes Monday (scanned PDF) on applications of induction
Invariants
Read about invariants in the book, chapter 6.2.
Invariants is a proof technique that can be used to show that, during a repetitive process, such as following the same rule over and over again in a game, certain conditions always hold, and thus they must also hold when we stop.
Invariants can be seen as an introduction to induction.
Russian multiplication
In the lecture, we saw a method of multiplication called Russian Peasant multiplication. It only requires the user to be able to add, double, and halve numbers.
Let's explain how it works using an example: we are going to calculate \(22 \times 24\).
We now make a table with rows of two numbers. We start with a row with the numbers 22 and 24. On the next row, we halve the left-hand side number, and we double the right-hand side number. (If the left-hand side number is odd, we round down when we halve; for example 11 below becomes 5 after halving.)
| 22 | 24 |
| 11 | 48 |
| 5 | 96 |
| 2 | 192 |
| 1 | 384 |
We stop when we reach 1.
The next step is to cross out all the rows where the left-hand side number is even:
| 11 | 48 |
| 5 | 96 |
| 1 | 384 |
Here, we crossed out the rows with the numbers 22 and 2 on the left-hand side.
The last step is to add up all the numbers on the right-hand side that are not crossed out:
| 11 | 48 | |
| 5 | 96 | |
| 1 | 384 | + |
| 528 |
The result of that addition is the answer! We can see that 48+96+384=528 and also 22*24=528.
This seems rather magical; why on earth does it work? We can use invariants to figure this out. To do this, we first change the method a little bit so that we do not compute the sum after the halving and the doubling, but during. So, we will compute three numbers: the left-hand side (x), the right-hand side (y), and the sum (s). We start with (x,y,s) being (22,24,0); 22 and 24 because we want to multiply them and s because we have not summed anything yet.
In each row, we halve x and double y as before, but we also add y to s if x is odd. If x is even, we do nothing to s. We also keep going with the halving until we reach 0:
| x | y | s | |
| 22 | 24 | 0 | (start) |
| 11 | 48 | 0 | (do nothing because 22 is even) |
| 5 | 96 | 48 | (add 48 because 11 is odd) |
| 2 | 192 | 144 | (add 96 because 5 is odd) |
| 1 | 384 | 144 | (do nothing because 2 is even) |
| 0 | (768) | 528 | (add 384 because 1 is odd) |
When x=0, we are done, and the answer 528 is in the s column. (We write (768) in the y column in the last row because that answer is never needed.)
This method is basically the same as before, but we have condensed everything into the repeated application of one single step.
The state of our method is three numbers \((x,y,s)\). We start in the state \((a,b,0)\) if we want to multiply \(a\) and \(b\). In the example above, a=22 and b=24. The invariant \(P\) of our system is given by: \[ P(x,y,s) = \; "x \cdot y + s = a \cdot b" \] In other words, whenever we are in a state \(x,y,s)\), multiplying \(x\) and \(y\) and then adding \(s\) should always be the answer \(a \cdot b\). (Try out for yourself that the invariant holds for every row in the above table!)
We can see that the invariant holds at the beginning state \((a,b,0)\), since \(a \cdot b + 0 = a \cdot b\).
We can see if the invariant holds at the end (when \(x\) is 0), that ((s\) must contain the answer, because \(0 \cdot y + s = a \cdot b\) means \(s = a \cdot b\).
All we have to do now is to show that the invariant is maintained by the step of the method. What is the step? There are two cases, one for when \(x\) is even, and one for when \(x\) is odd. \[ (x,y,s) \longrightarrow \begin{cases} (x/2,2y,s) & x \; \text{even} \\ ((x-1)/2,2y,s+y) & x \; \text{odd} \end{cases} \] So, the proof also has two cases.
Case 1: \(x\) is even. We have to show that \(P(x,y,s) \Rightarrow P(x/2,2y,s)\).
We assume \(P(x,y,s)\), meaning that \(x \cdot y + s = a \cdot b\).
We have to show that \(P(x/2,2y,s)\), meaning that \((x/2) \cdot 2y + s = a \cdot b\). We can see that this is the case because \((x/2) \cdot 2y\) is the same as \(x \cdot y\), so \((x/2) \cdot 2y + s = x \cdot y + s\), which we know to be equal to \(a \cdot b\), because of 1.
Case 2: \(x\) is odd. We have to show that \(P(x,y,s) \Rightarrow P((x-1)/2,2y,s+y)\).
We assume \(P(x,y,s)\), meaning that \(x \cdot y + s = a \cdot b\).
We have to show that \(P((x-1)/2,2y,s+y)\), meaning that \(((x-1)/2) \cdot 2y + s + y = a \cdot b\). We can see that this is the case because \(((x-1)/2) \cdot 2y\) is the same as \(x \cdot y - y\), so \(((x-1)/2) \cdot 2y + s + y = x \cdot y - y + s + y\), which equals \(x \cdot y + s\), which in turn we know to be equal to \(a \cdot b\), because of 1.
This concludes the proof.
To sum up, we established \(P\) as an invariant of the method, by showing (1) that \(P\) holds for the initial state \(P(a,b,0)\), and (2) that \(P\) is maintained by the step of the method. Once we know that \(P\) is an invariant, we know that it must always hold, even at the end of the method when \(x=0\). This in turns means that \(s = a \cdot b\) at the end of the method.
Induction
Read about induction in the book, chapter 5.
Induction is a proof method we use to prove general statements that hold for all natural numbers.
The book explains the ideas behind induction rather well. However, the actual proofs using induction in the book take (in my opinion) steps that are a bit too large, which makes it difficult to see for someone who has never seen induction proofs what is going on.
Here, I present induction proofs in the way I think they should be written. And the way you should write them in the answers to the weekly assignments and the exam. You can find more examples in the answers of the exercises for week 3.
Important principles we try to always follow are the following:
(1.) Always write down in the proof that are you are induction, what kind of induction you are doing, and over what variable.
(2.) Induction proofs really work the same way as proofs by case distinction. In proofs by case distinction, we (1) cleary state what cases we are considering, and (2) what we know in each case. We do the same in induction proofs. The only difference is that we have an extra bit of information we may use in the step case, namely the induction hypothesis (I.H.). In the step case, we therefore always explicitly write down what the induction hypothesis is.
Here is an example of an actual proof by simple induction.
To prove: 1 + 2 + ... + n = n(n+1)/2, for n ≥ 1
Proof: By induction over n. Let P(n) = "1 + 2 + ... + n = n(n+1)/2"
Base case: P(1): Then we have 1 = 1(1+1)/2. OK!
Step case: P(k) => P(k+1), k ≥ 1.
(1.) By the induction hypothesis (I.H.), we know that that P(k), in other words 1 + 2 + ... + k = k(k+1)/2.
(2.) Now we prove P(k+1):
1 + 2 + ... + k + (k+1)
= (1 + 2 + ... + k) + (k+1)
= k(k+1)/2 + (k+1) [ by the I.H. ]
= k(k+1)/2 + 2(k+1)/2
= (k+1)(k+2)/2
Which is what we had to prove!
Here is an example of a proof by strong induction that √2 is an irrational number. We did not do this particular proof in the lecture.
To prove: √2 is an irrational number.
Proof: What we are actually going to prove is that for any n ≥ 0, p ≥ 1 in \(\mathbb{N}\), √2 /= (n/p).
We are going to do this by strong induction over n. Let P(n) = "for any p ≥ 1 in \(\mathbb{N}\), √2 /= (n/p)".
Base case: P(0): √2 /= (0/p), for any p ≥ 1. OK!
Step case: (P(0) /\ P(1) /\ ... /\ P(k)) => P(k+1), for k≥0.
We have to show that √2 /= (k+1)/p, for any p ≥ 1. We do this by proof by contradiction. So, we imagine that we have p ≥ 1 such that √2 = (k+1)/p.
(1.) We know that p < k+1, because √2 > 1.
(2.) We also know that 2 = (k+1)2 / p2, which means that (k+1)2 = 2p2.
(3.) This means that k+1 is even. Let us introduce m such that k+1 = 2m.
(4.) Now we know that (2m)2 = 2p2, which implies that 4m2 = 2p2, which means that 2m2 = p2.
(5.) In other words, 2 = p2 / m2, and thus √2 /= (p/m). In other words, we have found a new way of writing √2 as a rational number!
(6.) This time, the numerator (here, p) is smaller than the previous numerator (then, k+1).
(7.) But 1 ≤ p < k+1, and by the IH we know that no such p can exist. In other words, what we assumed was false and there are no n and p such that √2 = (n/p).
Sums
Read about sums in the book, chapter 14.1 and 14.2.
Sums of series, e.g. \(1+2+ \dots +n\) or \(2^0 + 2^1 + 2^2 + \dots + 2^n\) can be solved by induction. We we will also see generalizations of these sums.
We talked about the following theorem in the lecture, but did not prove it:
To prove: 1 + x2 + ... + xn = (xn+1-1)/(x-1), for x /= 0, x /= 1, n ≥ 0
Proof: By induction over n. Let P(n) = "1 + x2 + ... + xn = (xn+1-1)/(x-1)".
Base case: P(0): Then we have 1 = (x-1)/(x-1). OK!
Step case: P(k) => P(k+1), k ≥ 0.
(1.) By the induction hypothesis (I.H.), we know that P(k), in other words 1 + x2 + ... + xk = (xk+1-1)/(x-1).
(2.) Now we prove P(k+1):
1 + x2 + ... + xk + xk+1
= (xk+1-1)/(x-1) + xk+1 [ by the I.H. ]
= (xk+1-1)/(x-1) + xk+1(x-1)/(x-1)
= (xk+1 - 1 + xk+1(x-1))/(x-1)
= (xk+1 - 1 + xk+2 - xk+1)/(x-1)
= (xk+2 - 1)/(x-1)
Which is what we had to prove!
Applications of Induction
We will wrap up the lectures about induction and see some examples of induction in the wild.
In particular, we saw the famous proof that all horses have the same color.
A video of that proof by a math blogger
A video of a similar proof by MindYourDecisions
Of course the statement is not true, and the above videos also explain what went wrong in the proof.