Maths Induction

MNYG4-YGCEC-3Y4WD-KMCQW-R4W96

Topics in PRECALCULUS Table of Contents | Home

26 MATHEMATICAL INDUCTION The principle of mathematical induction

THE NATURAL NUMBERS are the counting numbers: 1, 2, 3, 4, etc. Mathematical induction is a technique for proving a statement -- a theorem, or a formula -- that is asserted about every natural number. By "every" natural number, or "all" natural numbers, we mean any one that we might possibly name. See The mathematical existence of numbers.

For example, 1 + 2 + 3 + . . . + n = ½n(n + 1). This asserts that the sum of consecutive numbers from 1 to n is given by the formula on the right. We want to prove that this will be true for n = 1, n = 2, n = 3, and so on. Now we can test the formula for any given number, say n = 3: 1 + 2 + 3 = ½· 3· 4 = 6 -- which is true. It is also true for n = 4: 1 + 2 + 3 + 4 = ½· 4· 5 = 10 But how are we to prove this rule for every value of n?

The method of proof is the following. It is called the principle of mathematical induction. If 1)

when a statement is true for the natural number n = k, then it is also true for its successor, n = k + 1;

and 2)

the statement is true for n = 1;

then the statement is true for every natural number n.

For, when the statement is true for 1, then according to 1), it will also be true for 2. But that implies it will be true for 3; which implies it will be true for 4. And so on. It will be true for every natural number. To prove a statement by induction, then, we must prove parts 1) and 2) above. The hypothesis of Step 1) -- "The statement is true for n = k" -- is called the induction assumption, or the induction hypothesis. It is what we assume when we prove a theorem by induction. Example 1. Prove that the sum of the first n natural numbers is given by this formula: 1+2+3+. . . +n

n(n + = 1) . 2

Proof. We will do Steps 1) and 2) above. First, we will assume that the formula is true for n = k; that is, we will assume: 1+2+3+. .

= k(k + . 1)

. +k

2

(1)

This is the induction assumption. Assuming this, we must prove that the formula is true for its successor, n = k + 1. That is, we must show: 1+2+3+. . . + (k + 1)

=

(k + 1)(k + 2) 2

. (2)

To do that, we will simply add the next term (k + 1) to both sides of the induction assumption, line (1):

This is line (2), which is the first thing we wanted to show. Next, we must show that the formula is true for n = 1. We have: 1 = ½· 1· 2 The formula therefore is true for n = 1. We have now fulfilled both conditions of the principle of mathematical induction. The formula is therefore true for every natural number. Example 2. Prove that this rule of exponents is true for every natural number n: (ab)n = anbn.

Proof. Again, we begin by assuming that it is true for n = k; that is, we assume: (ab)k = akbk . . . . . . . . (3) With this assumption, we must show that the rule is true for its successor, n = (k + 1). We must show: (ab)k + 1 = ak + 1bk + 1. . . . . . . (4) (When using mathematical induction, the student should always write exactly what is to be shown.) Now, given the assumption, line (3), how can we produce line (4) from it ? Simply by multiplying both sides of line (3) by ab: (ab)kab

=

=

akbkab

akabkb

since the order of factors does not matter, = ak + 1bk +1 . This is line (4), which is what we wanted to show. So, we have shown that if the theorem is true for any specific natural number k, then it is also true for its successor, k + 1. Next, we must show that the rule is true for n = 1; that is, that (ab)1 = a1b1. But (ab)1 = ab; and a1b1 = ab.

This rule is therefore true for every natural number n. Example 3. Prove this formula for the sum of consecutive cubes: n²(n +

1³ + 2³ + 3³ + . . . = 1)² + n³ 4

Proof. For convenience, we will denote the sum up to n by S(n). We assume, then, that the formula is true for n = k; that is, that S(k)

= k²(k + 1)² 4

(1)

We must now show that the formula is also true for n = k + 1; that

S(k + 1)

=

(k + 1)²(k + 2)² 4

(2)

To do that, add the next cube to S(k), line (1):

