 Home

Codex Wiki

List of universities

University of Cambridge

Course of the University of Cambridge

Mathematics course of the University of Cambridge

Past exam of the mathematics course of the University of Cambridge

2007

Paper 4

Define the <binomial coefficient> $\binom nk$ as the number of $k$-element subsets of an $n$-element set. Equivalently it is $n!/[k!(n-k)!]$: there are $n(n-1)\cdots(n-k+1)$ ordered lists of $k$ distinct elements, and each subset gives $k!$ such lists. The empty subset gives $\binom n0=1$.

Distinguish one element of the set. A $k$-element subset either omits it, giving $\binom{n-1}k$ possibilities, or contains it and chooses its other $k-1$ elements from the remaining set, giving $\binom{n-1}{k-1}$ possibilities. These cases are disjoint and exhaustive, proving <Pascal's identity>:
$$
\boxed{\binom{n-1}k+\binom{n-1}{k-1}=\binom nk.}
$$
For the requested sum, fix $n\ge0$ and use <mathematical induction> on $k$. At $k=0$, both sides equal one. If the assertion holds at $k$, adding the next summand gives
$$
\sum_{j=0}^{k+1}\binom{n+j}j
=\binom{n+k+1}k+\binom{n+k+1}{k+1}
=\binom{n+k+2}{k+1},
$$
where the last equality is <Pascal's identity>. Thus the induction proves the <hockey-stick identity> for all nonnegative $n,k$:
$$
\boxed{\sum_{j=0}^k\binom{n+j}j=\binom{n+k+1}k.}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 2E / Solution

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 2E / Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 2E / Solution

 Ancestors (10)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion