Induction

From Math Images

Jump to: navigation, search
This is a Helper Page for:
Graph Theory
Pascal's triangle

Contents


Basic Method

Just as one domino knocks the other over, each proposition P(k) implies the next, P(k + 1).
Just as one domino knocks the other over, each proposition P(k) implies the next, P(k + 1).
Induction is a useful method of mathematical proof ordinarily used for statements that connect to the sequence of natural numbers. The principle of induction first involves proving a claim for a simple case, usually the first one in the sequence. Then, it must be shown that if any case later in the sequence is true, then the next statement in the sequence must also be true. A trail of dominos is a common analogy for the principle of induction. Imagine a long trail of dominos. They are close enough that if the first domino in the line were to fall, the rest would also fall. The "first domino" is the most trivial case, and the fact that one domino will knock over the next domino represents the bulk of the proof: showing that the other cases then follow from the simplest case.[1]

Let's imagine a series of propositions, P(1), P(2), ... P(n). In our analogy, the dominos are each of the propositions. We can first prove P(1) (the first domino falls). Then we prove that P(k) implies P(k + 1) for some number k ≥ 1 (the dominos will knock each other over). Thus, P(1) implies P(2), and P(2) implies P(3), etc. Thus, all of the dominos will fall, and we will have proved all of the propositions. If n is the variable we are using for the induction proof, the process is usually called induction over n.

Here is an outline for an induction proof.

1. State the general proposition P(n).

2.a.State the base case P(1), the first case for which the proposition is true.
b. Prove the base case.
3.a. State the induction hypothesis, which says that "If P(k) is true, then P(k + 1) is true for k ≥ 1." The next two steps will prove this statement.
b. Assume that P(k) is true.
c. Using the truth of P(k), show that P(k + 1) is then true.

4. State that all the cases P(n) have been proved by Induction. The proof is complete!

Since the propositions have to correspond to sequence of natural numbers, the claims that induction can prove always involve integers in some way. Furthermore, induction is most useful when traditional algebraic manipulation is not enough.

It is best to see an example to understand induction more fully.

Examples

The equation for the sum of the first n integers is a good example, since it is difficult to prove with algebra and involves integers. Here is the proof for the following equation:

 \sum_{i=1}^n i=1+2+3+\dots+n=\frac{n(n+1)}2

First, we will prove the base case, where n = 1. The sum here is simply 1. In the formula we have

\frac{1(1+1)}2=\frac{2}2=1

Thus, the theorem holds for n = 1. Next, we have to show that P(k) implies P(k + 1). Hence, for our induction hypothesis, we assume that case for k ≥ 1 is true.

We will prove the k + 1 case from the k case algebraically. Here is what we are assuming explicitly:

 \sum_{i=1}^k i=\frac{k(k+1)}2

Now, we will algebraically manipulate the sum for k + 1 into the formula using this fact.

 \sum_{i=1}^{k+1} i=\sum_{i=1}^k i+k+1

Substituting the for the sum, we now have:

\sum_{i=1}^{k+1} i=\sum_{i=1}^k i+k+1
=\frac{k(k+1)}2+k+1
=\frac{k^2+k+2k+2}2
=\frac{(k+1)(k+2)}2=\frac{(k+1)((k+1)+1)}2

This final expression is just the formula with k + 1 where k used to be. Thus, the truth of P(k) implies P(k + 1), and we have proved the theorem by induction.


The distributive property for numbers a, b, and c is commonly written like this:

a(b+c)=ab+ac

The sum in parentheses is between two numbers, but mathematicians and math students intuitively know that the distributive property would still hold if the sum was between 3 numbers, 6 numbers, or any number of numbers. This can be proved rigorously using induction.

This is the theorem that we will be proving, called the general distributive property:

\sum_{i=1}^n ca_i=c\left (\sum_{i=1}^n a_i \right )

The c and the ai's are all constants. Without summation notation, it looks like this:

(ca_1+ca_2+\dots+ca_n)=c(a_1+a_2+\dots+a_n)

Here is the proof that the distributive property applies to larger sums.