S(k + 1)

= =

S(k) + (k + 1)3 k²(k + + (k + 1)² 1)3 4

= k²(k + 1)² + 4(k + 1)³

4

=

(k + 1)²[k² + 4(k + 1)] 4

-- on taking (k + 1)² as a common factor,

=

(k + 1)²(k² + 4k + 4) 4

= (k + 1)²(k + 2)² 4

This is line (2), which is what we wanted to show. Finally, we must show that the formula is true for n = 1. 1²· 1 = 3

1

2² 4

= 1· 4 4

-- which is true. The formula, therefore, is true for every natural number. Problem 1. According to the principle of mathematical induction, to prove a statement that is asserted about every natural number n, there are two things to prove. a) What is the first? To see the answer, pass your mouse over the colored area.

To cover the answer again, click "Refresh" ("Reload"). If the statement is true for n = k, then it will be true for its successor, k + 1. b) What is the second? The statement is true for n = 1. c) Part a) contains the induction assumption. What is it? The statement is true for n = k. Problem 2. Let S(n) = 2n − 1. Evaluate a) S(k) = 2k − 1 b) S(k + 1) = 2(k + 1) − 1 = 2k + 2 − 1 = 2k + 1 Problem 3. The sum of the first n odd numbers is equal to the nth square. 1 + 3 + 5 + 7 + . . . + (2n − 1) = n². a) To prove that by mathematical induction, what will be the induction a) assumption? The statement is true for n = k: 1+3+5+7 + . . . + (2k − 1) = k². b) On the basis of this assumption, what must we show? The statement is true for its successor, k + 1:

1+3+5+7+...+ (2k − 1) + 2k + 1 = (k + 1)². c) Show that. On adding 2k + 1 to both sides of the induction assumption: 1 + 3 + 5 + 7 + . . . + (2k − 1) + 2k + k² + 2k + = 1 1 = (k + 1)²

d) To complete the proof by mathematical induction, what must we a) show? T h e s t a t e m e n t i s t r u e

f o r n = 1 . e) Show that. 1 = 1 ² Problem 4. Prove by mathematical induction:

If we denote that sum by S(n), then assume that the formula is true for n = k; that is, assume S( k)

= 2k k+

.

1

Now show that the formula is true for n = k + 1; that is, show:

k+

S(k + 1)

S(k + 1)

=

=

=

= Next,

f o r m u l a i

2k + 3

.

= S(k) + The next term =

T h e

=1

s t r u f o r n = 1 :

Therefore it is true for all natural numbers.

7.4 - Mathematical Induction The need for proof Most people today are lazy. We watch way too much television and are content to accept things as true without question. If we see something that works a few times in a row, we're convinced that it works forever.

Regions of a Circle Consider a circle with n points on it. How many regions will the circle be divided into if each pair of points is connected with a chord?

2 points 2 regions = 21

3 points 4 regions = 22

4 points 8 regions = 23

5 points 16 regions = 24

At this point, probably everyone would be convinced that with 6 points there would be 32 regions, but it's not proved, it's just conjectured. The conjecture is that the number of regions when n points are connected is 2n -1. Will finding the number of regions when there are six points on the circle prove the conjecture? No. If there are indeed 32 regions, all you have done is shown another example to support your conjecture. If there aren't 32 regions, then you have proved the conjecture wrong. In fact, if you go ahead and try the circle with six points on it, you'll find out that there aren't 32 regions. You can never prove a conjecture is true by example. You can prove a conjecture is false by finding a counter-example. To prove a conjecture is true, you need some more formal methods of proof. One of these methods is the principle of mathematical induction.

Principle of Mathematical Induction (English) 1. Show something works the first time. 2. Assume that it works for this time, 3. Show it will work for the next time. 4. Conclusion, it works all the time

Principle of Mathematical Induction (Mathematics) 1. Show true for n = 1 2. Assume true for n = k 3. Show true for n = k + 1 4. Conclusion: Statement is true for all n >= 1 The key word in step 2 is assume. You are not trying to prove it's true for n = k, you're going to accept on faith that it is, and show it's true for the next number, n = k + 1. If it later turns out that you get a contradiction, then the assumption was wrong.

