Recitation 3 Unfortunately, the small sums are not too illuminating. However, the larger sums suggest we consider an expression similar to n/3. So in the third column weve multiplied each sum by 3 in hopes of spotting a sequence generated by an expression something like n3 From the first few terms, you might guess that these new numbers are equal to n(n+1)(n+ 2). Alternatively, you might notice that the last couple numbers are equal to n+3n2+2n, which factors to n(n+1)(n+2). So now we have a conjecture Conjecture. For all positive integers, n 1·2+23+3:4+…+m(m+1)n(mn+1)(m+2) Let's use induction to verify this conjecture. Remember that an induction proof has five parts, though the last one is often omitted 1. Say that the proof is by induction 2. Define the induction hypothesis, a predicate P defined on the natural numbers 3. Handle the base case: prove that P(O)is true. 4. Handle the inductive step: prove that P(n)implies P(n+1) for all integers n20 5. Conclude that P(n) is true for all n E n by the principle of induction We noted in Lecture that while the base case is usually n=0, it could be any non negative integer, k, in which case the conclusion would simply be that P(n) holds for all n > k Proof. We use induction. Let P(n) be the proposition that 1·2+2·3+3:4+…+n(m+1) n(n+1)(n+2) Base case n=1: P(1)is true, because the lefthand side of (? )is 1- 2=2, and the righthand deis(1·2·3)/3=2 Inductive step: We must show that P(n)implies P(n+1) for all n 2 1. So assume that P(n) is true, where n denotes a positive integer. Then we can reason as follows 1·2+2.3+…+(n+1)(n+2) [1·2 n(n+1)]+(m+1)(n+2) n(n+1)(n+2) +(m+1)(m+2) by ind. hypothesis(??) n(n+1)(n+2)+3(mn+1)(n+2) 3 +1)m+2)(m+3) This shows that P(n+1)is true, and so P(n)implies P(n+1) for all n>1 By the induction principle, P(n) is true for all n 2 1, which proves the claimRecitation 3 2 Unfortunately, the small sums are not too illuminating. However, the larger sums suggest we consider an expression similar to n3/3. So in the third column we’ve multiplied each 3 sum by 3 in hopes of spotting a sequence generated by an expression something like n . From the first few terms, you might guess that these new numbers are equal to n(n+1)(n+ 2). Alternatively, you might notice that the last couple numbers are equal to n3 + 3n2 + 2n, which factors to n(n + 1)(n + 2). So now we have a conjecture: Conjecture. For all positive integers, n: n(n + 1)(n + 2) 1 2 + 2 3 + 3 4 + · · · . . . + n(n + 1) = 3 Let’s use induction to verify this conjecture. Remember that an induction proof has five parts, though the last one is often omitted: 1. Say that the proof is by induction. 2. Define the induction hypothesis, a predicate P defined on the natural numbers. 3. Handle the base case: prove that P(0) is true. 4. Handle the inductive step: prove that P(n) implies P(n + 1) for all integers n ≥ 0. 5. Conclude that P(n) is true for all n ∈ N by the principle of induction. We noted in Lecture that while the base case is usually n = 0, it could be any non￾negative integer, k, in which case the conclusion would simply be that P(n) holds for all n ≥ k. Proof. We use induction. Let P(n) be the proposition that: n(n + 1)(n + 2) 1 2 + 2 3 + 3 4 + · · · . . . + n(n + 1) = (1) 3 Base case n = 1: P(1) is true, because the lefthand side of (??) is 1 · 2 = 2, and the righthand side is (1 2 · · 3)/3 = 2. Inductive step: We must show that P(n) implies P(n+1) for all n ≥ 1. So assume that P(n) is true, where n denotes a positive integer. Then we can reason as follows: 1 2 + 2 3 + · · · · · + (n + 1)(n + 2) = [1 2 + 2 3 + + · · · · · n(n + 1)] + (n + 1)(n + 2) n(n + 1)(n + 2) = + (n + 1)(n + 2) by ind. hypothesis (??) 3 n(n + 1)(n + 2) + 3(n + 1)(n + 2) = 3 (n + 1)(n + 2)(n + 3) = 3 This shows that P(n + 1) is true, and so P(n) implies P(n + 1) for all n ≥ 1. By the induction principle, P(n) is true for all n ≥ 1, which proves the claim