We are going to do induction over the variable n, which controls how big the sum is. For the base case, there are two simple options. First, n = 1. When we plug 1 into the formula for n, the formula becomes this simple statement:

(ca_1)=c(a_1)

We could also use n = 2 for our base case. In this case, we have

(ca_1+ca_2)=c(a_1+a_2)

which we also know is true because this is exactly the distributive property. So either n = 1 or n = 2 could be our base case. Now comes the inductive step. We assume that the theorem holds for n = k ≥ 1 and prove that it holds for n = k + 1.

For the induction hypothesis, here is the case for n = k, which we are assuming is true.

\sum_{i=1}^k ca_i=(ca_1+ca_2+\dots+ca_k)

Now consider the case for n = k + 1.

\sum_{i=1}^{k+1} ca_i=(ca_1+ca_2+\dots+ca_{k+1})

Now let,

\sum_{i=1}^k a_i=a_1+a_2+\dots+a_k=b

Since there is a sum of k numbers within the k + 1 sum, the induction hypothesis holds here, and we can distribute the first k terms of the total sum.

\sum_{i=1}^{k+1} ca_i=(ca_1+ca_2+\dots+ca_{k+1})
=(c(a_1+a_2+\dots+a_k)+ca_{k+1})
=(c(b)+ca_{k+1})

To this expression, we can use the regular distributive property, and then the result is almost evident.

\sum_{i=1}^{k+1} ca_i=c(b+a_{k+1})
=c(a_1+a_2+\dots+a_k+a_{k+1})

Thus, the induction hypothesis holds true and we have proven the more general distributive property!

Variants

There are actually multiple types of induction. For example, sometimes it is very difficult to show that P(k) implies P(k + 1) but it is easier to show that P(k) implies P(k + 2). However, if we completed this type of inductive step with only one base case, we would only prove every other proposition, since we are skipping over the k + 1 case. In order to compensate for the propositions we are missing, we would need two base cases, P(1) and P(2). P(1) would imply P(3), P(5), P(7), and so on, while P(2) would imply P(4), P(6), P(8), and so on. Thus we have proven all of the propositions P(n).

The same principle applies if we can show that P(k) implies P(k + 3), P(k + 5), P(k + 475) or P(k + c). We just need more base cases to compensate. If we can show that P(k) implies P(k + c) then we need the base cases to be P(1), P(2), ... P(c). These base cases, coupled with the inductive step, would prove all of the propositions and the induction would be complete.

Induction on Negative Numbers

Induction can also be completed for negative numbers. In regular induction over positive numbers, we started with the base case, and the inductive step proved all the cases from the k case imply the k + 1 case. The dominos are knocked over in the positive direction. In order to knock the dominos down in the other direction, the inductive step needs to switch directions. In order to do this, the proposition P(k) needs to imply P(k - 1). Now, if the base case is P(c), all of the propositions will be proved for numbers that are less than c. If used in conjunction with induction over positive numbers, this method could be utilized to prove a theorem for all integers.

Strong Induction

In the inductive step of the more common form, the proposition P(k) is usually shown to imply that P(k + 1). However in the strong form, we are not limited to just using P(k). We show that "P(1), P(2), ... P(k) all together imply P(k + 1)". Logically this has the same result as the common form. First we prove the base case, P(1), and then we prove the strong inductive hypothesis. P(1) implies P(2), then P(1) and P(2) both imply P(3), then P(1), P(2), and P(3) all imply P(4), etc. Thus all of the dominos will fall, and the theorem is proved for all P(n). Since we have many propositions to help us finish the inductive step, this method of induction is given the adjective "strong".

The graph theory proof that the number of vertices in a tree is 1 more than the number of edges uses strong induction. For more, see the Graph Theory page.

More Examples

Here are some examples that readers can try themselves before seeing the answer!


1.Given that for numbers a, b, and c, the following is true:

(ab)^c=a^cb^c

use induction to show that this can be generalized to:

(a_1a_2a_3\dots a_n)^c=a_1^ca_2^ca_3^c\dots a_n^c