Annotated Example of Mathematical Induction Prove 1 + 4 + 9 + ... + n2 = n (n + 1) (2n + 1) / 6 for all positive integers n.

Another way to write "for every positive integer n" is . This works because Z is the set of integers, so Z+ is the set of positive integers. The upside down A is the symbol for "for all" or "for every" or "for each" and the symbol that looks like a weird e is the "element of" symbol. So technically, the statement is saying "for every n that is an element of the positive integers", but it's easier to say "for every positive integer n". Identify the general term and nth partial sum before beginning the problem The general term, an, is the last term on the left hand side. an = n2 The nth partial sum, Sn, is the right hand side. Sn = n (n + 1) (2n + 1) / 6 Find the next term in the general sequence and the series The next term in the sequence is ak+1 and is found by replacing n with k+1 in the general term of the sequence, an. ak+1 = ( k + 1 )2 The next term in the series is Sk+1 and is found by replacing n with k+1 in the nth partial sum, Sn. You may wish to simplify the next partial sum, Sk+1 Sk+1 = (k+1) [ (k+1) + 1 ] [ 2(k+1) + 1 ] / 6 Sk+1 = ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6 (This will be our Goal in step 3) We will use these definitions later in the mathematical induction process. We're now ready to begin.

1. Show the statement is true for n = 1, that is, Show that a1 = S1. a1 is the first term on the left or you can find it by substituting n=1 into the formula for the general term, an. S1 is found by substituting n=1 into the formula for the nth partial sum, Sn. lhs: a1 = 1 rhs: S1 = 1 ( 1+1 ) [ 2(1) + 1 ] / 6 = 1(2)(3) / 6 = 1 So, you can see that the left hand side equals the right hand side for the first term, so we have established the first condition of mathematical induction.

2. Assume the statement is true for n = k The left hand side is the sum of the first k terms, so we can write that as Sk. The right hand side is found by substituting n=k into the Sn formula. Assume that Sk = k ( k + 1 ) ( 2k + 1 ) / 6

3. Show the statement is true for n = k+1 What we are trying to show is that Sk+1 = ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6. This was our goal from earlier. We begin with something that we know (assume) is true and add the next term, ak+1, to both sides. Sk + ak+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + ak+1 On the left hand side, Sk + ak+1 means the "sum of the first k terms" plus "the k+1 term", which gives us the sum of the first k+1 terms, Sk+1.

This often gives students difficulties, so lets think about it this way. Assume k=10. Then Sk would be S10, the sum of the first 10 terms and ak+1 would be a11, the 11th term in the sequence. S10 + a11 would be the sum of the 10 terms plus the 11th term which would be the sum of the first 11 terms. On the right hand side, replace ak+1 by ( k+1)2, which is what you found it was before beginning the problem. Sk+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + ( k + 1 )2 Now, try to turn your right hand side into goal of ( k + 1 ) ( k + 2 ) ( 2k +3 ) / 6. You need to get a common denominator, so multiply the last term by 6/6. Sk+1 = k ( k + 1 ) ( 2k + 1 ) / 6 + 6 ( k + 1 )2 / 6 Now simplify. It is almost always easier to factor rather than expand when simplifying. This is especially aided by the fact that your goal is in factored form. You can use that to help you factor. You know that you want a (k+1) (k+2) (2k+3) in the final form. We see right now that there is a (k+1) that is common to both of those, so let's begin by factoring it out. Sk+1 = ( k + 1) [ k ( 2k + 1 ) + 6 ( k + 1 ) ] / 6 What's left inside the brackets [ ] doesn't factor, so we expand and combine like terms. Sk+1 = ( k + 1) ( 2k2 + k + 6k + 6 ) / 6 Sk+1 = ( k + 1) ( 2k2 + 7k + 6 ) / 6 Now, try to factor 2k2 + 7k + 6, keeping in mind that you need a (k+2) and (2k+3) in the goal that you don't have yet. Sk+1 = ( k + 1) ( k + 2 ) ( 2k + 3 ) / 6 Hey! That's what our goal was. That's what we were trying to show. That means we did it!

