 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/2/e/i/solution

For

n \geq 2

and

1 \leq k \leq n - 1

(k n - 1) + (k - 1 n - 1) = \frac{( n - 1 )! ( n - k )}{k ! ( n - k )!} + \frac{( n - 1 )! k}{k ! ( n - k )!} = \frac{n !}{k ! ( n - k )!} = (k n) .

This proves Pascal's identity. The boundary cases

k = 0, n

follow for

n \geq 1

using the usual extension

(j m) = 0

for

j < 0

j > m

. The recurrence itself requires

n \geq 1

 New to topics? Read the docs here!