Sample Induction Proofs - University of Illinois Urbana ...

1 Math 213 Worksheet: Induction Proofs III, Sample Proofs Hildebrand Sample Induction Proofs Below are model solutions to some of the practice problems on the Induction worksheets. The solutions given illustrate all of the main types of Induction situations that you may encounter and that you should be able to handle. Use these solutions as models for your writing up your own solutions in exams and homework. For additional examples, see the following examples and exercises in the Rosen text: Section , Examples 1 10, Exercises 3, 5, 7, 13, 15, 19, 21, 23, 25, 45. Section , Example 6, Exercises 13, 15. Pn i 2. 1. Prove by Induction that, for all n Z+ , i=1 ( 1) i = ( 1)n n(n + 1)/2.

2 proof : We will prove by Induction that, for all n Z+ , n X ( 1)n n(n + 1). (1) ( 1)i i2 = . i=1. 2. Base case: When n = 1, the left side of (1) is ( 1)12 = 1, and the right side is ( 1)1(1+1)/2 =. 1, so both sides are equal and (1) is true for n = 1. Induction step: Let k Z+ be given and suppose (1) is true for n = k. Then k+1. X k X. i 2. ( 1) i = ( 1)i i2 + ( 1)k+1 (k + 1)2. i=1 i=1. ( 1)k k(k + 1). = + ( 1)k+1 (k + 1)2 (by Induction hypothesis). 2. ( 1)k (k + 1). = (k 2(k + 1)). 2. ( 1)k (k + 1). = ( k 2). 2. k+1. ( 1) (k + 2). = . 2. Thus, (1) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , (1) is true for all n Z+.

3 Pn 1. 2. Find and prove by Induction a formula for i=1 i(i+1) , where n Z+ . proof : We will prove by Induction that, for all n Z+ , n X 1 n (1) = . i=1. i(i + 1) n+1. Base case: When n = 1, the left side of (1) is 1/(1 2) = 1/2, and the right side is 1/2, so both sides are equal and (1) is true for n = 1. 1. Math 213 Worksheet: Induction Proofs III, Sample Proofs Hildebrand Induction step: Let k Z+ be given and suppose (1) is true for n = k. Then k+1 k X 1 X 1 1. = +. i=1. i(i + 1) i=1. i(i + 1) (k + 1)(k + 2). k 1. = + (by Induction hypothesis). k + 1 (k + 1)(k + 2). k(k + 2) + 1. = (by algebra). (k + 1)(k + 2). (k + 1)2. = (by algebra). (k + 1)(k + 2). k+1.

4 = . k+2. Thus, (1) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , (1) is true for all n Z+ . Pn 3. Find and prove by Induction a formula for i=1 (2i 1) ( , the sum of the first n odd numbers), where n Z+ . proof : We will prove by Induction that, for all n Z+ , n X. (1) (2i 1) = n2 . i=1. Base case: When n = 1, the left side of (1) is 1, and the right side is 12 = 1, so both sides are equal and (1) is true for n = 1. Induction step: Let k Z+ be given and suppose (1) is true for n = k. Then k+1. X k X. (2i 1) = (2i 1) + (2(k + 1) 1). i=1 i=1. 2. = k + 2(k + 1) 1 (by Induction hypothesis). = k + 2k + 1 = (k + 1)2.

5 2. Thus, (1) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , (1) is true for all n 2. Qn 4. Find and prove by Induction a formula for i=2 (1 i12 ), where n Z+ and n 2. proof : We will prove by Induction that, for all integers n 2, n . Y 1 n+1. (1) 1 2 = . i=2. i 2n Base case: When n = 2, the left side of (1) is 1 1/22 = 3/4, and the right side is (2+1)/4 = 3/4, so both sides are equal and (1) is true for n = 2. 2. Math 213 Worksheet: Induction Proofs III, Sample Proofs Hildebrand Induction step: Let k 2 be given and suppose (1) is true for n = k. Then k+1. Y k . 1 Y 1 1. 1 2 = 1 2 1 . i=2. i i=2.

