University of Illinois at Urbana Champaign Fall

University of Illinois at Urbana-Champaign Fall 2006 Math 444 Group E13 1. Prove by induction that for all n ≥ 1 one has 1 12 + 1 22 + . . . + 1 n2 < 2 . Correction. First, following the hint, let us call P (n) the property 1 12 + 1 22 + . . . + 1 n2 ≤ 2? 1 n . Then P (1) is the assertion 1 ≤ 1, so P (1) is true. Now, assume that n ? N is such that P (n) is true. We wish to deduce from this that P (n+1) is also true. We have 1 12 + 1 22 + . . . + 1 (n + 1)2 = 1 12 + 1 22 + . . . + 1 n2 + 1 (n + 1)2 ≤ 2? 1 n + 1 (n + 1)2 (?) by the induction hypothesis. To obtain what we want, it is therefore enough to prove that? 1 n + 1 (n + 1)2 ≤ ? 1 n + 1 , which is equivalent to 1 (n + 1)2 ≤ 1 n ? 1 n + 1 .

• urbana-champaign fall


• since both maps


• k? ?


• induction hypothesis


• induction theorem enables