How to Do Induction Proofs

Опубликовал Admin
29-09-2016, 01:15
451
0
Mathematical induction is a method of mathematical proof founded upon the relationship between conditional statements. For instance, let us begin with the conditional statement: "If it is Sunday, I will watch football." You could make a following statement that: "If I am watching football, I will order takeout." You could follow that statement with another: "If I am ordering takeout, I will not cook." From these, you could validly conclude that: "If it is Sunday, I will not cook," because of the logical relationship between these conditional statements. If you can prove the first statement in a chain of implications is true, and each statement implies the next, it naturally follows that the last statement in the chain is also true. This is how mathematical induction works, and the steps below will illustrate how to construct a formal induction proof.

Using "Weak" or "Regular" Mathematical Induction

  1. Assess the problem. Let's say you are asked to calculate the sum of the first "n" odd numbers, written as [1 + 3 + 5 + . . . + (2n - 1)], by induction. (The last term here derives from the fact that if you double any number and then subtract 1 from that value, the resulting number will always be odd.) At first, you might notice that the sum of consecutive odd numbers seems to follow a pattern (e.g., 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16; 1 + 3 + 5 + 7 + 9 = 25). The sum seems to be the number of odd numbers you are adding squared, right? Now that we have an idea of the pattern at play here, we can begin our proof.
  2. State the property that will be proved using induction. In our example, we have noticed a pattern relating to the sum of the first "n" odd numbers. To complete the task we are assigned (i.e., calculating the sum of the first "n" odd numbers), we could actually take the time to write out all the odd numbers, starting with 1 all the way to "n," and add them up. But there is an easier way. Based on what we observed about the first few summations we did, we could offer this property, which we will try to prove via induction:
    • 1 + 3 + . . . + (2n - 1) = n^2
    • We will refer to this property as P(n), because "n" is the variable we used above.
    • The left-hand sign of the equation represents the sum of the first "n" odd numbers, beginning with 1.
  3. Understand the concept behind mathematical induction. It is helpful to think of induction in terms of dominoes, which recalls the "chain of implications" discussed in the introduction above. Think of every value of "n" in the property above, P(n), as an individual domino, arranged in a line. If we can show that P(1)—the first value in the chain—is true, that means we can knock over the first domino. Further, if we assume that any one domino can be knocked over (i.e., P(n) holds true for some arbitrary value of "n") and, with that assumption, that the following domino can also be knocked over (i.e., P(n + 1) is also true), that means we can knock over all the dominoes with our stated property. This means the property is true in all cases and we have achieved our goal through induction.
  4. Prove the base case for the property holds true. The "base case" for a particular property is some small value used to show that the first statement of the property holds true. In this case, we will use "1," as this is the first odd number and easy to work with. If the property holds true for the base case, we will have shown we can knock over the first domino and we can move on to the next step.
    • P(1): 1 = 1^2
    • P(1): 1 = 1 (It held, we're good. First domino down.)
  5. State the inductive hypothesis. The next step of induction involves making an assumption. In our example, we will assume that for some arbitrary value of "n"—let's say "k"—that the statement is true. That is, we have faith that our property will hold regardless of the value used for "n." If this wasn't true, our property (i.e., our solution to the original problem of calculating the sum of the first "n" odd numbers) wouldn't have much use. While we haven't proved anything yet, this assumption is important, and takes the following form:
    • P(k): 1 + 3 + . . . + (2k - 1) = k^2
    • Remember that we are assuming this is true going forward in the proof (i.e., that we can knock over any individual domino in the chain).
  6. Prove the inductive hypothesis holds true for the next value in the chain. In other words, we assume that P(k) holds true and, using that assumption, try to prove that P(k + 1) also holds true. If we can do that, we have proven that our theory is valid using induction because if knocking down one domino (assuming P(k) is true) knocks down the next domino (using that assumption, proving P(k + 1) is also true), all the dominoes will fall and our property will be proved valid. So let's try that:
    • P(k): 1 + 3 + . . . + (2k - 1) = k^2 is true.
    • P(k + 1): 1 + 3 + . . . + (2k - 1) + (2(k + 1) - 1) = (k + 1)^2
    • The italicized portion above on the left-hand side of the equation represents the addition of the next odd-numbered term in the sequence, k + 1. If we can make that left-hand side equal the right-hand side, we will have succeeded.
    • From our assumption, we know that the un-italicized portion above equals k^2, so let's make that replacement.
    • P(k + 1): k^2 + (2(k + 1) - 1) = (k + 1)^2
    • P(k + 1): k^2 + 2k + 1 = (k + 1)^2
    • P(k + 1): (k + 1)^2 = (k + 1)^2
  7. Conclude the property is validly proved by mathematical induction. By use of a little algebra, we have proved that our property holds true not only for some arbitrary value of "n," but also for the value following that value. We have shown that P(1) is true, assumed that P(k) is true, and proved that, based on that assumption, P(k + 1) is also true. To use our continuing domino analogy, we successfully knocked down the first domino, showing our property has some value. Then, assuming that any arbitrary domino in the chain could be knocked over, we proved that doing so will necessarily knock down the next domino, ad infinitum down the rest of the chain. Thus, we have shown that our property holds in general and have successfully concluded our proof by mathematical induction.

Using "Strong" or "Complete" Mathematical Induction

  1. Understand the difference between the two forms of induction. The above example is that of so-called "weak" induction, named so not because of a difference in quality between the two induction methods but rather to illustrate a difference between what is assumed in the inductive hypothesis of each type of proof. The two proof techniques are actually equivalent, it is just sometimes necessary to assume more in the inductive hypothesis in order to prove the proposition at hand. To return to our domino analogy, sometimes the weight of assuming P(k) is true is not sufficient enough to knock down the domino represented by P(k + 1). Sometimes you need to be able to knock down all the dominoes before it in order to prove that your proposition holds.
  2. State the proposition to be proved using strong induction. To illustrate this, let us consider a different example. Let's say you are asked to prove true the proposition that all integers greater than 1 can be written as the product of prime numbers.
    • As before, we will refer to this proposition as P(n), where "n" is the number that can be expressed as a product of primes.
    • Since we are talking about all integers greater than 1, "n" will have to be greater than, or equal to, 2.
    • Remember that a prime number is a positive integer greater than 1 that can only be divided, without a remainder, by itself and 1.
  3. Prove the base case holds true. As before, the first step in any induction proof is to prove that the base case holds true. In this case, we will use 2. Since 2 is a prime number (only divisible by itself and 1), we can conclude the base case holds true.
  4. State the (strong) inductive hypothesis. Here is where the difference between "weak" and "strong" induction presents itself most clearly, as this step is the only difference between the two forms of inductive proof. The inductive hypothesis for "weak" induction would assume that for some arbitrary value of "n"—again, let's use "k"—that the proposition holds. We would then use that assumption to prove that the next value in the chain is true, allowing us to conclude our proposition is valid overall. However, for this proposition, assuming P(k) is true tells us nothing about P(k + 1). This type of "weak" assumption is insufficient here, so we will need to assume more. The inductive hypothesis for "strong" induction, instead of simply assuming that P(k) is true, assumes that, for all values of "n" between the base case and "k," that the proposition is true. We will use this comparatively stronger assumption (i.e., we are assuming more) to prove the proposition true.
    • This type of "strong" assumption is what differentiates the two forms of proof.
    • In this case, we will assume that, for some value of k ≥ 2, that each integer "n" such that 2 ≤ n ≤ k may be written as the product of primes.
  5. Prove the "strong" inductive hypothesis holds true for the next value in the chain. We will now use this strong assumption to prove that P(k + 1) also holds true, thereby proving the validity of our proposition overall. There are two relevant outcomes for "k + 1." If "k + 1" is a prime number, our proposition holds, and we are done. If "k + 1" is not a prime number, it will have a smallest prime factor, which we will denote as "p." Therefore, "k + 1" can be expressed as the product of "p" and some other number, "x." Since "x" will necessarily be less than "k," our inductive hypothesis tells us that "x" can be written as a product of primes, which ultimately means that—regardless of whether "k + 1" is prime or not—it can be written as a product of prime numbers.
  6. Conclude the proposition is validly proved by strong mathematical induction. Using our "strong" inductive hypothesis, we were able to prove our proposition held when "weak" induction would have been insufficient to do so. Try "weak" induction first, because the fact that you are assuming less theoretically makes the logic behind the proof stronger, contrary to the naming conventions used for these two types of proofs. Mathematically, though, the two forms of induction are equivalent.

Tips

  • In a "weak" induction proof, you are ultimately looking for a connection between P(k) and P(k + 1) to prove your proposition true. In a "strong" induction proof, you are looking for a connection between P(any value of "n" between the base case and "k") and P(k + 1).
  • If "strong" induction holds, so does regular induction, and vice-versa. Remember these two types of proofs are equivalent, and one is not inherently better than the other. "Strong" induction sometimes offers a bit of help writing out the proof when the inductive hypothesis for "weak" induction doesn't clearly prove the proposition at hand.
  • Induction works because of the Well-Ordering Principle. That is, every nonempty set of positive integers has a smallest element. In our example, that smallest element was 1.
  • Induction is normally used to prove that a property is true for all natural numbers. This means you will be working with positive integers (non-fractional, or whole, numbers).

Warnings

  • Do not forget the base cases! It is often easy to overlook this simple step, as it is quite trivial. However, your inductive proof will be incomplete without it.
  • Don't confuse mathematical induction with the concept of inductive reasoning, wherein one attempts to reach a probable conclusion based on observed evidence. Mathematical induction is actually deductive reasoning that uses logic to move from certain, clear premises to a definite conclusion.
Теги:
Information
Users of Guests are not allowed to comment this publication.