~INDUCTION~

mirrorball


This is one of the most powerful tools of mathematics. It's used quite extensively in higher mathematics for proving expressions involving n cases.
(i.e., expanding formulas from 2 & 3 dimensions to the nth dimension)

It also gives us a way of working in higher dimensional spaces.  Generally
speaking, there are no visuals in 4-D, 5-D, 6-D, & so on, but we can still work in them with equations & formulas.

It gives a valid way of generalizing without committing the typical fallacy of "hasty generalization". It is a very powerful & remarkable method.

To understand the logic behind this method, think of an infinite row of standing dominoes, spaced perfectly, so if you tip over the 1st, it will tip over the 2nd & the 2nd will tip over the 3rd, & so on....all dominoes will fall (if the spacing between them is correct. ( /->|->|->|->......)

Think of a dominoe falling as an expression being true for that case.
(i.e., 2nd dominoe falls means expression is true for n=2, 3rd dominoe falls means the expression is true for n=3, & so on)

Our goal is to have the expression true for all values of n. So, our goal is to show that all the dominoes fall.

How do we get all the dominoes to fall? First show that the 1st one falls. That would be equivalent to showing that the expression is true for n=1. We could do that just by substituting n=1 into the expression & showing that it holds (is true).

Now, for the tricky part. We must show that the spacing between any 2 dominoes is correct. What does that mean? It means, no matter where we are, let's say at the kth dominoe, if it falls, does it tip over the next one? The next one is the (k+1) dominoe. If dominoe k knocks down dominoe k+1, no matter what k is, then all will fall & the expression is true for all n. Because, if k=1, then 1st knocks down 2nd, then 2nd knocks down 3rd, & so on.

Showing k tips k+1 is the key. In words, it goes this way, "if k falls, does it
tip k+1?" This is an implicative statement. We assume the if part then we show the then part follows. (i.e., assuming the kth falls, does it knock over k+1?) Which means, if we assume the expression true for k (kth falls), can we then prove it true for k+1 (k+1 falls)? If so, then the expression will be true for all positive integers n (our goal).

Here we go. Our first induction proof.

Since 1= 12, 1+3=22, 1+3+5=32, one might guess that

        1+3+5+...+(2n-1) = n2     That would be a very good guess, right?

Note the expression (2n-1) gives the last term of our sum, where n stands for the number of the term. (i.e., if n=3, we have a sum of the first 3 terms & the expression (2n-1) will be 5, the last term. Then n2 would be 32 or 9, the sum of the 1st 3 terms.

Now, let's prove it by math induction on n.

1) Does the 1st dominoe fall? 
(i.e., is the expression true for n=1?),   1=12? yes.

2) Assume the kth dominoe falls.
(i.e., assume the expression true for n=k)   

Note:  k can be anywhere along the line. Just sub k in for n.  

   1+3+5+...+(2k-1)=k2  (we accept this & can use it)

3) Does the kth dominoe knock down the next one, k+1? 

(Must show the expression true for n=k+1). 

Using the expression in 2) & any permissible math technique(s), 
can we show the expression holds for k+1?

There are several different approaches to show step 3. One of which is adding the same expression to both sides of 2. It is always good to know what you are after or want to show. 

Here is what we want to show. (expression true for k+1)

  1+3+5+....+(2k-1)+[2(k+1)-1]=(k+1)2   (can't use this, however)

Note: The term after (2k-1) would be [2(k+1)-1] 
          (just increase k by 1] this is (2k+1).

So, to get it 3), add the quantity (2k+1) to both sides of our assumption 
in 2).

It's reasonable to do this since, by adding (2k+1) to both sides, the left side of 2) becomes the left side of what I want to show. 

Now, does the right side come out to the right side of what I want? 
If it does, we are done.

We get,  1+3+5+...+(2k-1)+(2k+1)= k2 +(2k+1)

which is the same as:   1+3+5+...+(2k+1)= k2+2k+1 

(don't need to write the term before the last one on the left side)

Since k2+2k+1 = (k+1)2 , we have                    

1+3+5+...+(2k+1)= (k+1)2 , yippee!

Note that this is the original formula when k+1 is in the formula for n.

We have just shown that the expression is true for n=k+1, if true for n=k. That means all dominoes will fall---> expression is true for all n.

This is one of the simplest induction proofs, some are lengthy & require much fooling around to get that 3rd step. However, the logical structure of all of them has been described in this essay.

Hope you enjoyed this little lesson on mathematical induction. Save it for future reference.