Conclusion The conclusion is found by saying "Therefore, by the principle of mathematical induction" and restating the original claim. Therefore, by the principle of mathematical induction, 1 + 4 + 9 + ... + n2 = n (n + 1) (2n + 1) / 6 for all positive integers n.

Summations Earlier in the chapter we had some summation formulas that were very melodious. In the following examples, c is a constant, and x and y are functions of the index.

You can factor a constant out of a summation ∑cx = c∑x The sum of a constant times a function is the constant times the sum of a function.

The sum of a sum is the sum of the sums ∑(x+y) = ∑x + ∑y The summation symbol can distribute over addition.

The sum of a difference is the difference of the sums ∑(x-y) = ∑x - ∑y The summation symbol can distribute over subtraction.

Sum of the Powers of the Integers Now, we're going to look at the sum of the whole number powers of the natural numbers. Sigma Notation = Closed Form

Expanded 1 + 1 + 1 + ... + 1 (n times)

1 + 2 + 3 + ... + n

1 + 4 + 9 + ... + n2

1 + 8 + 27 + ... + n3

1 + 16 + 81 + ... + n4

1 + 32 + 243 + ... + n5

The closed form for a summation is a formula that allows you to find the sum simply by knowing the number of terms.

Finding Closed Form Find the sum of : 1 + 8 + 22 + 42 + ... + (3n2-n-2) The general term is an = 3n2-n-2, so what we're trying to find is ∑(3k2-k-2), where the ∑ is really the sum from k=1 to n, I'm just not writing those here to make it more accessible. Take the original, open form of the summation, ∑(3k2-k-2) Distribute the summation sign, ∑3k2 - ∑k - ∑2

Factor out any constants, 3∑k2 - ∑k - 2∑1 Replace each summation by the closed form given above. The closed form is a formula for a sum that doesn't include the summation sign, only n.

Now get a common denominator, in this case, 2.

Remember that the word factor begins with the letter F and anytime you have a choice of doing something in mathematics that starts with the letter F, that's probably where you should start. So, do not expand, factor instead. The common factor is n so we'll factor that out of each term. The whole expression is over 2. n [ (n+1)(2n+1) - (n+1) - 4 ] / 2 Now expand inside the brackets [ ]. n [ 2n2 + 3n + 1 - n - 1 - 4 ] / 2 Simplify like terms. n ( 2n2 + 2n - 4 ) / 2 Notice the common factor of 2 inside the parentheses, let's factor that out. 2 n ( n2 + n - 2 ) / 2 The 2 in the numerator and the 2 in the denominator divide out and we can factor the rest to get the closed form for the sum. n ( n + 2 ) ( n - 1) Isn't that beautiful? At this point, we could write a mathematical induction problem similar to those in the book for this problem. It would read ... Prove:

We're not going to prove that statement, but that is how the book came up with many of the problems that you're asked to prove. You take an open form, find the closed form, and then put it in the text as a problem for the student to prove.

Pattern Recognition Sometimes you have to figure out what the general term of a sequence is. Here are some guidelines.

1. Calculate the first several terms of the sequence. Sometimes it helps to write the term in factored and expanded form. 2. Try to find a recognizable pattern. Here are some things to look for 1. Linear patterns: an + b (will have a common difference) 2. Quadratic pattern: an2 + b (the perfect squares plus/minus a constant) 3. Cubic pattern: an3 + b (the perfect cubes plus/minus a constant) 4. Exponential patterns: 2n + b, 3n + b (powers of 2 or 3 plus/minus a

constant)

5. Factorial patterns: n!, (2n)!, (2n-1)! (factoring these really helps)

3. After you have your pattern, then you can use mathematical induction to prove the conjecture is correct.

