A team in Germany made over 270,000 dominos to fall and created a world record. It took a week for them to set this up.
How do they know for sure that if the first domino falls all the dominos will fall? They came to that conclusion by knowing two facts
- The first dominos falls. Even a toddler can push it down.
- If any domino falls, the next one falls.
The two steps used in dominos effect is Mathematical Induction. It is a special way of proving things. Using induction you take specific facts and prove that it is true for all cases. If this was not the case then you need to spend another week to prove that 300,000 dominos will fall.
A proof by mathematical induction that a proposition P(n) is true for every positive integer n consists of two steps.
1. Base Case: Show that the proposition P(1) is true.
2. Inductive Step: Assume that P(k) is true for an arbitrarily chosen positive integer k, and show that under that assumption, P(k + 1) must be true.
From these two steps we conclude that for all positive integers n, P(n) is true.
Let us solve some problems to understand this better.
Problem 1: Family Tree
Imagine that your great, great, great, … grandfather Tom had two children. Call this generation one, so generation one contains 2 offsprings of Tom. Each of these children have two children, so generation two will have 4 offsprings. Each of these 4 offsprings has two children so at generation three, we have 8 offsprings. If this continues from generation to generation can you prove that at generation n we will have 2n offsprings?
Base Case: P(1) asserts that generation 1 has 21 offspring, which is true since we are told that Tom had two children.
Inductive Step: We assume that for an arbitrary integer k, P(k) is true, i.e., that generation k has 2k offspring. We need to show that generation k + 1 has 2k + 1 offspring.
Generation k + 1 has 2 * 2k offsprings [Generation k has 2k assumed to be true] Generation k + 1 has 21 * 2k offsprings Generation k + 1 has 2k + 1 offsprings
Thus P(k + 1) is true when P(k) is true. Hence P(n) is true for all natural numbers.
Problem 2: Sum of consecutive natural numbers
Prove that for every positive integer n, the sum of first n positive integers is n * (n + 1) / 2
Base Case: For P(1) we get 1 * (1 + 1) /2 = 1, which is true.
Inductive Step: Let us assume that the formula is true for the first k integers. We need to prove that it is true for the first (k + 1) integers.
From our assumption 1 + 2 + ... + k = k * (k + 1) / 2 For 1 + 2 + ... + k + (k + 1) = (k * (k + 1) / 2) + (k + 1) = (k * (k + 1) + 2 * (k + 1)) / 2 = (k2 + 3*k + 2) / 2 = ((k + 1) * (k + 2)) / 2 = ((k + 1) * ((k + 1) + 1)) / 2
Thus P(k + 1) is true when P(k) is true, and therefore P(n) is true for all natural numbers.
Recursion is a term that is used often in computer science. It is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Recursion is mathematical induction. In the book The Algorithm Design Manual – Steve Skiena writes
When I first learned the programming technique of recursion it also seemed like complete magic. The program tested whether the input argument was some basis case like 1 or 2. If not, you solved the bigger case by breaking it into pieces and calling the subprogram itself to solve these pieces. That was a program? Ridiculous! The reason both seemed like magic is because recursion is mathematical induction. In both, we have general and boundary conditions, with the general condition breaking the problem into smaller and smaller pieces. The initial or boundary condition terminates the recursion. Once you understand either recursion or induction, you should be able to see why the other one also works.
What does the following piece of python code do?
def increment(y): if y == 0: return 1 else: if y % 2 == 1: return (2 * increment(y / 2)) else: return y + 1
By looking at the code it is not very obvious what it does. From the method name you can guess that it increments the input by 1 and returns the incremented value. In fact this is what it does. I verified it by using the following print statements
print 'Increment of 0 -> ', increment(0) print 'Increment of 1 -> ', increment(1) print 'Increment of 10 -> ', increment(10) print 'Increment of 101 -> ', increment(101)
Here is the output
Increment of 0 -> 1 Increment of 1 -> 2 Increment of 10 -> 11 Increment of 101 -> 102
By verifying it with few inputs does not guarantee that it is going to work for all the inputs. You need to prove it for all cases. We can use mathematical induction to prove this.
Base Case: Here the base case is 0. I already proved for input 0 it returns 1 with a print statement,
Inductive Step: Assume that it is true for y = n – 1 and we need to prove that it is true for y = n
Half of the cases are straightforward. Look at the code and you can see that when y is an even number y + 1 is explicitly returned. Hence we need to prove when y is an odd number.
Since y is odd we call keep y = 2 * m + 1 for some integer m (2 * increment(y / 2)) = (2 * increment((2 * m + 1) / 2)) = (2 * increment(m + 1/2)) = (2 * increment(m)) = (2 * (m + 1)) [assumption in inductive step; increment(m) = m + 1] = 2 * m + 2 = (2 * m + 1) + 1 = y + 1 [as y = 2 * m + 1]
Thus we have proved that it will work for all the cases.
Incorrect uses of induction in real life
You can never really prove the proposition that “All swans are white” even if you have only seen white swans in your entire life. Until 1697 people assumed that all swans are white. In 1697 Willem de Vlamingh’s spotted a Black Swan in Western Australia and the proposition became false.
House prices in the United States went up in 2000, 2001, 2002, … , 2006. Using this data we concluded that house prices will always go up. Banks started lending subprime loans based on this assumption. The result was a financial crisis. The S&P/Case-Shiller 20-City Composite Home Price Index given below should tell you the story.
Similarly real estate prices in major Indian cities have gone up since 2000, 2001, 2002, … Based on this data most of us have come to a conclusion that the prices will always go up. Is this true? I do not know. But I know that you cannot apply mathematical induction to these kinds of problems.