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

For the base case $n=2$, the product is $1-1/4=3/4=(2+1)/(2\cdot 2)$. Assume the identity holds for some $n\ge 2$. Multiplying by the next factor givesThis is the desired expression with $n$ replaced by $n+1$, so mathematical induction proves the identity for every $n\ge 2$. The factorization $1-i^{-2}=(i-1)(i+1)/i^2$ also explains the cancellation as a telescoping product.

For $n=1$, both sides are $1/3$. Assuming the formula through $n$, adding the next term givesThe last expression is the required formula at $n+1$, completing mathematical induction. The partial fraction decompositionprovides a second explanation: this is a telescoping sum.

Suppose, for a proof by contradiction, that an integer $n$ is both an even number and an odd number. Then $n=2u$ and $n=2v+1$ for some integers $u,v$. Subtracting yields $u-v=1/2$. The left side is an integer, while $1/2$ is not. This contradiction proves that no integer is both even and odd.

The contrapositive is that an integer perfect square has residue $0$ or $1$ modulo $4$. Let $n=t^2$ for an integer $t$. If $t=2u$ is an even number, then $t^2=4u^2\equiv 0(\mathrm{mod}4)$. If $t=2u+1$ is an odd number, then $t^2=4u(u+1)+1\equiv 1(\mathrm{mod}4)$. These exhaust the possible parities of an integer. Thus a residue of $2$ or $3$ excludes being a perfect square, as required by the contrapositive.

Take $u=(1,1)$ and $v=(1,2)$. Their first coordinates are equal, so both $uRv$ and $vRu$ hold, although $u\ne v$. Thus $R$ is not an antisymmetric relation, and hence it is not a partial order. The failure arises because its comparisons ignore the second coordinate entirely.

Check each partial order axiom. For every $(a,b)$, $a\le a$ and $b\ge b$, so $S$ is a reflexive relation. If both $(a,b)S(c,d)$ and $(c,d)S(a,b)$, the first coordinates satisfy $a\le c\le a$ and the second coordinates satisfy $b\ge d\ge b$. Therefore $a=c$ and $b=d$, which proves $S$ is an antisymmetric relation.

Finally, if $(a,b)S(c,d)$ and $(c,d)S(e,f)$, then $a\le c\le e$ and $b\ge d\ge f$. Hence $(a,b)S(e,f)$, making $S$ a transitive relation. All three axioms hold, so $S$ is a partial order. It is a product order, with the usual order on the first coordinate and the reversed order on the second.