For question 3b, follow induction format. Big Oh notation O(n), Omega notation (n), Theta notation (n).

The following code computes an entry in Pascal's Triangle. Algorithm 2: Pascal's Triangle Function C(n,k) : Input: n a positive integer, k an integer between 0 and n Output: k!(nk)!n! If n=1 or k=0 or k=n : L Return 1 Return C(n1,k1)+C(n1,k) (a) (5 points) Use induction to prove that for any n1, C(n,k)=k!(nk)!n!forallk{0,1,,n} This will establish correctness of the algorithm. Note that 0!=1. Hint: in order to apply induction as described in class, let H(n) be the claim in (1). Solution: (b) (5 points) Find the time complexity of computing C(n,1). Do this by finding a formula for the total number of additions performed in computing C(n,1). Use induction to justify your answer. Solution: (c) (5 points) Find the time complexity of computing C(n,2). Do this by finding a formula for the total number of additions performed in computing C(n,2). Use induction to justify your answer. Solution