Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability (4223)

Solutions to all nine questions of the examination dated 26 June 2014.^[ref]

By De Morgan's laws, taking a set difference from a union requires exclusion from both sets, while taking a set difference from an intersection requires exclusion from at least one:For example, $x$ belongs to the first left-hand side precisely when $x\in A$, $x\notin B$ and $x\notin C$; these are exactly the membership conditions on the first right-hand side. For the second identity, replace the two exclusions by their logical disjunction.

Prove both identities by mathematical induction. The base case $n=2$ is the two-set form of De Morgan's laws. For the union identity, suppose the result holds for $n$. Applying the two-set identity and then the inductive hypothesis givesFor the intersection identity, the corresponding step isThese close the two inductions.

Apply the two identities already proved with $A=\mathcal{U}$. Every $B_i$ is a subset of the common universe, and a complement is the set difference from that universe. ThereforeReplacing each set difference from $\mathcal{U}$ by its complement notation gives the claimed finite forms of De Morgan's laws.

Function composition is not always commutative. The reversed function composition may be undefined when the necessary domain of a function and codomain do not match. A counterexample using functions $\mathbb{R}\to \mathbb{R}$ avoids that issue: let $f(x)=x+1$ and $g(x)=2x$. ThenBoth function compositions exist, and their values differ at every real $x$.

For every $x\in \mathbb{R}$, the definition of function composition givesThe functions agree at every argument, so function extensionality proves the associative property of function composition.

The real cube root in the denominator vanishes at $x=-1$, so the printed rule needs the domain of a function $D_1=\mathbb{R}\setminus \{-1\}$. On its actual domain of a function, the second iterated function simplifies toThis suggestsFor the induction step, assume the formula at $n$ and restrict to arguments for which its value is not $-1$. Its cube is $x^3/(1+n{x}^3)$, so another application givesReal cube roots are multiplicative, including for negative arguments. The newly excluded point satisfies $x^3/(1+n{x}^3)=-1$, hence $x^3=-1/(n+1)$; all earlier exclusions remain. This proves both the formula and the domain of a function by mathematical induction. The inherited exclusions are essential for an iteration of a partial function: cancellation in the final expression cannot repair an undefined intermediate application.

Set $y=f(x)$ and cube the equation. Solving for $x^3$ givesConsequently the inverse function isThe value $y=1$ is impossible in the original equation. Conversely, every real $y\ne 1$ gives exactly one real $x$ by the displayed cube root, and this $x$ cannot equal $-1$. Direct substitution verifies both inverse identities. Thus the corrected bijection is $f:\mathbb{R}\setminus \{-1\}\to \mathbb{R}\setminus \{1\}$.

List the $n$ elements of the finite set $A$. A subset is determined by $n$ membership decisions, each with two possibilities. This is a bijection from the power set to the set $\{0,1{\}}^n$, soThe empty set case is included: its power set contains the single empty subset.

There are $n(n-1)\cdots (n-k+1)=n!/(n-k)!$ ordered selections of $k$ distinct elements. Every size-$k$ subset appears in exactly $k!$ orders, giving the binomial coefficientFor $k=0$, both the empty selection and $0!$ contribute one.

Partition the power set into disjoint classes according to subset size. The class of size-$i$ subsets has cardinality $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, while the whole power set has cardinality $2^n$. Counting every subset once givesThis is also the binomial theorem evaluated at $1+1$, but the counting proof follows directly from the earlier parts.

Use mathematical induction with the defining Fibonacci recurrence. Both identities hold at $n=0$: their two sides are zero. If the first holds at $n$, thenIf the second holds at $n$, thenEach inductive hypothesis therefore advances to $n+1$.

For $n\ge 2$ and $1\le k\le n-1$, the factorial formula for a binomial coefficient givesThis proves Pascal's identity. The boundary cases $k=0,n$ follow for $n\ge 1$ using the usual extension $\left(\genfrac{}{}{0ex}{}{m}{j}\right)=0$ for $j<0$ or $j>m$. The recurrence itself requires $n\ge 1$.

For fixed $n\ge 0$, use mathematical induction on $k$. At $k=0$, both sides equal one. If the hockey-stick identity holds at $k$, then Pascal's identity givesThis is the required formula with $k$ replaced by $k+1$.

The relation is reflexive because $a-a=2\cdot 0$. It is symmetric because $a-b=2k$ implies $b-a=2(-k)$. It is transitive because $a-b=2k$ and $b-c=2\ell$ imply $a-c=2(k+\ell )$. It is therefore an equivalence relation, namely congruence modulo an integer for modulus two. Its two equivalence classes consist of the even integers and the odd integers.

The notation means that $n$ divides $a_1-a_2$:This is congruence modulo an integer; equivalently, the two integers have the same remainder on division by the positive integer $n$.

