This kind of argument is supported by the First Principle of Mathematical Induction, which says the following:
IF 1. P(b) is true for some integer b, and 2. If P(k) is true then P(k+1) is true, for all k >= b THEN P(n) true for all n >= b
(1) is called the base case, and (2) is called the inductive step. So we need to provide that both a base case and the inductive step are true for our property P to prove that P is true for all integers greater than or equal to the base case.
For example, the property P(n) might be that 1 + 2 + ... + n = n(n+1)/2, and we might want to show that it's true for all n >= 1. We could prove this by induction by proving the two steps above:
Prove that the property is true for the base case b, that is, P(b). For this example the base case is 1, so we simply check P(1),
1 = 1*(1+1)/2which is true.
Show that IF the property is true for some arbitrary value k, then it must be true for k+1 as well. Note that what we are proving here is the implication P(k) -> P(k+1)(if P(k) then P(k+1)). Said another way, we need to prove P(k+1) given P(k). We aren't concerned with whether or not P(k) is actually true; we just show that if it is true, then P(k+1) must be true as well. P(k) is called the inductive hypothesis. For this example:
P(k): 1+2+ ... + k = k(k+1)/2 (inductive hypothesis -- assume true) P(k+1): 1+2+ ... + k + k+1 = (k+1)(k+2)/2 (need to show this given P(k))How to prove P(k+1) given P(k)? Fortunately, the left side of P(k) is often very similar to the left side of P(k+1); in this case they differ only by k+1. Since we know that P(k) is true, we can add k+1 to both sides of that equation and still have a true statement:
1+2+ ... + k + k+1 = k(k+1)/2 + k+1The left side now looks like the left side of P(k+1). The right side looks different, but maybe they're just in different forms. We can transform the right side as follows:
k(k+1)/2 + k+1 = k(k+1)/2 + 2(k+1)/2 = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2Thus we have shown P(k+1) given P(k), so the proof by induction is complete.
Base case (n=1): A fence with a single post (|) has 0 sections.
Inductive step: If a fence with k posts has k-1 sections, then a fence with k+1 posts has k sections.
Proof: A fence with k+1 posts has a fence with k posts embedded in it.
|-|-|-| ... |-|-| \______________/ k postsBy the inductive hypothesis, a fence with k posts has k-1 sections. But a fence with k+1 posts has just one additional section (see diagram), so it has k-1+1 = k sections. This completes the proof by induction.
21 > 1, so the base case holds.
Starting with the inductive hypothesis (the k case), we notice that the left side looks like the left side of the k+1 case but is smaller by a factor of 2. So multiply both sides of the inductive hypothesis by 2, which maintains the inequality:
2k > k => 2k * 2 > k * 2 => 2k+1 > k * 2But we're trying to show that 2k+1 > k + 1, and we can't turn k*2 into k+1. However, note that for all k>1, k*2 is bigger than k+1, so anything that is bigger than k*2 must be bigger than k+1 as well. We have already shown that 2k+1 > k * 2, so we can conclude that 2k * 2 > k + 1.
There is another form of mathematical induction, called the Second Principle of Mathematical Induction, that is often useful. It says the following:
IF 1. P(b) true (for some integer b) 2. P(r), b<=r<=k, true -> P(k+1) (k >= b) THEN P(n) is true for all n >= b
The Second Principle is different in the second rule, which assumes not only that P is true for k, but that P is true for all values from b to k. This sounds like a stronger condition, but it turns out that the First and Second principles are actually equivalent. Depending on the problem, it just may be more convenient to use one form over another.
Base case: A fence with a single post (|) has 0 sections.
Inductive step: If a fence with r posts, 1<=r<=k, has r-1 sections, then a fence with k+1 posts has k sections.
Proof: A fence with k+1 posts can be divided into two parts, each of which has at least one post (since k>=1). If we say that the left part has x posts, then the right part must have the rest of the posts, that is, (k+1)-x posts.
|-|...|-|...|-| (k+1) posts total \______/ \_____/ x posts (k+1)-x postsSince each part has at least one and not more than k posts, the inductive hypothesis applies to each part. So by the inductive hypothesis, the left part has x-1 sections and the right part has k+1-x-1 sections. The whole fence, which has k+1 posts, has the sections in the left plus the sections in the right plus the section that joins them together:
x-1 + k+1-x-1 + 1 = k sections. | | | | left right join totalThis completes the proof.
Base cases (n=8, n=9, n=10): 8=3+5; 9=3+3+3; 10=5+5.
Inductive step (second principle): If any amount of postage r, 8<=r<=k, can be built using only 3-cent and 5-cent stamps, then postage k+1 can be built using only 3-cent and 5-cent stamps.
Proof: Cases k=8, k=9, and k=10 were proved in the base case, so here we can assume that k+1 >= 11. By the inductive hypothesis, we know that the postage for k-2 can be formed using 3-cent and 5-cent stamps since (k+1)>=11 => (k-2)>=8. Now take the postage for k-2 and add a 3-cent stamp; this gives the postage for k+1, completing the proof.