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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.