we shall look at a well known problem which we will use Induction to simplify till we arrive at an efficient solution.
Mathematical Induction
Mathematical Induction is a proof technique that is used to establish a claim or statement mostly over the set of Natural numbers. It can be likened to a Domino set such that pushing down the first one, pushes down the next one and so on.
One of the common ways it is formulated is,
Let T(n) be a statement defined for n > 0, we want to prove T(n) for all natural numbers. It is sufficient to show that
1. T(1) is true.
2. Assume that if T(n-1) is true and we can show that T(n) is true then the statement is true for all n.
Why is it important
Sometimes, solving a problem directly can be harder and using Induction solves the problem easily. Induction can also make it easier to reason about the correctness of recursive algorithms.
It can help to prove certain theorems which solving directly might be more difficult.
In addition, Induction can give insight into more efficient ways to solve a problem and It is this last usage that I want to talk about with a popular problem.
Problem
Given a sequence of real numbers (a0, a1, a2, ..., an) and a real number x, find the value of the polynomial F(x,n) = a[n]*x^n + a[n-1]*x^(n-1)+ ... a[1]*x + a[0].
Solution 1
For n = 0, F(x,0) = a[0]. For n = 1, F(x,1) = a[1]* x. This is trivial.
Suppose that we know how to solve F(x, n-1) = a[n-1]*x^(n-1)+ ... a[1]*x + a[0]. How do we compute F(x, n) ?
Can you notice that the only term missing is a[n]*x^n ? So all we need to do is add that term and we are done.
F(x, n) = F(x, n-1) + a[n]*x^n.
While this is correct, It is too slow! The total number of multiplications performed is n + (n-1) + (n-2) + ... + 1 = O(n^2). The main reason why it is slow is that we keep on computing x^k each time.
Can we cache previous computations to improve this solution ?
Solution 2
Let us make our Induction hypothesis stronger. It turns out we can make our solution more efficient If we use a stronger Induction.
Suppose we know how to calculate F(x, n-1) and we also know how to calculate x^k for some k > 0.
Can we solve F(x, n) ?
Since we know how to calculate x^k efficiently. This is possible if we cache a previous computation of x^k and use it in the next loop iteration.
x^k = x * x^(k-1)
F(x, n) = F(x, n-1) + a[n]*x^n.
Since at each step we are only doing two multiplications, then we have a total of
2 + 2+ ... 2 = 2*n = O(n) operations in total. Now this is faster.
But Can we still do better ?
Solution 3
I will attempt to give a different Induction hypothesis that turns out to give better results overall.
In the previous solutions , we have gone from (a[n-1], a[n-2], .. a[0]) to (a[n],a[n-1], a[n-2], .. a[0]).
Now we will go from (a[n], a[n-1], a[n-2], .. a[1]) to (a[n], a[n-1], a[n-2], .. a[1], a[0]) and show that the second formulation is better. Please take a moment to consider the difference.
Suppose we know how to solve F(x, n-1) = a[n]*x^(n-1) + a[n-1]*x^(n-2)+...a[1], can
we solve F(x, n) ?
Yes, It is straight forward.
F(x, n) = x*F(x,n-1) + a[0].
Phew! This solution is more efficient than the last one because it does one multiplication instead on two per iteration. So that is a total of 1 + 1 + 1 + ... + 1 = n = O(n).
This solution is called Horners rule and its the fastest out of the three solutions.
Can we do better ? I leave that to you.
Conclusion
As you can see, there are several ways to frame an Induction hypothesis. Mathematical Induction allows us to break down a problem in terms of smaller sub-problems whose solutions can be combined to give the solution of the bigger problem.
Cheers!