6 I (k + 1)2.. k+1 1. = 1 (by Induction hypothesis). 2k (k + 1)2. k + 1 (k + 1)2 1. = . 2k (k + 1)2. 2. k + 2k k+2. = = . 2k(k + 1) 2(k + 1). Thus, (1) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , (1) is true for all n Z+ with n 2. 5. Prove that n! > 2n for n 4. proof : We will prove by Induction that ( ) n! > 2n holds for all n 4. Base case: Our base case here is the first n-value for which ( ) is claimed, , n = 4. For n = 4, the left and right sides of ( ) are 24 and 16, respectively, so ( ) is true in this case. Induction step: Let k 4 be given and suppose ( ) is true for n = k. Then (k + 1)!

7 = k!(k + 1). > 2k (k + 1) (by Induction hypothesis). k 2 2 (since k 4 and so k + 1 2)). k+1. =2 . Thus, ( ) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , it follows that ( ) is true for all n 4. 6. Prove that for any real number x > 1 and any positive integer x, (1 + x)n 1 + nx. proof : Let x be a real number in the range given, namely x > 1. We will prove by Induction that for any positive integer n, ( ) (1 + x)n 1 + nx. holds for any n Z+ . Base case: For n = 1, the left and right sides of ( ) are both 1 + x, so ( ) holds. Induction step: Let k Z+ be given and suppose ( ) is true for n = k.

8 We have (1 + x)k+1 = (1 + x)k (1 + x). (1 + kx)(1 + x) (by ind. hyp. and since x > 1 and thus (1 + x) > 0). = 1 + (k + 1)x + kx2 (by algebra). 1 + (k + 1)x (since kx2 0). Hence ( ) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , it follows that ( ) holds for all n Z+ . 3. Math 213 Worksheet: Induction Proofs III, Sample Proofs Hildebrand Pn 7. Prove that i=1 fi2 = fn fn+1 for all n Z+ . proof : We seek to show that, for all n Z+ , n X. ( ) fi2 = fn fn+1 . i=1. Base case: When n = 1, the left side of ( ) is f12 = 1, and the right side is f1 f2 = 1 1 = 1, so both sides are equal and ( ) is true for n = 1.

9 Induction step: Let k Z+ be given and suppose ( ) is true for n = k. Then k+1. X k X. fi2 = fi2 + fk+1. 2. i=1 i=1. 2. = fk fk+1 + fk+1 (by ind. hyp. ( ) with n = k). = fk+1 (fk + fk+1 ) (by algebra). = fk+1 fk+2 (by recurrence for fn ). Thus, ( ) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of Induction , it follows that ( ) is true for all n Z+ . 8. Prove that fn (3/2)n 2 for all n Z+ . proof : We will show that for all n Z+ , ( ) fn (3/2)n 2. Base cases: When n = 1, the left side of ( ) is f1 = 1, and the right side is (3/2) 1 = 2/3, so ( ) holds for n = 1. When n = 2, the left side of ( ) is f2 = 1, and the right side is (3/2)0 = 1, so both sides are equal and ( ) is true for n = 2.

10 Thus, ( ) holds for n = 1 and n = 2. Induction step: Let k 2 be given and suppose ( ) is true for all n = 1, 2, .. , k. Then fk+1 = fk + fk 1 (by recurrence for fn ). k 2. (3/2) + (3/2)k 3. (by Induction hypothesis with n = k and n = k 1). = (3/2)k 1 (3/2) 1 + (3/2) 2.. (by algebra).. 2 4. = (3/2)k 1 +. 3 9. 10. = (3/2)k 1 > (3/2)k 1 . 9. Thus, ( ) holds for n = k + 1, and the proof of the Induction step is complete. Conclusion: By the principle of strong Induction , it follows that ( ) is true for all n Z+ . Remarks: Number of base cases: Since the Induction step involves the cases n = k and n = k 1, we can carry out this step only for values k 2 (for k = 1, k 1 would be 0 and out of range).