There is well known story, about a math teacher in the elementary school. He got mad and told the kids:

– Find the sum of the numbers 1 to 100! I want the answers by the end of the class!

Most of the kids started summing of the numbers as follow:

`1 + 2 + 3 + 4 + 5 + ... + 100`

Probably if they had a computer they would write simple program which calculates the sum of the numbers of 1 up to 100. The program would look as:

var sum = 0; for (var i = 1; i <= 100; i++) { sum += i; }

They constructed an algorithm with linear complexity – О(n). Obviously with this approach is quite tedious to solve the exercise on the paper.

Twenty seconds after the teacher gave the question, one kid give the correct answer. The name of the kid was Carl Friedrich Gauss – one of the greatest mathematician of all the time.

Gauss rearranged the numbers in pairs of sum 101:

100 + 1 = 101 99 + 2 = 101 98 + 3 = 101 ... 50 + 51 = 101

He noticed there are 50 pairs with sum of 101 and therefore the right answer is: `50 * 101 = 5050`

. The Gauss method is definitely faster both on paper and in form of computer program, even though the multiplication complexity is not O(1), in modern computer it’s reduced as much as possible.

Now suppose you have to write function which accepts an integer N greater than 0. It should return the sum of 1 to N inclusive.

The first algorithm apparently returns correctly the sum of the first N positive integers. The problem with it, it’s not effective, especially for big N. We should try to apply the Gauss method. The function would be:

function sum(n) { return n * (n + 1) / 2; }

The code seems pretty good, but how we can be sure it works correctly for any N? Unit tests are good, but they can test only for partial values of N. If the tests fail for particular value, we can consider the approach as incorrect.

In the our case the code work correctly for example:

sum(5); //15 sum(10); //55 sum(100); //5050

These tests return correct result, but there is no way to pretty sure that code would work with every value of N. We should use more sophisticated approach.

Mathematical induction is pretty good variant to prove the formula is valid for every N. With the method of the mathematical induction, firstly we have to prove the correctness of the formula for initial or base step of the induction. If it’s true, make inductive hypothesis for N, then using the hypothesis we will try to prove this formula is true for N+1. If we could prove it, then it’s true for every N.

So we proved the method of Gauss is valid for every value of N. Mathematical induction and strong mathematical induction are helpful tool to prove the correctness of particular algorithm. Especially the strong induction could be used to prove of more complicated and recursive algorithms.

The theory of program correctness is not start and finish with the method of induction.

Reference:

Discrete Mathematics and Its Applications