Finite Differences Finite differences can help you find the pattern if you have a polynomial sequence. The first differences are found by subtracting consecutive terms. If the first differences are all the same, then the pattern is linear. The second differences are found by subtracting consecutive first differences. If the second differences are all the same, then the pattern is quadratic. Remember that you can find a quadratic model by taking the equation y=ax2+bx+c with three points. Then solve the system of equations that results. The analogy here is that you can find an=an2+bn+c by substituting in three terms in the sequence for an and their corresponding position in the sequence for n. Then solve the system of linear equations. This can be extended to third differences by subtracting consecutive second differences. If the third differences are all the same, the pattern is cubic. You can fit a cubic model with four points and the model an=an3+bn2+cn+d.

Finite Differences Example: Find the general term of the sequence 1, -2, -1, 4, 13, 26, 43, 64, 89, ... The first finite differences are found by subtracting consecutive terms in the original sequnce. That is, take -2-1=-3, -1-(-2)=1, 4-(-1)=5, 13-4=9, 26-13=13, etc. The first finite differences are: -3, 1, 5, 9, 13, 17, 21, 25, ... Since these aren't all the same, your sequence is not a linear (first degree) polynomial. Move on to the second finite differences. These are the differences in the consecutive terms of the first finite differences. 1-(-3)=4, 5-1=4, 9-5=4, 13-9=4, 17-13=4, etc. The second finite differences are 4, 4, 4, 4, 4, 4, 4, ... Since the second finite differences are all the same, your sequence is that of a second degree polynomial and you can write the general term as an = An2 + Bn + C. Plug in the values 1, 2, 3 (since there are three variables) into the expression. 1. When n=1, 1A + 1B + 1C = 1 (the first term is 1) 2. When n=2, 4A + 2B + 1C = -2 (the second term is -2)

3. When n=3, 9A + 3B + 1C = -1 (the third term is -1) Now, solve that system of linear equations (I recommend using matrix inverses AX=B, so X=A-1B). If you need a refresher on how to do that, visit the section on matrix inverses in chapter 6. In our case, we get A=2, B=-9, and C=8, so the general term of our sequence is an=2n29n+8. If you want to check it, pick any value for n and plug it into the general term. You should get the nth number in the sequence. For example, if n = 6, then a6 = 2(6)2 - 9(6) + 8 = 26. Check the sequence, sure enough, the 6th number is 26.

