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

Mathematical induction has two obligations. Establish the base case $S(0)$ if the natural numbers start at zero, or $S(1)$ if they start at one. Then prove the induction step: for an arbitrary natural $k$ in the relevant range, assume $S(k)$ and deduce $S(k+1)$.

The base case starts the chain, and the step propagates truth to every subsequent natural number:

The base case is $F_5=5$, so $5\mid F_5$. To relate successive blocks of five, use the Fibonacci addition formula:This identity can also be obtained simply by applying the Fibonacci recurrence five times. If the mathematical induction hypothesis is $5\mid F_{5n}$, thenis a sum of two multiples of five. HenceThe generalisation is Fibonacci multiple-index divisibility:Indeed, $F_{mn+m}=F_m{F}_{mn+1}+F_{m-1}{F}_{mn}$, so precisely the same mathematical induction works with $5$ replaced by $m$.

For finite sets, the inclusion-exclusion principle statesAn element present in $r$ of the sets is counted ${\sum }_{k=1}^r(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{r}{k})=1$ times, which explains the alternating corrections.

There are $\lfloor 999/d\rfloor$ positive integers strictly below $1000$ divisible by $d$. For the divisors $2,5,7$, the single counts are $499,199,142$. Their pairwise intersections correspond to divisibility by $10,14,35$, giving $99,71,28$. The triple intersection has $\lfloor 999/70\rfloor =14$ elements. Therefore

A binary relation $R$ on $A$ is a subset of $A\times A$. Its properties are quantified over elements of $A$:

Thus an equivalence relation is a binary relation that is simultaneously reflexive, symmetric and transitive. The equivalence class of $a$ is the set of all elements related to it:Antisymmetry permits diagonal pairs and does not mean that a binary relation fails to be a symmetric relation.

The binary relation $\le$ is reflexive and transitive but is not a symmetric relation. For example, $1\le 2$ while $2\nleqq 1$. ThereforeThere are consequently no equivalence classes for this binary relation in the requested sense.

This is equality of remainders in modular arithmetic. It is reflexive because $3\mid (n-n)=0$, symmetric because $3\mid (n-m)$ implies $3\mid (m-n)$, and transitive because $3\mid (n-m)$ and $3\mid (k-n)$ imply $3\mid (k-m)$ by addition. ThusIts three equivalence classes areIf zero is included in $\mathbb{N}$, it belongs to $C_0$; otherwise that class starts at three.

In a symmetric relation, each of the $n$ diagonal pairs $(a,a)$ can be chosen independently. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs of distinct elements, either both ordered pairs $(a,b),(b,a)$ occur or neither occurs. Every such choice is free and produces a distinct symmetric relation. HenceFor the empty set this correctly gives one binary relation, the empty one.