Calculus II Solutions for the Proof by Induction Exercises

Solutions for the Proof by Induction Exercises 1. n X i= i=1 n(n + 1) 2 Proof1 : • We first prove that the statement is true if n = 1. In this case, statement becomes: 1 = 1(2)/2, which is true. • We assume that the statement is true if n = k. That is, k X i=1 i= k(k + 1) . 2 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X (k + 1)(k + 2) . i= 2 i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i = i=1 k X i + (k + 1) k(k + 1) + (k + 1) 2 k(k + 1) + 2(k + 1) = 2 (k + 1)(k + 2) = 2 = 2. n X i2 = i=1 Break apart the sum i=1 By assumption QED n(n + 1)(2n + 1) 6 Proof: • We first prove that the statement is true if n = 1. In this case, statement becomes: 12 = 1(2)(3)/6, which is true. • We assume that the statement is true if n = k. That is, k X i2 = i=1 1 k(k + 1)(2k + 1) . 6 Q.E.D. is latin: quod erat demonstrandum, used to mean “which is what had to be proven” and signifies the end of a proof. Sometimes a box () is employed for the same purpose. 1 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X (k + 1)(k + 2)(2k + 3) . i2 = 6 i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i 2 = i=1 k X i2 + (k + 1)2 Break apart the sum i=1 k(k + 1)(2k + 1) + (k + 1)2 6 (k + 1)(k(2k + 1) + 6(k + 1)) = 6 (k + 1)(2k 2 + 7k + 6) = 2 (k + 1)(k + 2)(2k + 3) = 6 = 3. n X By assumption Factor out (k + 1) QED 2i−1 = 2n − 1 i=1 Proof: • We first prove that the statement is true if n = 1. In this case, statement becomes: 20 = 21 − 1 = 1, which is true. • We assume that the statement is true if n = k. That is, k X 2i−1 = 2k − 1. i=1 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X 2i−1 = 2k+1 − 1. i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i=1 i−1 2 = k X 2i−1 + 2k i=1 k = 2 − 1 + 2k 2 Break apart the sum By assumption = 2 · 2k − 1 = 2k+1 − 1 4. n X i3 = i=1 QED n2 (n + 1)2 4 Proof: • We first prove that the statement is true if n = 1. In this case, statement becomes: 13 = 12 (22 )/4, which is true. • We assume that the statement is true if n = k. That is, k X i=1 k 2 (k + 1)2 . i = 4 3 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X (k + 1)2 (k + 2)2 i3 = . 4 i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i3 = i=1 k X i3 + (k + 1)3 Break apart the sum i=1 2 k (k + 1)2 + (k + 1)3 = 4 (k + 1)2 (k 2 + 4k + 4) = 4 (k + 1)2 (k + 2)2 = 4 5. By assumption Factor out (k + 1)2 QED 1 1 1 n + + ··· + = 1·2 2·3 n(n + 1) n+1 Proof: • We first prove that the statement is true if n = 1. In this case, statement becomes: 1/2 = 1/2, which is true. • We assume that the statement is true if n = k. That is, k X i=1 1 k = . i(i + 1) k+1 3 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X k+1 1 = . i(i + 1) k + 2 i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i=1 k X 1 1 1 = + i(i + 1) i(i + 1) (k + 1)(k + 2) i=1 k 1 + k + 1 (k + 1)(k + 2) k(k + 2) + 1 = (k + 1)(k + 2) 2 k + 2k + 1 k+1 = = (k + 1)(k + 2) k+2 = 6. n X i=1 Break apart the sum By assumption QED 1 n = i(i + 1) n+1 SOLUTION: This is a duplicate question (same as 5). Sorry! 7. n X (2i − 1) = n2 i=1 Proof: • We first prove that the statement is true if n = 1. In this case, statement becomes: 2(1) − 1 = 12 , which is true. • We assume that the statement is true if n = k. That is, k X (2i − 1) = k 2 . i=1 • We show, using our assumption, that the statement must be true when n = k + 1. That is, k+1 X (2i − 1) = (k + 1)2 . i=1 We do that by starting with the LHS of the equation, then showing that we can get the RHS: k+1 X i=1 k X (2i − 1) = (2i − 1) + (2k + 1) i=1 4 Break apart the sum = k 2 + 2k + 1 = (k + 1)2 By assumption QED 8. n! > 2n for n ≥ 4. Proof: • We first prove that the statement is true if n = 4. In this case, statement becomes: 4! = 4(3)(2)(1) > (2 · 2)(2 · 2), which is true. • We assume that the statement is true if n = k. That is, k! > 2k . • We show, using our assumption, that the statement must be true when n = k + 1. That is, we need to show that (k + 1)! > 2k+1 . We do that by starting with the LHS of the equation, then showing that we can get the RHS: (k + 1)! = k!(k + 1) Break apart the sum k > 2 (k + 1) By assumption k k+1 ≥2 ·2=2 QED 9. 2n+1 > n2 for all positive integers. Proof: • This one is a bit trickier than the others. Although we only need to check it in the case that n = 1, let’s check it for a few values of n: n 2n+1 n2 1 22 = 4 12 = 1 2 23 = 8 22 = 4 3 24 = 16 32 = 9 So we see that not only is 2n+1 larger than n2 , the difference between them is growing. Now let’s try the proof. • We assume that the statement is true if n = k. That is, 2k+1 > k 2 . • We show, using our assumption, that the statement must be true when n = k + 1. That is, we need to show that 2k+2 > (k + 1)2 . 2k+2 = 2k+1 · 2 > 2k 2 5 By assumption We would be finished if we can assert that 2k 2 > (k+1)2 , or that 2k 2 > k 2 +2k+1, or equivalently, k 2 − 2k − 1 > 0 The critical value here is where we have equality: k 2 − 2k − 1 = 0 ⇒ k =1± √ 2 √ For k > 1 + 2 ≈ 2.14, our statement is true. In particular, it is true when k = 3, 4, 5, · · ·. What about the smaller values of k? We have shown that the statement is true for those cases by actual computation. Therefore, the statement is true for all n > 0. 6