6.042/18.] Mathematics for Computer Science February 9, 2005 Srini devadas and Eric Lehman Notes for Recitation 3 1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If ·P(0) is true,an for all nE N, P(n) implies P(n+1), then P(n) is true for all nE N As an example let's try to find a simple expression equal to the following sum and then use induction to prove our guess correct 1·2+2·3+3:4+…+n·(mn+1) To help find an equivalent expression, we could try evaluating the sum for some small n and(with the help of a computer) some larger n sum 3×sum 1 2 6 2 24 3 60 4 120 210 100343400≈10°/31030200 100339010006.042/18.062J Mathematics for Computer Science February 9, 2005 Srini Devadas and Eric Lehman Notes for Recitation 3 1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If • P(0) is true, and • for all n ∈ N, P(n) implies P(n + 1), then P(n) is true for all n ∈ N. As an example, let’s try to find a simple expression equal to the following sum and then use induction to prove our guess correct. 1 2 + 2 3 + 3 4 + · · · . . . + n · (n + 1) To help find an equivalent expression, we could try evaluating the sum for some small n and (with the help of a computer) some larger n: n 0 sum 0 3 × sum 0 1 2 6 2 8 24 3 20 60 4 40 120 5 70 210 . . . . . . . . . 10 440 1320 100 1000 343400 ≈ 106/3 334334000 ≈ 109/3 1030200 1003002000