Write $a_1-a_2=kn$ with $k\in \mathbb{Z}$. The difference of two squares factors asThe final factor is an integer, so $n$ divides the difference. By congruence modulo an integer, $\boxed{a_1^2\equiv a_2^2(\mathrm{mod}n)}$.

Dividing by $n^2$ gives $10^5/n+2\to 2$. Thus the quadratic term controls the growth:The sharper Big theta notation also supplies the requested Big O notation bound.

For $n>0$,Consequently $\boxed{\sqrt{n^6+n^2}=\Theta (n^3),\text{in particular }O(n^3)}$ in Big theta notation and Big O notation.

Here $a,b\ge 2$ are fixed integers. The term $a{b}^n$ has exponential growth, whereas $a{n}^b$ has fixed-degree polynomial growth and $n{b}^a$ is linear. Since a fixed-base exponential eventually dominates every fixed-degree polynomial,Hence the requested Big O notation bound, with its matching lower order, is $\boxed{\Theta (b^n),\text{in particular }O(b^n)}$.

For sufficiently large positive $n$, the logarithm identities giveAfter division by $n{\log }_{2}n$, the right-hand side tends to one. Thus $\boxed{\Theta (n\log n),\text{in particular }O(n\log n)}$ gives the asymptotic order in Big theta notation and Big O notation.

The number $K$ is fixed. By Big O notation, for each $i$ there are constants $C_i>0$ and $N_i$ such that $f_i(n)\le C_{i}g(n)$ when $n\ge N_i$. Take $N={\max }_i{N}_i$. For $n\ge N$, positivity givesThe constants in parentheses are independent of $n$, proving $\boxed{h=O(g),l=O(g^2)}$. If $K=1$, the second sum is empty and $l=0$, which satisfies the same upper bound.

The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case $T(1)=t>0$ and use $m=\lceil n/4\rceil$, $n-m$ for $n\ge 2$. This integer rounding in a divide-and-conquer recurrence gives $1/4\le m/n\le 1/2$. The unrounded calculation is the special split fraction $1/4$.

Prove $T(n)\le An{\log }_{2}n+Bn$ by strong induction. Put $h_0=H_2(1/4)>0$, choose $A\ge 1/h_0$, and choose $B\ge t$. The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses $H_2(m/n)\ge h_0$. This closes the inductive hypothesis and proves $\boxed{T(n)=O(n\log n)}$ in Big O notation.

Use the same integer rounding in a divide-and-conquer recurrence, now with root cost $n^2$. Since $1/4\le m/n\le 1/2$,Choose $C\ge \max \{T(1),8/3\}$ and use strong induction with inductive hypothesis $T(j)\le C{j}^2$. Both child sizes are positive and less than $n$, soThe same factor $5/8$ occurs for the exact fractional split. Therefore $\boxed{T(n)=O(n^2)}$ in Big O notation.

Let $I=\int e^x\sin xdx$. Two applications of integration by parts givewhere additive constants can be absorbed at the end. Solving for $I$ yieldsDifferentiating the answer gives $e^x\sin x$.

After division by $x>0$, the equation is linear with coefficient $-1/x$ on $y$. Its integrating factor is $1/x$, and the product rule givesUsing the antiderivative from the preceding part,The arbitrary constant multiplies the homogeneous solution $x$.

The homogeneous characteristic equation is $r^2-4r+3=(r-1)(r-3)=0$, giving $e^x$ and $e^{3x}$. Since the forcing $e^{3x}$ already appears among these solutions, try a particular solution $y_p=Ax{e}^{3x}$. Differentiation and substitution giveso $A=1/2$. The general solution is

Write $Y(t)=y(e^t)$, so $t=\log x$. The chain rule givesSubstitution into the Cauchy-Euler equation therefore gives $Y^{\prime \prime }+Y^{\prime }-2Y=0$. Its characteristic equation factors as $(r-1)(r+2)=0$, so $Y=C_1{e}^t+C_2{e}^{-2t}$. Returning to $x$ gives

The arithmetic-geometric mean inequality for the positive numbers $x$ and $a/x$ givesEquality holds precisely when $x=a/x$, hence at $x=\sqrt{a}$. Thus $\boxed{\underset{x>0}{\min }g(x)=\sqrt{a}}$, attained only at $\boxed{x=\sqrt{a}}$. Equivalently, the exact identity $g(x)-\sqrt{a}=(x-\sqrt{a}{)}^2/(2x)$ proves the same global bound.

For $f(x)=x^2-a$, its derivative is $f^{\prime }(x)=2x$. Substitution into Newton's method givesEvery positive input gives another positive input, so a starting value $x_0>0$ keeps the denominator nonzero at every step.

The update in Newton's method is exactly $x_n=g(x_{n-1})$. Positivity is preserved, and the arithmetic-geometric mean inequality from part (a) applies to every update. ConsequentlyThis holds even when $0<x_0<\sqrt{a}$: the first update moves to or above the positive square root.

