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

Use strong induction with three consecutive base cases:For $n\ge 11$, assume all values from $8$ through $n-1$ have the required representation. Since $8\le n-3<n$, write $n-3=3k+5m$ with $k,m$ nonnegative integers. Then $n=3(k+1)+5m$ is another such representation. Strong induction proves the claim for every $n\ge 8$. This is a consecutive-base induction for additive semigroups: the three base cases handle all residues before repeated addition of $3$.

At $n=2$, the product is $1-1/4=3/4$, as required. Suppose the formula holds at $n\ge 2$. Appending the next factor giveswhich is exactly the formula at $n+1$. Thus mathematical induction gives $(n+1)/(2n)$ for every $n\ge 2$. The factorization $1-i^{-2}=(i-1)(i+1)/i^2$ also explains the cancellation in this telescoping product.

Fix $m\ge 1$ and use two-base mathematical induction on $n$. At $n=0$, the proposed right side is $F_m$; at $n=1$, it is $F_{m-1}+F_m=F_{m+1}$. Suppose the identity holds at $n$ and $n+1$. The defining recurrence relation for the Fibonacci numbers givesThis is the assertion at $n+2$, completing the proof of the Fibonacci addition formula. The argument includes $m=1$, since $F_{m-1}=F_0$ is defined.

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of $g$ gives $f(a)=f(a^{\prime })$, and injectivity of $f$ then gives $a=a^{\prime }$. Thus the function composition is injective.

For any $c\in C$, surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Taking $b=f(a)\in B$ proves that $c$ has a preimage under $g$. Thus $g$ is surjective.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of the function composition forces $a=a^{\prime }$. Hence $f$ is injective.

Suppose $g(b)=g(b^{\prime })$. Since $f$ is surjective, choose $a,a^{\prime }\in A$ with $f(a)=b$ and $f(a^{\prime })=b^{\prime }$. Then $(g\circ f)(a)=(g\circ f)(a^{\prime })$, so injectivity gives $a=a^{\prime }$ and therefore $b=b^{\prime }$. Thus $g$ is injective. The use of surjectivity is what makes every point of $B$ accessible to this argument.

Fix $b\in B$. Since $g\circ f$ is surjective, there is $a\in A$ with $g(f(a))=g(b)$. Injectivity of $g$ gives $f(a)=b$, proving that $f$ is surjective. All five conclusions are instances of injectivity and surjectivity under composition.