1. Pizza! (22 points). Suppose we have an infinitely large pizza (every computer scientist's dream), and we wish to determine what is the maximum number of pizza pieces that we can produce, using only n perfectly straight and infinitely long) cuts. The figure below illustrates the most pieces we can make, for n = 1, 2, 3 and 4 cuts. Pay careful attention to how many/which pieces are divided (and thus added) by the newest cut. 112 pieces 7 peces 11 pcoes Let S(n) denote the number of slices, given n cuts across the pie. From the illustration above, we see that S(1) = 2, and S(2) = 4, and we can also infer from the description that S(O) = 1. (a) (1 marks] What is the value of S(5)? (b) [3 marks] Complete the following recurrence relation for S(n): S(O)=1 S(n) = O D for n > 0 (c) [6 marks] What is S(n) as a function of n? Your solution should not be a recurrence, contain a summation, or use asymptotic notation