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

A binary relation $R$ on $A$ is an equivalence relation exactly when it is reflexive, symmetric, and transitive:The equivalence class of $a\in A$ is $[a{]}_R=\{b\in A:aRb\}$. The equivalence classes partition $A$: every element belongs to its own class, and two classes are either equal or disjoint.

For positive integer pairs, reflexivity is $ab=ba$. If $ad=bc$, reversing the equality gives $cb=da$, establishing symmetry. For transitivity, suppose $(a,b)R(c,d)$ and $(c,d)R(e,f)$. Then $ad=bc$ and $cf=de$, whenceSince $d>0$, cancellation gives $af=be$. Thus $(a,b)R(e,f)$, and $R$ is an equivalence relation.

Membership in the equivalence class of $(4,6)$ means $4b=6a$, or $2b=3a$. Since $2$ and $3$ are coprime, $a=2r$ and $b=3r$ for a positive integer $r$. Conversely every such pair satisfies the equality. ThereforeThese pairs are precisely the positive numerator-denominator representations of the rational number $2/3$.

Use mathematical induction, starting at $n=1$. Since $F_0=0$ and $F_1=1$, the sum is $-1=(-1{)}^1{F}_0-1$.

Suppose the formula holds at $n\ge 1$. Adding the next Fibonacci number with its sign and using the Fibonacci recurrence givesThis is the required successor case. Thus

Fix $n\ge 1$ and use mathematical induction on $m$ with two initial cases, as appropriate for the second-order Fibonacci recurrence. At $m=0$, the right side is $F_{n-1}{F}_0+F_n{F}_1=F_n$. At $m=1$, it is $F_{n-1}+F_n=F_{n+1}$.

If the identity holds at $m$ and $m+1$, thenHence the induction establishes

Fix $m\ge 0$, using the convention for binomial coefficients that $\left(\genfrac{}{}{0ex}{}{k}{m}\right)=0$ when $m>k$. At $n=0$, both $\left(\genfrac{}{}{0ex}{}{0}{m}\right)$ and $\left(\genfrac{}{}{0ex}{}{1}{m+1}\right)$ equal $1$ if $m=0$ and $0$ otherwise.

For the successor step, apply the induction hypothesis, then Pascal's rule:Thus mathematical induction proves the hockey-stick identityThe zero convention also covers the case $n<m$, without a separate starting index.

The stated identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ has an even right side because $n$ is even. Its left side is an odd integer $k$ times the integer binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. An odd multiplier preserves integer parity, so that coefficient must be even. Equivalently, reducing the identity in modular arithmetic gives

Write $n=2r$ and $k=2s$. Partition an $n$-element set into $r$ distinguished pairs, and let $\tau$ interchange the two elements of every pair. It induces an involution on the $k$-element subsets. Every nonfixed subset is paired with its distinct image, so nonfixed subsets contribute an even number to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{2r}{2s}\right)$.

A fixed subset contains either both or neither of the elements of each distinguished pair. Since it contains $2s$ elements, it consists of exactly $s$ whole pairs. There are $\left(\genfrac{}{}{0ex}{}{r}{s}\right)$ such fixed subsets. Counting modulo $2$ therefore givesThe same involution explains part (i): a fixed subset cannot have odd size.