No peeking!

We can use either n = 1 or n = 2 as the simple base case, just as with the general distributive property proof. Here is the case for n = 1,

(a_1)^c=a_1^c

which is definitely true. Here is the case for n = 2:

(a_1a_2)^c=a_1^ca_2^c

which is true because it is a given property for the problem.

Now that we have the base case proven, we do the inductive step. We assume the case for n = k ≥ 1 and show that it implies the case for n = k + 1. The case for n = k, which we are now assuming is true, looks like this:

(a_1a_2a_3\dots a_k)^c=a_1^ca_2^ca_3^c\dots a_k^c

Now let

a_1a_2a_3\dots a_k=b

Now we will use algebraic manipulation and the cases for n = 2 and n = k to demonstrate the case for n = k + 1.

(a_1a_2a_3\dots a_ka_{k+1})^c=(ba_{k+1})^c
(a_1a_2a_3\dots a_ka_{k+1})^c=(b)^c(a_{k+1})^c

which we know by the case for n = 2. Now we substitute back in the expression for a and use the case for n = k.

(a_1a_2a_3\dots a_ka_{k+1})^c=(a_1a_2a_3\dots a_k)^c(a_{k+1})^c
(a_1a_2a_3\dots a_ka_{k+1})^c=a_1^ca_2^ca_3^c\dots a_k^ca_{k+1}^c

Now that we have completed the inductive step we have proved the theorem by induction!



2. Prove the following formula for the sum of the cubes.

\sum_{i=1}^n i^3=1^3+2^3+\dots+n^3=\frac{1}4n^2(n+1)^2

Interestingly enough, note that:

\frac{1}4n^2(n+1)^2=\left ( \frac{n(n+1)}2 \right )^2=\left ( \sum_{i=1}^n i \right )^2

The equation that follows from this fact (shown below) is called Nicomachus's theorem.[2] Proving the sum of cubes formula will amount to proving Nicomachus's theorem.

\sum_{i=1}^n i^3=\left ( \sum_{i=1}^n i \right )^2

No peeking!

The general proposition P(n) is stated above. So first, we tackle the base case, where n = 1.

Our sum is simply 13 = 1. In the other half of the equation:

\frac{1}4(1)^2(1+1)^2=\frac{1}4(1)(4)=1

Thus we have established the result for the base case n = 1. Now for the inductive step. We must show that if case for n = k is true, then the case for n = k + 1 is true. So let us assume that the case for n = k ≥ 1 is true, namely:

\sum_{i=1}^k i^3=1^3+2^3+\dots+k^3=\frac{1}4k^2(k+1)^2

We will use this to imply the case for k + 1. The following process will be similar to proving the formula for the sum of the numbers from 1 to n. Consider the sum of the cubes of 1 to k + 1.

\sum_{i=1}^{k+1} i^3=1^3+2^3+\dots+k^3+(k+1)^3=\frac{1}4k^2(k+1)^2+(k+1)^3

Now we will combine the two terms and try to get the formula for the sum of cubes with k + 1 in the place of n. This will require some really fancy FOILing and factoring. In order to avoid that, we will turn this expression into a polynomial. Then we will take what the formula for the k + 1 sum of cubes should be, and show they are the same.

\sum_{i=1}^{k+1} i^3=\frac{k^2(k+1)^2+4(k+1)^3}4
=\frac{k^2(k^2+2k+1)+4(k^3+3k^2+3k+1)}4
=\frac{k^4+2k^3+k^2+4k^3+12k^2+12k+4}4
=\frac{k^4+6k^3+13k^2+12k+4}4

So, now here is our polynomial. Now, we will take what the formula for the k + 1 sum should be, and try to transform it into this sane polynomial. If we can, then the formula is thus equal to the sum for k + 1 and we will have our result. To get the formula for k + 1, substitute n for k + 1. We have:

\frac{(k+1)^2((k+1)+1)^2}4=\frac{(k+1)^2(k+2)^2}4
=\frac{(k^2+2k+1)(k^2+4k+4)}4
=\frac{k^4+4k^3+4k^2+2k^3+8k^2+8k+k^2+4k+4}4
=\frac{k^4+6k^3+13k^2+12k+4}4

