In the Pascal triangle, each number is the sum of the two numbers in the line above it and on each side of it. The first six lines of the triangle are shown below:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Using a zero-based counting system and denoting the number in the nth row and the kth column by (pascal-triangle n k) , (pascal-triangle 4 2) is 6, and (pascal-triangle 5 1) is 5. The algorithm that we use to build the triangle line by line says that (pascal-triangle n k) is the sum of (pascal-triangle (- n 1) (- k 1)) and (pascal-triangle (- n 1) k). We consider that each row of the triangle is continued with a zero at each end. Use this algorithm to define the procedure pascal-triangle. Analyze this algorithm to determine the number of additions performed when (pascal-triangle n k) is computed.

Your procedure should produce the following:

(pascal-triangle 10 5) ==> 252

(pascal-triangle 12 6) ==> 924

(pascal-triangle 14 7) ==> 3432

(pascal-triangle 16 8) ==> 12870