CS 2110 Midterm: CS 211 Cornell 2006 Fall t2 Examst2cs211sp03

• School: Cornell University
• Department: Computer Science
• Course: CS 2110
• Professor: All

Document Summary

There are 6 questions on 9 numbered pages. Check now that you have all the pages. Use the back of the pages for workspace. The exam is closed book and closed notes. Page 1 of 9: (15 points) prove by induction that for all n 0, n 1. In the induction step, state the induction hypothesis and indicate exactly where in your argument it is used. Make sure your argument is perfectly clear any ambiguity whatsoever will result in loss of points. Basis: for n = 0, the left-hand side is the empty sum, which by convention is 0, and the right-hand side evaluates to 0. X i=0 i(i + 1) = n3 n. We wish to prove under this assumption that n. X i=0 i(i + 1) = (n + 1)3 (n + 1) X i=0 i(i + 1) + n(n + 1) by taking out the last term n3 n.