We are sometimes irritated when somebody does something stupid and repeatedly does so. That’s why we use the phrase “for the nth time” to describe the fact that you’ve already lost count of such things. So where does this phrase come from? I would probably think this came from mathematics and especially that technique called mathematical induction.
There are some statements in mathematics which we think to be true but we are not really sure of it. One class of these problems have something to do with statements about sequences of numbers. For example, if somebody told you that the sum the first natural numbers is equal to , would you believe it? You can either derive this result or you can try it out for a few numbers to convince yourself that it is true. But if this statement is true for the first few numbers, there is no guarantee that it will be true for all numbers. To convince ourselves, we use the mathematical induction technique.
The mathematical induction is a two step process. If you wish to prove that is true for all positive integers ,
- Basis Step – First show that it is true for
- Inductive Step – Assume that is true. Prove that is true.
When you have shown both steps to be true, then you have shown that f(n) is true for all positive integer n.
If we substitute to the above expression, we get
We have just shown that the basis step is true. Now let’s work on the inductive step. Assuming that is true, we now show that it is also true for . How do we do this? We can write as the sum of the first n terms and , that is,
Then we simplify the right hand side:
Notice that we can factor the quadratic expression of the numerator:
Now the last expression is precisely what you will get when you substitute to :
We have just shown, using the mathematical induction technique, that is true for all positive integers. Using this technique, how would you show that the binary search algorithm has running time ?