Proof by Induction

Date: 07/13/97 at 21:58:25
From: Tan Lutter
Subject: Mathematical Induction

Prove by induction on n that |A^n|=|A|^n.

I'm not sure how to do this problem at all.

Date: 07/16/97 at 04:16:49
From: Doctor Sydney
Subject: Re: Mathematical Induction

Hello!  

I'm glad you wrote. Induction can be confusing at first, but once 
you get the hang of it, it will be okay. 

You will probably remember how to do proofs by induction if you have a 
good understanding of how the proofs work. Let's quickly review this. 

Proofs by induction are commonly used when you want to prove a 
statement that depends on some variable (usually named n) for all 
positive integer values of that variable. For instance, in your 
problem you want to prove the above equality for all positive integer 
values of n. In other words, you want to show that the above equality 
holds for n = 1, n = 2, n = 3, and so on. 

How does the inductive proof do this? First, it demonstrates that 
the statement holds for the "base case" - usually the n = 1 case.  
Next, when doing an inductive proof, you assume that the statement 
holds for the kth case. What is the kth case, you may be wondering? It 
is any case. We write k because we want k to be able to represent any 
positive integer. 

Next, you prove that the (k+1)st case holds assuming that the kth case 
holds. Then the proof is done! Why? Well, think about it. In the first 
part we showed that the statement we are trying to prove holds for n = 
1, right? Then, in the second part of the proof, we demonstrate that 
if the kth case holds, so does the (k +1)st case. Combining these two 
pieces of information, we see that since the 1st case holds (as proven 
in the first part of the proof), the 2nd case must hold too (according 
to the second part of the proof); well, if the 2nd case holds (as just 
demonstrated), so too must the third case hold, right? And so on. Thus 
we have shown that the statement holds for any n.  

This will all become much more clear if we do an example. Let's look 
at your example. To show that |A|^n = |A^n| for all n by induction, we 
follow the steps outlined above.  

1. Show that the statement holds for the base case n = 1.  

When n = 1, the equation is |A|^1 = |A^1|, right? Does this equation 
hold? Yes, because anything to the first power is itself, so 
|A|^1 = |A| and |A^1| = |A|. Hence, |A|^1 = |A^1|. Thus, we have shown 
that the equality holds for n = 1.

2. Now, we assume that the equality holds for the kth case. That is, 
we assume that |A|^k = |A^k|.

3. We now want to prove that the (k+1)st case holds.  

We want to prove that |A|^(k+1) = |A^(k+1)| (**). Let's use what we 
know. In inductive proofs, proving that the (k+1)st case holds almost 
always relies on the fact that we have assumed that the kth case 
holds. So, let's rewrite the equation for the (k+1)st case in a way 
that will allow us to use information from the kth case.  

We know that |A|^(k+1) = |A|^k * |A|, right? Similarly, we have that 
|A^(k+1)| = |A^k * A| = |A^k| * |A|.

Substituting into (**), we see that we want to prove that:

|A|^k * |A| =  |A^k| * |A|

I bet you can prove that the equation above holds. I'll leave the last 
steps to you.

Once you have proved that the above equation holds, you will have 
proven that the (k+1)st case holds, and thus, the proof will be over. 

Again, the reason the proof works is as follows: First, we prove that 
the equation holds for n = 1. Next, we prove that if it holds for the 
kth case then it must also hold for the (k+1)st case. Since the 
equation holds for n = 1, it must also hold for n = 2 (the second part 
of the proof shows that if the kth case holds then so must the 
(k+1)st. Here, k = 1). But if the equation holds for n = 2, it must 
also hold for n = 3, and so on. Does that make sense to you?

Please do write back if you have more questions. Also, you might want 
to look in our archives for old questions and answers on related 
topics. To browse through or search the archives, go to the following 
URL:

   http://mathforum.org/dr.math/   

If you search using the word "induction" you can look at other 
problems that require inductive proofs. The more you are familiar with 
this type of proof the easier it will become.  

Good luck!

-Doctor Sydney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/