A Simple Example

We begin with a simple example. Consider the following code snippet (some variant of which you must have seen and used many times):

					for( i=0; i< n; i++)
						for(j=0; j<= i; j++)
							print("Blah");
				

It is not too hard to see that for each value of $i=0,1,\dots,n-1$, the index $j$ goes from $j=0,\dots,i$. That is, the index $j$ takes on exactly $i+1$ distinct values. Further for each such distinct pair $(i,j)$, the code above prints Blah exactly once. Thus, the total number of times Blah is printed is exactly \[\sum_{i=0}^{n-1} (i+1) = \sum_{i=1}^n i = 1 +2 +\cdots +n.\] While the sum $1+2+\cdots n$ is a valid answer it is not that useful especially when we would like to do some asymptotic analysis. Further, for purely aesthetic reasons it would be nice to have a closed form expression. And indeed there is one:

Below is a Khan Academy video for the same proof:

Two Digressions

The Historical Digression

I will start the discussion about the history behind Lemma 1 with an alternate proof (idea) for Lemma 1:

If you need practice on writing proof details, write the proof details for the proof idea above as an exercise. If not or if you want to see the proof details, click here.

Here is the Khan academy video of the same proof as above (stated in a slightly slicker way)

It is claimed that Gauss discovered this proof when he was seven(!) years old. The story goes that Gauss' math teacher wanted to keep his students busy and asked them to calculate $1+2+\cdots+100$, thinking that they would manually add the $100$ numbers. Apparently, Gauss figured out the quick proof and the identity above and promptly came up with the correct answer. (See this article for a more detailed account of this incident.)

The Algorithmic Digression

Pft, you say. What is the big deal with the problem above (and what does Lemma 1 have to do with this)? You can easily solve the problem as follows.

						//Input is A[0], ..., A[n-2]

						check = new bool[n]; //We will assume that the index starts with 1

						for(j=1; j<= n ;j++)
							check[j]=false;

						for (i=0; i< n-1;i++)
							check[A[i]]=true;

						for(j=1; j<= n; j++)
							if(!check[j])
								return j;
					

With the current definition of the problem, the solution above is perfectly fine. However, say you want to solve this problem on a router that has to solve the problem for say $n=10^6$ (think a large file is being sent that is divided into $10^6$ packet and one of them is missing and the router wants to find out which one). As you might imagine, router have to work extremely fast and be extremely light-weight. In particular, we want to find out the missing number but with the following additional constraints:

1. The algorithm/router can look at each number/packet only one and in the order it receives them, i.e. make one pass over the data.
2. The algorithm can only use $O(\log{n})$ temporary space (this is enough to store the IDs of a few packets by the router but no more).
3. The algorithm/router needs to output the missing $j$ in $O(\log{n})$ time once it was received all the numbers/packets.

Unfortunately the algorithm above does not meet the last two criteria (though it does satisfy the first one). Indeed check has n entries (and hence the algorithm uses $\Omega(n)$ space) while lines 11-13 can take $\Omega(n)$ time in the worst-case to output the missing number. It turns out that one can use Lemma 1 to design a streaming algorithm to solve the missing number problem:

If you are curious about streaming algorithms, this survey by Muthu Muthukrishnan is perhaps the best place to start. (As a bonus it also solves the exercise above.)

Types of Inductive Proofs

It turns out that the inductive proof of Lemma 1 we saw above is what is known as mathematical induction . The main idea here is that whatever statement you are trying to prove holds for every natural number $n$. For Lemma 1, the statement is the identity that we need to prove. In other words, for each value of $n$ there is only one statement that we need to prove. In other words, the proof is very "linear". To illustrate what we mean consider the animation below, which repeats the inductive step till $n=19$. (Click the "Next" button to perform one inductive step. $S(n)$ denotes the sum $\sum_{i=1}^n i$ and the sum $S(n-1)$, while computing $S(n)$, is denoted in red to highlights where the induction hypothesis is used.)

Before we move on to the next kind of induction proof, here is a fun exercise for mathematical induction:

Sentences involving repetition of "buffalo" are attributed to our very own Bill Rapaport : see his Buffalo buffalo buffalo buffalo buffalo page. If you need a solution sketch for the exercise above, this page has an outline.

Structural Induction

An Example With Trees

We will consider an inductive proof of a statement involving rooted binary trees. If you do not remember it, recall the definition of a rooted binary tree: we start with root node, which has at most two children and the tree is constructed with each internal node having up to two children. A node that has no child is a leaf.

Recall that the depth of a rooted binary tree is the maximum number of edges it takes to go from the root to any leaf. Consider the following problem:

Note that in the above there is a parameter/number: the depth $d$. However, when we do induction, we will not just do induction $d$ instead we will do induction on all binary rooted trees of depth $d$.

Proof Idea

We will induct on depth $d$ (or more precisely on binary rooted trees of depth $d$). As usual, the interesting part is proving the inductive step, where we are in a situation as below:

In the above, the root $r$ has up to two children: let the subtree rooted at the left child be called $T_L$ and the subtree rooted at the right child be called $T_R$. The main observation is that if the original tree has depth $d$, then both $T_L$ and $T_R$ have depth at most $d-1$ and thus, we can apply induction on these subtrees.

Comparison with structure of proof of Lemma 1

As noted earlier, the structural induction proof above is not "linear" as the mathematical induction proof of Lemma 1. To illustrate this, consider the animation below. It runs the inductive step in the proof above for $d=0,1,2$ (each row corresponds to the same $d$). (Click on "Next" to perform the next inductive step: the animation resets after all the $d=2$ rooted trees have been considered.) The green shaded tree is the current tree of the inductive step, the left sub-tree $T_L$ is denoted by red shaded tree, $T_R$ is blue shaded and if $T_L=T_R$ then it is shaded pink.

Analyzing the Merge algorithm

In the previous example of structural induction for each value of the induction parameter $d$, there were multiple objects (i.e. trees of depth $d$) but for each value of $d$, there were only a finite number of objects. However, one can do structural induction when the parameter can have infinitely many objects associated with it. In fact, if you have read the page of asymptotic analysis you have already seen such an example. For completeness, we reproduce that proof here.

We start off with the problem we want to solve:

The following algorithm is the well-known Merge algorithm that solves the above problem in time $O(m+n)$.

                       	int [] Merge (A, n, B, m)
                        //Combine two sorted arrays (A of size n and B of size m) into one sorted array of size m+n
                     	{
                                int C = new int[m+n]; // Initialize the array to be returned

                                i=j=k=0;

                                while (i< n and j< m) // Repeat while neither A nor B has been exhausted
                                {
                                        if(A[i]<B[j])
                                                C[k++] = A[i++];
                                        else
                                                C[k++] = B[j++];
                                }

                                while (i< n) //A has not been exhausted
                                        C[k++]=A[i++];
                                while (j< m) //B has not been exhausted
                                        C[k++]=B[j++];

                                return C;
                        }
                 

Recall that we have show that on input A with n elements in sorted order and B with m sorted elements, Merge returns the union of the m+n elements in sorted order (or equivalently the array C returned in line 21 has the elements of A and B in sorted order). We will prove this by induction. As mentioned earlier this will be a (structural) induction proof where for each value of m+n there are infinite possibilities for A and B.