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

Count pairs $(M,K)$ of subsets of an $n$-element candidate set with $K\subseteq M$, $|M|=m$, and $|K|=k$. Choosing the whole team $M$ first and then the special-role players $K$ gives $\left(\genfrac{}{}{0ex}{}{n}{m}\right)\left(\genfrac{}{}{0ex}{}{m}{k}\right)$. Alternatively choose $K$ first, then choose the other $m-k$ players from the $n-k$ candidates outside $K$, giving $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n-k}{m-k}\right)$. Each construction specifies the same pair uniquely. Thus double counting proves

Using the wiki convention that paths follow the written order of the binary relations, composition of relations isSome treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation $R$ below are the same under either convention.

A pair belongs to $R\circ R$ exactly when two successive $R$ steps connect its endpoints. The chain $a\to b\to c\to d$ has two such length-two paths, $a\to b\to c$ and $b\to c\to d$. HenceThis applies composition of relations directly; no other middle element gives a pair.

The relation powers are $R^2=\{(a,c),(b,d)\}$, $R^3=\{(a,d)\}$, and $R^i=\varnothing$ for $i\ge 4$. For $k=1$, $(a,b),(b,c)\in T$ but $(a,c)\notin T$, so transitivity fails. For $k=2$, $(a,c),(c,d)\in T$ but $(a,d)\notin T$, so it still fails.

For $k=3$, $T$ consists of every pair in which the first endpoint precedes the second in $a,b,c,d$. Composing any two such pairs again gives such a pair, so $T$ is transitive. Thus the smallest $k$ is $3$; this $T$ is the transitive closure of a relation $R$.

In the partially ordered set $(A,⪯)$, the assertion $m=\mathrm{lub}(S)$ means bothThe first condition makes $m$ an upper bound; the second makes it the least upper bound. Both conditions are necessary, and antisymmetry makes such an element unique.

Suppose $m$ is the greatest lower bound of the set $X$ of all upper bounds of $S$. Every $s\in S$ satisfies $s⪯x$ for every $x\in X$, so each such $s$ is a lower bound of $X$. Since $m$ is the greatest of those lower bounds, $s⪯m$ for every $s\in S$. Thus $m$ itself is an upper bound of $S$, meaning $m\in X$.

Also $m$, being a lower bound of $X$, satisfies $m⪯x$ for every $x\in X$. It is therefore an upper bound of $S$ below every other upper bound, which proves $m=\mathrm{lub}(S)$. The argument also covers empty $S$ or $X$ whenever the assumed greatest lower bound exists.

Put $H_n={\sum }_{k=0}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$; the other summands in the printed sum vanish. The initial values are $H_0=1=F_1$ and $H_1=1=F_2$. For $n\ge 2$, Pascal's identity givesFor the first sum, when $n$ is even its final term is zero; otherwise its range already agrees with $H_{n-1}$. In the second sum put $j=k-1$, obtaining $\left(\genfrac{}{}{0ex}{}{n-2-j}{j}\right)$ for $0\le j\le \lfloor (n-2)/2\rfloor$. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives $H_n=F_n+F_{n-1}=F_{n+1}$ from the two preceding cases and the Fibonacci recurrence. Hence