Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 2

List the $n$ elements of the finite set $A$. A subset is determined by $n$ membership decisions, each with two possibilities. This is a bijection from the power set to the set $\{0,1{\}}^n$, soThe empty set case is included: its power set contains the single empty subset.

There are $n(n-1)\cdots (n-k+1)=n!/(n-k)!$ ordered selections of $k$ distinct elements. Every size-$k$ subset appears in exactly $k!$ orders, giving the binomial coefficientFor $k=0$, both the empty selection and $0!$ contribute one.

Partition the power set into disjoint classes according to subset size. The class of size-$i$ subsets has cardinality $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, while the whole power set has cardinality $2^n$. Counting every subset once givesThis is also the binomial theorem evaluated at $1+1$, but the counting proof follows directly from the earlier parts.

Use mathematical induction with the defining Fibonacci recurrence. Both identities hold at $n=0$: their two sides are zero. If the first holds at $n$, thenIf the second holds at $n$, thenEach inductive hypothesis therefore advances to $n+1$.

For $n\ge 2$ and $1\le k\le n-1$, the factorial formula for a binomial coefficient givesThis proves Pascal's identity. The boundary cases $k=0,n$ follow for $n\ge 1$ using the usual extension $\left(\genfrac{}{}{0ex}{}{m}{j}\right)=0$ for $j<0$ or $j>m$. The recurrence itself requires $n\ge 1$.

For fixed $n\ge 0$, use mathematical induction on $k$. At $k=0$, both sides equal one. If the hockey-stick identity holds at $k$, then Pascal's identity givesThis is the required formula with $k$ replaced by $k+1$.