FYI, here is a solution finding a formula for the total number of additions performed in computing C(n,2).

Problem 2. Pascal's Triangle 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) Find the time complexity of computing C(n,3) for large n. 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: (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: We hypothesize that the formula for the total number of additions is (j=1n1j)1. It is known that j=1n1j=2n(n1), so the total number of additions can be written as 2n(n1)1 which is O(n2). Inductive Hypothesis: Let H(n) be the statement: the total number of additions for C(n,2) is (j=1n1j)1. Base Case: Consider H(2). Calling C(2,2) returns 1 with no additions. Accordingly, (j=11j)1=0 Inductive Step: We will show that for n1,H(n)H(n+1). Calling C(n+1,2) returns C(n,1)+C(n,2) which gives 1 addition so far. We know from (b) that C(n,1) performs n1 additions. By the inductive hypothesis, C(n,2) performs (j=1n1j)1 additions. Putting these together gives: 1+n1+(j=1n1j)1=n+(j=1n1j)1=(j=1nj)1 Thus H(n+1) is true. Therefore, H(n) is true for all n1 by induction, which implies that for all n1, the total number of additions for C(n,2) is (j=1n1j)1