Mathematical Induction

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

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. Proof by induction requires two steps:

__Base case__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)/2

which is true.__Inductive step__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)). 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

The 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+1**= k(k+1)/2**+ k+1**k(k+1)/2 + k+1 = k(k+1)/2 + 2(k+1)/2 = (k(k+1) + 2(k+1))/2 = (k

Thus we have shown P(k+1) given P(k), so the proof by induction is complete.^{2}+ k + 2k + 2)/2 = (k^{2}+ 3k + 2)/2 = (k+1)(k+2)/2

__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.

__Base case__(n=1):2

^{1}> 1, so the base case holds.__Inductive step__: If 2^{k}> k then 2^{k+1}> k+1.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:

2

But we're trying to show that 2^{k}> k => 2^{k}* 2 > k * 2 => 2^{k+1}> k * 2^{k+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 2^{k+1}> k * 2, so we can conclude that 2^{k}* 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.