Complete induction

Week 2 : Complete induction.

Complete induction is mostly required in solving problems with questions that require us to combine smaller elements such as binary trees.

P(n) : Every rectangular array of chocolate m*n squares can be broken up in mn – 1 tries.

For a rectangular array to exist, the dimensions must be bigger than zero. Therefore, the predicate implies that we only have to prove it in the set of positive natural numbers in terms of either m or n.

For complete induction, we always work under the assumption that for all natural numbers i, if i is strictly smaller than n, then P(i) is true.

Then we prove the most basic case in the set of natural numbers which is n= 1
Therefore, if there is a rectangular array of m*1 squares, then to break it up in to 1*1 pieces, we will have to break it m-1 times because all m number of chocolate pieces are joined in a straight line and to break them in to single pieces, there is m-1 joints to separate.

Next in the inductive step, we consider arrays where n > 1
         An array of size m*n can be made by joining an array of m*1 and m*(n-1). Since we assumed that for all i<n, P(i) is true, then the array of m*1 requires (m-1) breaks to separate in to single pieces while the array of size m*(n-1) requires [m(n-1)-1] tries. When these two are combined, that requires one more break in the resulting array of size m*n to be broken off in to single pieces.
So, the array m*n will in total require (m-1) + (m(n-1)-1) + 1 number of breaks which equals (mn -1).
         Thus, for an array of size m*n, mn-1 tries are required to be broken up in to single pieces.
         Therefore, P(n) is true if n > 1

We proved that the predicate is true for both the conditions. So now, the results can be extended to the conclusion that every rectangular array of chocolate m*n squares can be broken up in mn – 1 tries