3. It is Fal in Boulder, which means everything must have Pumpkin Spice in it. You tie your Pumpkin Spice Shoelaces before going to the Pumpkin Spice Gym and getting a Pumpkin Spice Workout in... you know, typical Boulder stuff. You are having a party this weekend and want to serve pie - Pumpkin Pie, obvi and you want to cut your circular pie into as many pieces as possible using only straight cuts. Let Pu be the maximum number of pieces of pie after n straight cuts For example, with 0 straight cuts, you can have exactly po 1 piece (the entire pie), and with 1 cut you can have pi 2 pieces of delicious pumpkin pie. (a) Devise a recurrence relation for the maximum number of pieces of pie after n straight cuts, that depends on the maximum number of pieces of pie after n -1 straight cuts. Include the initial conditions, and verify that your recurrence relation works for the first four cases (b) Conjecture a closed- form solution for p (c) Prove that your closed-form solution from part (b) is correct for1 using Induction. Be sure to clearly state your induction hypothesis, and state whether you're using weak induction or strong induction