And there it is, the same polynomial! We have shown by assuming the case for n = k the case for n = k + 1:

\sum_{i=1}^{k+1} i^3=\frac{(k+1)^2((k+1)+1)^2}4

Thus, the inductive step is complete, and we have proven the theorem for all n by induction. If you want to know more about sums of powers, then consult this page.



3. Show that for any integer n > 0, the number 169n + 6 is divisible by 7.

No peeking!

In this problem, our base case would be n = 1. We have:

169^1+6=169+6=175
\frac{175}7=25

Thus, the theorem holds for n = 1. Before we move onto the inductive step, we actually require one more fact. Let us consider 169 divided by 7. Since we have to add 6 in order to make a number that is a multiple of 7, we know then that 169 divided by 7 has a remainder of 1. We will apply this reasoning later in the proof.

Now for the inductive step. We have to show that if 169k + 6 is divisible by 7, then 169k + 1 + 6 is divisible by 7. Then, we assume that 169k + 6 is divisible by 7. As before, this also means that we are assuming that 169k divided by 7 has a remainder of 1.

Now let's consider the case for k + 1.

169^{k+1}+6=169(169^k)+6

For one moment, let us consider just 169(169k) without the 6.

As we have shown in the base case and assumed in the induction hypothesis, both 169 and 169k have a remainder of 1 when divided by 7. When we multiply two numbers of this kind, we will get another number with a remainder of 1 when divided by 7. Click below to see why.

Let's imagine two numbers that when divided by 7 have a remainder of 1. This means that they are each 1 greater than a multiple of seven. Thus, they both have the following form, where n is a positive integer.

7n+1

When we multiply two numbers of this form, the result will be evident. Let a and b be positive integers. In order to simplify the expression, we will use the FOIL method.

(7a+1)(7b+1)=49ab+7a(1)+7b(1)+(1)(1)
=49ab+7(a+b)+1
=7(7ab+a+b)+1
This final expression is a number of the form 7n + 1, where the 7ab + a + b is the n. This means that it is a number that has a remainder of 1 when divided by 7, like the original two numbers! Thus, we have shown that when two numbers that have a remainder of 1 are multiplied, the resulting number has the same property.

Thus the number 169(169k) has a remainder of 1 when divided by 7. As we have shown before, this means that it is 6 less than a multiple of 7, and adding 6 to this number will yield a multiple of 7. Thus, we have established the case for n = k + 1 as a multiple of 7. We have completed the inductive step and proven that numbers of the form 169n + 6 for n > 0 are all divisible by 7 through the induction method.



4. Show that any number n ≥ 12 can be made by a sum of a multiple of 4 and a multiple of 5 (where 0 counts as a multiple of both).

No peeking!

This is a case of induction where we need more than 1 base case. Actually, the proof requires 4 base cases, where n is 12, 13, 14, and 15.

4(3)+5(0)=12+0=12

4(2)+5(1)=8+5=13

4(1)+5(2)=4+10=14

4(0)+5(3)=0+15=15

Thus we have established the 4 base cases we need. Now, in the inductive step, the induction hypothesis is "if P(k) is true, then P(k + 4)" is true. So we assume the P(k) case and show that case for k + 4, where k ≥ 12. This method is discussed in the "Variants" section.

So we are explicitly assuming the following, where a and b are nonnegative integers:

k=4a+5b

This inductive step isn't too hard. We have the following equation which quickly shows the result.

k+4=4a+5b+4

k+4=4a+4+5b

k+4=4(a+1)+5b

Thus the case for k + 4 has been shown from P(k) and we have shown the result.[3]


References

  1. Maurer, Stephen B. Discrete Algorithmic Mathematics". A. K. Peters Ltd. Wellesley MA: 2004.
  2. Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, p. 82, 2003.
  3. http://www.cs.cornell.edu/courses/cs312/2002sp/handouts/induction/induct-examples.html
Personal tools