The Technique of Proof by Induction Suppose that having just learned the product rule for derivatives [i.e. (fg)' = f'g + fg'] you wanted to prove to someone that for every integer n >= 1, the derivative of is . How might you go about doing this? Maybe you would argue like this: "Well, see that when n=1, f(x) = x and you know that the formula works in this case. Now for n=2, Now for n=3, Now for n=4, Now for n=5, And you see we can keep on going this way - do you see the pattern? We just keep using the product rule in conjunction with the result from the previous line and we get the theorem for the next integer." Consider another example. Suppose that you wanted to show that for every integer n >= 1, . You might argue this way:

It's true for n=1, that's pretty clear. I can also check it directly for n =2, 3 ,4 and 5. Now that I know it's true for n=5, I can show you that it is true for n=6 like this: and so the formula works for n=6, too. Now I can continue this way and use this last result to show that the formula is true for n=7. Then, using the fact that it is true for 7, show that is also true for 8 etc. I could say something like, "so, see, I can continue just like this and prove the result for one integer after another." But that's not very satisfying. Now suppose I wanted to prove the following theorem. Theorem. Suppose that m is a fixed integer and . Then for every integer n >= 1, . We might recall that we have already shown this is true for n=2 and n=3. To show that it is true for n=4, we could say that since we know that and , then . Now that we know that the result is true for n = 4, we can show that it is true for n = 5 in exactly the same way. Since and , we have Now that we know the result is true for n = 5, we can show that it is true fro n =6 in exactly the same way. Since and , then . And now we might say that it is fairly evident that we can continue this process and so it is true that for every integer n >= 1. Mathematical Induction is way of formalizing this kind of proof so that you don't have to say "and so on" or "we keep on going this way" or some such statement. The idea

is to show that the result is true for n=1 and then show how once you've shown it to be true for some integer, you can see that it must be true for the next one as well.

The Principle of Mathematical Induction Suppose we have an assertion P(n) about the positive integers. Then if we show both of (i) and (ii) below, then P(n) is true for all n >= 1. (i). P(1) is true (ii). For each k >= 1: If P(k) is true, then P(k+1) is true. So to prove that

we could argue like this:

For n = 1, the result is clearly true since

.

Now suppose that for integer k >= 1,

. We

will be finished if we can show that we have,

. But

and so the result follows by induction. Similarly, Theorem. Suppose that m is a fixed integer and . Then for every integer n >= 1, . Proof. We will argue by induction. This result is trivial for n=1 it just says that if with that!

, then

. Hard to argue

Now assume that for some integer k >= 1, Since

.

and since multiplying corresponding sides of

congruences is still a congruence,

. But his last

expression reduces to . Hence the result follows by induction. Note: Induction arguments don't always start with the case n = 1. Sometimes we want to prove that an assertion is true for all integers n >= m for some other integer m. In that case we can use the slightly more general version of induction below.

The Principle of Mathematical Induction Suppose we have an assertion P(n) about the integers. Then if we show both of (i) and (ii) below, then P(n) is true for all n >= m. (i). P(m) is true (ii). For each k >= m, If P(k) is true, then P(k+1) is true. Examples I. The Fibonacci Numbers The Fibonacci numbers are defined by the recurrence relation, So the first few Fibonacci Numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,... There are numerous curious properties of the Fibonacci Numbers. Once guessed, most such properties can be verified by induction. Here are a few examples. 1. For every n >= 1,

.

2. For every n >= 1, 3. More generally, For every k >= 1, and n >= 1, if . 4. For every n >= 1 and m >= 1, 5. For every n >= 1, 6. For n >= 2,

. .

.

Another form of Mathematical Induction is the so-called Strong Induction described below. Principle of Strong Induction Suppose that P(n) is a statement about the positive integers and (i). P(1) is true, and (ii). For each k >= 1, if P(m) is true for all m < k, then P(k) is true. Then P(n) is true for all integers n >= 1. We will see examples of this form of induction later in the course. Also equivalent to the Principle of Induction is the WellOrdering Principle. The Well-Ordering Principle simply states that every non-empty subset of the positive integers has a smallest element. This simple observation can serve as the foundation of some very significant mathematical arguments. Definition. Let n and m be positive integers, and let A(n,m) = { an + bm >0 : a and b are integers }. (So, z belongs to A(n, m) if and only if z is an integer, z > 0, and there exists integers a and b such that z = an + bm.) Theorem. For any positive integers n and m, the smallest element of A(n, m) is gcd(m, n) - the greatest common divisor of n and m. Proof. By the Well-ordering Principle, A(n, m) does have a smallest element. Let d denote the smallest element of A(n, m). Then d = an + bm for some integers a and b. We will first show that d is a common divisor of m and n. By the divison algorithm, there exist integers q and r with 0 <= r < d and n = qd + r. But then, r = n - qd = n - q(an + bm) = (qa+1)n - (qb)m. So if r >0, then r must belong to A(n, m). However, this is impossible since r < d and d is the smallest element of A(n, m). So it must be that r = 0. Hence, n = qd and this means

that d divides n. Similarly, d divides m. So we have shown that d is a common divisor of n and m. On the other hand if t is any common divisor of m and n then say n = kt and m = st, then d = an + bm = akt + bst = (ak+bs)t. So d is a multiple of t. Hence d is at least as large as any other common divisor of m and n. Thus d is the largest of the common divisors of n and m. This completes the proof. Corollary. If n and m are relatively prime, then there exist integers a and b such that an + bm = 1. The following simple lemma is often useful. (Its proof is an exercise for you). Lemma. If n and m are relatively prime, then so are n and n + m, and so are n and n - m. Exercise: (Let fn denote the nth Fibonacci number.) 1. Show that for each n >= 1, fn and fn+1 are relatively prime. 2. Prove or Disprove: For each n >= 1, fn and fn+2 are relatively prime. 3. Prove or Disprove: For each n >= 1, fn and fn+3 are relatively prime.

Some Induction Exercises 1. Let Dn denote the number of ways to cover the squares of a 2xn board using plain dominos. Then it is easy to see that D1 = 1, D2= 2, and D3 = 3. Compute a few more values of Dn and guess an expression for the value of Dn and use induction to prove you are right. 2. The triangle inequality says that for any two real numbers x and y,

.

Show that for any n real numbers 3. How many ways are there to cover the squares of a 2xn chessboard with dominos?

Let D denote the number of such ways. For example, D =1, D =2, and D =3 as illustrated below. n

2

1

3

Work out the value of D and maybe D , and guess an expression for D . To verify your guess you will need to use the strong form of induction. That means that instead of just assuming that the result is true for some k, you assume that it is true for all values less than some k, and then show that it must be true for k. 4

5

n

4. (a). Prove: For n >= 1, (b). Does the series

.

converge or diverge?

5. Let an denote the number of subsets of {1, 2, 3, ... n} (including the empty set and the set itself.) (a). Show an = 2an-1. (This is pretty simple - you don't need induction here.) (b). Guess a formula for the value of an and use induction to prove you are right. 6. Prove that for any n>=1, 4 | 3 +1 (2n-1)

7. Prove by induction: For any n >= 1, 1 + 2 + 3 + ... + n = (1 + 2 + 3 + ... + n) . Example Induction Proofs 3

3

3

3

2

1. Prove that for every n >= 1, We argue by induction. For n=1, the expression has the value

. So the assertion is true for n=1.

Now assume that for some integer k,

. Then

there must exist an integer t such that . Now we must show that the assertion must be true for k+1, i.e. that .' However,

So we have , and the result follows by induction. 2. Prove by induction that the sum 1 + 3 + 5 + 7 + ... + 2n-1 is a perfect square. It is almost impossible to prove this assertion without proving much more. For convenience, let Sn = 1 + 3 + 5 + 7 + ... + 2n-1. Then Sn+1 = Sn + (2n+1). Now the result is easily seen to be true in the case k=1, since 1 is a perfect square. Now assume that Sk is a perfect square, say Sk = t for some t. Then we must show that Sk+1 is also a perfect square. Well, Sk+1 = Sk + (2k+1) = t + 2k +1. Now what?? Well, we seem to be stuck. The proof isn't going anywhere. But look what happens if we try to prove the stronger result that Sn= n . Our argument would be almost the same as before except that at the very end 2

2

2

we would have: Sk+1 = Sk + (2k+1) = k + 2k +1 = (k+1) . And now the induction proof works! This is the Inventor's Paradox - it is often easier to prove a stronger result than what you need. Here we prove not just that Sn is a perfect square, but that it is a particular perfect square, namely n . 3. Let f be the nth Fibonacci number, Prove by induction: For every n>=1, 2 | f ( i.e. f is even) 2

2

2

n

3n

3n

Proof. We argue by induction. For n=1 this says that f = 2 is even - which it is. 3

Now suppose that for some k, f is even. So f = 2m for some integer m. Now we must show that f is even. 3k

3k

3(k+1)

Then, f + m ).

3(k+1)

=f

3k+3

=f

3k+2

+f

3k+1

=f

3k+1

+f +f 3k

3k+1

= 2f

3k+1

+ f = 2(f 3k

3k+1

4. Prove by Induction: For all integers n >= 1, Proof: For n=1 this asserts that

- which is certainly

true. Now suppose that for some integer k >= 1, Thus, there is some integer m such that We claim that that

.

.

. But this is equivalent to showing

.

However, , and so is a multiple of 4 and the result follows by induction. 5. Prove by induction: For any n>=1, 7 | 8n - 1. We argue by induction. For n=1 this just says that 7 | 7 which is true. Now suppose that for some k>=1, 7 | 8k - 1. So that 8k - 1 =

7t for some integer t. We must show that 7 | 8k+1 - 1. But, 8k+1 - 1 = 8 ( 8k - 1 ) + 7 = 8(7t) + 7 = 7( 8t +1 ). And so we have 8k+1 - 1 is a multiple of 7 and so, 7 | 8k+1 - 1. A Fibonacci Series Problem Recall that the Fibonacci numbers are defined by the recurrence relation, fn = fn-1 + fn-2 n>2, f1=1, f2=1. So, f1=1, f2=1, f3=2, f4=3, f5=5, f6=8, f7=13, f8=21, f9=34, ... In this exercise we will determine some highly interesting properties of the Fibonacci numbers. A. Show by induction that

for all n>2.

B. Show by induction that . C. Show (by simple algebraic manipulation) that . D. Recall that every bounded, monotone sequence converges. Using this fact, prove: Lemma. If an is a bounded sequence in which (i). a3 > a5 > a7 > ... (ii). a2 < a4 < a6 < ... (iii). lim |an+1-an|=0 Then an converges. E. Show that satisfies the conditions of the lemma in (D). Consequently, we know that the sequence must converge to some limit t. Problem: Find the exact value of t. Note that by (A) your answer should be a number somewhere between 1 and 2.

F. Using the result of (E), determine if the power series converges or diverges.

More Induction Exercises 1. Show that n lines in general position divide the plane into

regions. 2. If every two cities in state A are joined by a one-way road,then it is possible to find a starting city A and a route from A that passes through every city exactly once. 3. 52n-1 + 1 is divisible by 6. 4. xn-yn is divisible by x-y. 5. n2 + n + 41 is prime for n=1,2...40, but it is not prime for all n >= 1. 6. For every integer n >= 1, any collection of n sets. A1, A2, ..., An.

holds for

7. For every integer n >= 1, is divisible by at least n distinct primes. 8. Show that if x is the root of 1- x - x2 so that x2= 1 - x, then for every integer n >= 1, x = f - xf . 2n

2n-1

2n

Example Induction Argument

1. Prove by induction: For all n >= 1, 9 -1 is divisible by n

8.

We will argue by induction . We first note that for n=1, this just says that 8 | 8 which is clearly true. Now, assume that the result holds for some integer k. So, 8 | 9 -1, and hence 9 -1 = 8t for some integer t. We claim that the result is true for the next larger integer, k+1. That is, we claim that 8 | 9 -1. Once we show this we will be finished. (1)

(2)

k

k

k+1

But, 9 -1 = 9( 9 -1 ) + 8 = 9( 8t ) + 8 = 8( 9t +1 ) and so 9 -1 is a multiple of 8, and so 8 | 9 -1. Thus our result follows by induction. ========================= 1. This is just to let everybody know what we are up to so they will know what to expect in the forthcoming argument. 2. Don't say, "assume that the result holds for all n," or anything equivalent to it. That's what you are trying to prove. The word some is significant here. 3. In the algebra at the end don't write: 8 | 9 - 1 = 9( 9 -1 ) + 8 The left-hand side of this expression is an assertion, "8 divides 9 - 1, " while the right-hand side is an algebraic expression. Similarly, don't write k+1

k

k+1

k+1

(3)

k+1

k

k+1

8 | 9 - 1 9( 9 -1 ) + 8 Either of the following is fine: 9 - 1 = 9( 9 -1 ) + 8 (Both sides are algebraic expressions.) OR k+1

k+1

k

k

8 | 9 - 1 8 | 9( 9 -1 ) + 8 (Both sides are equivalent assertions.) Induction Problems k+1

k

1. Prove that for every n >= 1, 2. An integer n is a perfect square if it is the square of some other integer. (For example 1, 4, 9, 16, 25 and 36 are all perfect squares.) Prove by induction that the sum 1 + 3 + 5 + 7 + ... + 2n-1 (i.e. the sum of the first n odd integers) is always a perfect square. 3. Show that any 2 x 2 board with one square deleted can be covered by Triominoes. n

n