Subtract the previous iterate in Newton's method:The denominator is positive and the numerator is negative. If $x_{n-1}=\sqrt{a}$, the difference is zero and all subsequent iterates equal the root.

After the first update, the sequence lies in $[\sqrt{a},x_1]$ and is nonincreasing. The monotone convergence theorem for sequences gives a limit $L\ge \sqrt{a}$. The update is continuous on this interval, so passing to the limit givesPositivity forces $\boxed{x_n\to \sqrt{a}\text{ for every }{x}_0>0}$. If an iterate reaches the root exactly, the constant tail gives the same conclusion. The Exact Newton error identity for a quadratic here is $x_n-\sqrt{a}=(x_{n-1}-\sqrt{a}{)}^2/(2x_{n-1})$, also showing quadratic convergence once the error is small.

The constraint implies $x^2=z^2+1$, so $x\ne 0$ and its gradient $(2x,0,-2z)$ never vanishes on the feasible set. The Lagrange multiplier equations $\nabla f=\lambda \nabla g$ giveThus $\lambda =1$, $y=0$, $z=-1/2$, and feasibility gives $x=\pm \sqrt{5}/2$. The two stationary points and their values areThey are both global minima. Indeed, on the constraint, completing the square givesEquality holds only at the two displayed points. There are no other constrained stationary points, and the objective is unbounded above as $|y|\to \infty$.

Differentiating the polynomial coordinate map givesIts Jacobian matrix isThe determinant identifies where the inverse function theorem applies.

On a branch with fixed signs of $u,v$ and $uv\ne 0$, use $u^2=x+y$ and $v^2=y-x$. Differentiating these identities, or inverting the Jacobian matrix, givesThe inverse Jacobian matrix is thereforeThese are local partial derivatives. Choosing the signs specifies an inverse function on $y>|x|$; the original map has four preimages there and has no single global inverse. At $u=0$ or $v=0$, the displayed inverse derivatives are not finite.

The requested partial derivatives areThe last printed derivative has a misplaced superscript on $f$; the second-derivative list and subsequent Taylor expansion use $f_{yy}$.

Put $h=x-1$ and $k=y-1$. At $(1,1)$, the value is $5+4\alpha$, the gradient is $(5+4\alpha ,4+2\alpha )$, and the Hessian matrix is $\left(\begin{array}{cc}8& 2\alpha \\ 2\alpha & 2\end{array}\right)$. Thus the quadratic Taylor expansion isThe exact remainder is $h^3$, since the original polynomial has only the cubic term $x^3$ beyond degree two.

Solving $f_y=0$ gives $y=-1-\alpha x$. Substitution into $f_x=0$ gives $x\{3x+2(1-{\alpha }^2)\}=0$. Therefore $(0,-1)$ is always a critical point. When $\alpha \ne -1$ as well as the printed restriction $\alpha \ne 1$, there is a second critical pointAt $(0,-1)$, the Hessian matrix is $\left(\begin{array}{cc}2& 2\alpha \\ 2\alpha & 2\end{array}\right)$ with determinant $4(1-{\alpha }^2)$. The second-derivative test gives a strict local minimum when $|\alpha |<1$ and a saddle point of a scalar function when $|\alpha |>1$.

The allowed value $\alpha =-1$ requires higher-order terms. With $v=y+1+\alpha x$, completing the square gives the exact identityThe coordinate change is invertible, so the Hessian at a critical point under a change of coordinates preserves the classification. At $\alpha =-1$, this is a cubic degenerate saddle: along $v=0$, the difference from the critical value is $x^3$ and takes both signs. Thus, throughout the printed parameter range,There is no local maximum. When the second point is distinct, it is a local minimum for $|\alpha |>1$ and a saddle point of a scalar function for $|\alpha |<1$: in the $(x,v)$ coordinates its Hessian matrix is $\mathrm{diag}(-2(1-{\alpha }^2),2)$. The printed instruction to split only at $\alpha =1$ misses the negative-parameter cases.

Let $(B_i)$ be a finite or countable partition of a sample space into events of positive probability. The events $A\cap B_i$ are disjoint and their union is $A$. Countable additivity and the definition of conditional probability therefore give the law of total probabilityCells of zero probability contribute zero through $\mathbb{P}(A\cap B_i)$ and can be omitted rather than assigning an undefined conditional probability.

The two definitions of conditional probability giveSubstitution proves Bayes' theorem:The positive probabilities assumed in the question make both conditional expressions defined.

Mutual independence means that for every nonempty $I\subseteq \{1,2,3\}$,Beyond the trivial single-event identities, this requires the three pairwise equalities and the triple equality $\mathbb{P}(A_1\cap A_2\cap A_3)=\mathbb{P}(A_1)\mathbb{P}(A_2)\mathbb{P}(A_3)$. Pairwise independence alone omits that last requirement.