 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability-resit/2/d/solution

Fix

m \geq 0

, using the convention for binomial coefficients that

(m k) = 0

when

m > k

. At

n = 0

, both

(m 0)

and

(m + 1 1)

equal

1

m = 0

and

0

otherwise.

For the successor step, apply the induction hypothesis, then Pascal's rule:

\sum_{k = 0}^{n + 1} (m k) = (m + 1 n + 1) + (m n + 1) = (m + 1 n + 2) .

k = 0 \sum n (m k) = (m + 1 n + 1) (m, n \geq 0) .

The zero convention also covers the case

n < m

, without a separate starting index.

 New to topics? Read the docs here!