Permutation and Mathematical Induction

Last post, I show how basic mathematical induction works. Now, I am going to use it to prove that an algorithm is work correct. In this case, we are going to prove a permutation algorithm, which take an array of unique numbers L, and return an an array of all permutations of L. Let call it perms(L). For example:

1. If L = [ ], then perms(L) would be [ [ ] ].
2. If L = [1, 2, 3], the result of perms(L) will be an array [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Note: the arrary could be any order.

The algorithm that I am going to prove is shown here:

 1: def perms(L)
 2:   return [[]] if L.size == 0
 3:   result = []
 4:   L.each do |elm|
 5:     L1 = L - [elm]
 6:     perms(L1).each |p|
 7:       p1 = [elm] + p
 8:       result << p1
 9:     end
10:   end
11:   return result
12: end

The exact statement that I want to prove to you is: for any given array L of size n, the perms(L) is an array of all size-n permutation of L.

First, basis step: Let L = [ ]. The L.size will be 0. Then the perms(L) will return immediately with value [ [ ] ], which is the array of all size-0 permutation of L.

Inductive step: Let assume statement is true for any array with size n. We have to show that for any array L of size n+1, perms(L) will return an array of all size-(n+1) permutation of L.

Chinese Abacus and Mathematical Induction

When I was a kid, I used to practice Chinese Abacus every day. Me and my brother turn this boring practice into a competition, and the winner is the person who can do 1 + 2 + ... + 100 faster! Of course, it's has to be correct. At that time, we were told that the correct value is 5050, and we did not question about it.

Now, I kinda wonder, if I am going to proof to some one that 1 + 2 + ... + 100 = 5050, how can I do that?  Here one way to do it.

First line up two line of sum this way, one from 1 to 100, another from 100 to 1.

  1 +   2 +   3 + ... + 100
100 +  99 +  98 + ... +   1
---------------------------------------
101 + 101 + 101 + ... + 101 = 101 * 100

Then, sum each column. As you can see, sum value in each column is equal 101. Since we know that there is going to be 100 column. So the sum of the last line, which is sum of those two line, is 101 * 100. Because we start with 2 lines,  the sum of  \(1 + 2 + 3 + ... + 100\) = \(101 \cdot 100 / 2 = 5050 \).

This way, we can also show that, for any given interger \(n \ge 1\)
$$ \displaystyle\sum_{i=1}^{n} i = 1 + 2 +  ... + n = \frac{n\dot(n+1)}{2}$$
Nice!, It's probably require a genius to come up with the proof like this, don't you think?

Another way, we can use mathematical induction to proof this statement too. It's more systematic, and can be generalize to prove more complex statements. The proof by mathematical induction has two parts, basis step and induction step. Basically, we have to show the basis is true, then show if any given number is true, then the next one also true.