Let f : N R20. We define the cumulative surn of f, denoted Sumf, to be the function Sumf : N R20 defined as follows: For example, we have previously proved in this course that if f(n) n, then Sumy(n) = In Parts (a) and (c), you may not use any theorems that may have been shown in lecture/tutorial, and must use the formal definition of big-Oh (a) [4 rnarks] Prove that for all f : N R20, iff e 0(n), then Sumy e O(n2) Hint: be careful about choosing constants here! It may be tempting to say that "f(n) Skn, but this is only true after a certain point. Also remember that you can break up summations: f(i) = f(i) + f(i) for all a b c i=e+ 1 2" rn (b) [3 marks] Prove by induction that for all natural numbers n, 1=1 (c) [4 marks] Using part (b), disprove the following claim: for all f, g : N R20, if f(n) E(g(n)), then Sumf(n) E O(ng(n))