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

The set difference consists of elements belonging to the first set but not the second:The symmetric difference consists of elements belonging to exactly one of the two sets:In particular, the two sets in this union are disjoint sets.

Every complement of a set is taken in the same universal set $\mathcal{U}$. Apply De Morgan's laws for propositional logic to the membership propositions. For every $x\in \mathcal{U}$,Equality of membership for every element proves the set identities

Using set difference as an intersection with a complement of a set, and using double negation, givesInterchanging the two sets simply interchanges the two terms of this union, whose commutativity gives

We use a double inclusion proof. First, let $x\in \overline{A\oplus B}$. If $x\in A$, then $x\in B$, since otherwise $x\in A\setminus B\subseteq A\oplus B$. Hence in this case $x\in A\cap B$. If $x\notin A$, then $x\notin B$, since otherwise $x\in B\setminus A\subseteq A\oplus B$. Hence in this case $x\in \overline{A\cup B}$. This proves the first set inclusion.

Conversely, an element of $A\cap B$ belongs to neither $A\setminus B$ nor $B\setminus A$. An element of $\overline{A\cup B}$ also belongs to neither set difference. Thus every element of $(A\cap B)\cup \overline{A\cup B}$ lies outside $A\oplus B$, proving the reverse set inclusion. Therefore

The identity function fixes every element, and function composition means applying the inner function first:

If $f(x)=f(y)$, applying the function $f$ gives $f(f(x))=f(f(y))$. Since $f\circ f={\mathrm{id}}_A$, this implies $x=y$, proving injectivity. Also every $y\in A$ is the image of $f(y)$, because $f(f(y))=y$, proving surjectivity.

Thus $f$ is a bijection and its inverse function is itself:Such a function is an involution.

Take the functionThen $f(f(x))=-(-x)=x$ for every real number $x$, while $f(1)=-1\ne 1$. Thus it is an involution different from the identity function.

Seek an affine function $f(x)=cx+d$. Its function composition with itself isEquating coefficients requires $c^2=a$ and $(c+1)d=b$. Because $a>0$ and $a\ne 1$, either choice $c=\sqrt{a}$ or $c=-\sqrt{a}$ has $c+1\ne 0$. Thus two valid functions areSubstitution into $c^{2}x+(c+1)d$ verifies each answer. These provide the requested maps; no assumption that every possible solution is affine function is needed.

Try a linear function $f(x)=cx$. The functional equation becomes $c^{2}x=(c+1)x$ for all $x$, so $c$ must be a root of a polynomial $c^2-c-1$. Its two roots of a polynomial giveFor either choice, $c^2=c+1$ proves the required equality directly. The positive coefficient is the golden ratio.

There are $n(n-1)\cdots (n-k+1)$ ordered selections without replacement. Each unordered $k$-element subset occurs in exactly $k!$ orders, so the binomial coefficient isOne precise specification of its domain, codomain, and map isHere ${\mathbb{N}}_0=\{0,1,2,\dots \}$, and $0!=1$ includes the single empty selection. The actual values on $D$ are positive, so ${\mathbb{N}}_{+}$ is also a valid codomain. For fixed $n$, one can instead use the function $C_n:\{0,\dots ,n\}\to {\mathbb{N}}_{+}$ with $C_n(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Apply the factorial formula for the binomial coefficients:For $n=0$ or $n=1$, the same equality holds with the conventional zero value when the lower index exceeds the upper index.

For $0\le k\le n$, the adjacent binomial coefficients obeySince $\left(\genfrac{}{}{0ex}{}{n}{k}\right)>0$ and $k+1>0$, the sign is determined by the numerator:The printed codomain ${\mathbb{N}}_{+}$ is inconsistent with the displayed map: $g(n)=-1$, and when $n$ is odd, $g((n-1)/2)=0$. With the usual extension $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ for $k>n$, $g$ is a function ${\mathbb{N}}_0\to \mathbb{Z}$, and $g(k)=0$ for $k>n$; the positive range above remains unchanged. Without that extension, the natural domain is $\{0,\dots ,n\}$.^[ref]

In the intended range $0\le k\le n$, division by the positive binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ givesConsequently the intended remainder isThere is a necessary qualification to the printed unrestricted domain. If binomial coefficients outside $0\le k\le n$ are extended by zero, then every $k>n$ satisfies $g(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$, regardless of $n\mathrm{mod}3$. For example, $n=3,k=4$ satisfies the literal equality but has $n\mathrm{mod}3=0$. Thus the literal extended-domain premise alone does not determine a remainder; the boxed conclusion requires $0\le k\le n$, or equivalently here $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ne 0$.

For adjacent binomial coefficients, the ratiois greater than $1$ when $k<(n-1)/2$, equal to $1$ at $k=(n-1)/2$, and less than $1$ afterwards. For odd $n$, the row is therefore increasing up to its two equal central entries and decreasing after them. The maximum is attained exactly atThey are distinct, including when $n=1$, so $k^{\ast }$ is not unique. This is the unimodality of binomial coefficients.

We prove Cassini's identity by mathematical induction. At $n=1$,Suppose $D_n=F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$. The Fibonacci recurrence gives $F_{n-1}=F_{n+1}-F_n$ and henceThe induction proves

For a nonzero geometric sequence, substitute $H_n=c{q}^n$ into the linear recurrence and cancel $c{q}^{n-1}$:The characteristic equation of a linear recurrence therefore has rootsThe zero sequence $c=0$ is a degenerate solution for any $q$ for which the displayed expression is defined. A nonzero sequence with $q=0$ cannot satisfy the recurrence at $n=1$, since it would require $0=0+H_0$.

The linearity of the Fibonacci recurrence allows a linear combinationThe initial conditions give $A+B=0$ and $A\varphi +B\psi =1$. Since $\varphi -\psi =\sqrt{5}$, we obtain $A=1/\sqrt{5}$ and $B=-1/\sqrt{5}$. Thus Binet's formula is

Use mathematical induction with two base cases. At $n=0$, the formula gives $(1-1)/\sqrt{5}=0=F_0$. At $n=1$, it gives $(\varphi -\psi )/\sqrt{5}=1=F_1$.

If it holds at $n-1$ and $n$, then the Fibonacci recurrence givesThe identities ${\varphi }^2=\varphi +1$ and ${\psi }^2=\psi +1$ turn the numerator into ${\varphi }^{n+1}-{\psi }^{n+1}$. Thus

For functions $f,g:\mathbb{N}\to \mathbb{R}$, big O notation meansUsing the natural logarithm and exponential function, $3^{\log n}=n^{\log 3}$. Since $\log 3>1$, for every $n\ge 1$ we have $n\le n^{\log 3}$. The witnesses $C=1,N=1$ therefore prove

For $n\ge 1$, $\log 3<2$ implies $3^{\log n}=n^{\log 3}\le n^2$, and also $n\le n^2$. ConsequentlyThe definition of big O notation holds with $C=4,N=1$:

Suppose the definition of big O notation held with constants $C>0,N$. Choose an odd integer $n>\max (C,N)$. At this input, $f(n)=n$ and $g(n)=1$, so the required inequality would be $n\le C$, a contradiction. ThusThe infinitely many even inputs, where $f(n)/g(n)=1/n$, cannot repair the failure on odd inputs because the bound must hold for every sufficiently large input.

A direct mathematical induction proves $0\le F_n\le 2^n$. The base cases $F_0=0\le 1$ and $F_1=1\le 2$ hold. If the bound holds at $n-1$ and $n$, then the Fibonacci recurrence givesThus the definition of big O notation holds with $C=1$, proving

By divisibility, write $a=nu$ and $b=nv$ for positive integers $u,v$. ThenThe factor $u^2-v^2$ is an integer, so

The Euclidean division gives $a=qb+r$ with $q\in {\mathbb{N}}_0$ and $0\le r<b$. Writing $a=nu,b=nv$ givesSince $u-qv$ is an integer, this proves the divisibilityincluding $r=0$.

The greatest common divisor is the largest positive integer dividing both inputs:This maximum exists because $1$ belongs to the set and all its elements are at most $b$.

Write $a=qb+r$ using the Euclidean division. If $d\mid a$ and $d\mid b$, then $d\mid (a-qb)=r$. Conversely, if $d\mid b$ and $d\mid r$, then $d\mid (qb+r)=a$. Therefore $(a,b)$ and $(b,r)$ have exactly the same positive common divisors, provingFor $r=0$, this agrees with $\gcd (b,0)=b$.

Set $(a_0,b_0)=(a,b)$. At each iteration with $b_i>0$, compute the remainder $r_i=a_i\mathrm{mod}{b}_i$, then setStop at the first index $n$ with $b_n=0$ and return $a_n$. The positive second coordinates strictly decrease, so algorithm termination follows from the well-ordering principle. The equality of greatest common divisors established in (ii) is a loop invariant, and at termination it gives

Consider one iteration with $a_i>b_i>0$ and $r_i=a_i\mathrm{mod}{b}_i$. If $b_i\le a_i/2$, then $r_i<b_i\le a_i/2$. If $b_i>a_i/2$, the quotient is $1$, so $r_i=a_i-b_i<a_i/2$. In either case $r_i<a_i/2$, whenceRepeated application, or mathematical induction, provesThis also holds for the final iteration, whose left side is zero. For zero iterations the correct relation is equality $a_0{b}_0=ab$, rather than a strict inequality.

Count the final division producing zero as an iteration, and let the total be $n$. The terminal product $a_n{b}_n=0$ alone gives no useful bound. Instead apply (i) to each nonterminal product, which is a positive integer and hence at least $1$.

If $n\ge 2$, the penultimate product satisfiesAs $n$ is an integer, this impliesFor $n=1$, the same bound holds since $a>b\ge 1$ implies $ab\ge 2$. In particular the Euclidean algorithm uses $O(\log a+\log b)$ divisions, in big O notation. The convention that includes the final zero-producing division explains the one-step offset in the argument.

The second coordinate after two iterations satisfieswhenever those two divisions are needed, by the same remainder bound, now applied to $b_i>b_{i+1}>0$. Let $m=\lfloor {\log }_{2}b\rfloor$. If the Euclidean algorithm has not already stopped after $2m$ iterations, then its positive second coordinate is at most $1$: for $m\ge 1$,For $m=0$ the original $b$ is already $1$. A second coordinate of $1$ requires just one more division. ConsequentlyThis removes dependence on the potentially much larger input $a$. It improves the scale ${\log }_2(ab)$ to one involving only the smaller input; the rounded numerical bound need not be smaller for every pair. One may always take the minimum of the bounds in (ii) and (iii).

Assume the homogeneous function is differentiable. Applying the multivariable chain rule to $f(tx,ty)=t^{m}f(x,y)$ gives, for $t$ near $1$,Setting $t=1$ proves Euler theorem for homogeneous functions:Only positive $t$ near $1$ are needed, so the derivation remains valid even when a noninteger $m$ makes the printed phrase “all real $t$” require qualification.

The linear ordinary differential equation has differential operator $(D-3{)}^2$. Put $y=e^{3x}v$ and use the product rule twice:Substitution cancels the $v$ and $v^{\prime }$ terms, leaving $v^{\prime \prime }=4$. Two integrations give $v=2x^2+C_{1}x+C_2$. Hence the general solution isThe two arbitrary constants account for the order of the differential equation; the $x^2$ factor in the particular term reflects the repeated root $3$ of the characteristic polynomial.

On an interval with $x\ne 0$, set $y=xv$. The product rule gives $y^{\prime }=v+x{v}^{\prime }$, and substitution givesThis is a separable differential equation. Since $1+v^2>0$ for real $v$, separation loses no real constant solution:Thus the general solution on any interval avoiding zero and the poles of the tangent function isAt $x=0$ the original differential equation forces $y(0)=0$, but no real solution from this family extends over a whole interval through zero: $\log |x|+C$ encounters infinitely many poles as $x\to 0$.

For $x\ne \pm 1$, write the linear ordinary differential equation asAn integrating factor on each interval avoiding $\pm 1$ is $\mu (x)=1/(1-x^2)$; multiplication by a nonzero constant, including a sign, is immaterial. ThereforeThe partial fraction decomposition isIntegrating gives the general solutionThe constant is independent on each connected interval of definition. At the singular points the undivided differential equation forces $y(1)=0$ and $y(-1)=1$. The displayed family tends to these values, but its derivative has a logarithmic divergence there, so no member extends as a differentiable function through either singular point.

The chain rule givesThe exponential function never vanishes, so all critical points areIn particular $f^{\prime }(0)=0$.

Use the Taylor series $e^u=1+u+u^2/2+\cdots$ with $u=x^3-x^5$. Since $u$ begins at cubic order and $u^2$ begins at sixth order, through cubic terms the Taylor series isThe linear and quadratic coefficients are zero. The stronger remainder $O(x^5)$, in big O notation, follows because the fourth-order term is also zero; the next term is $-x^5$.

Near zero, $x^3-x^5=x^3(1-x^2)$ has the sign of $x$, so $f(x)<1$ just to the left and $f(x)>1$ just to the right. Thus the critical point is neither a local minimum nor a local maximum. Moreover the Taylor series gives $f^{\prime \prime }(x)=6x+O(x^3)$, which changes sign at zero. ThereforeThis is the point called a “saddle point” in the question; stationary inflection point specifies the one-variable meaning.

Solving the linear ordinary differential equation and imposing the initial condition givesAs $\lambda >0$, the requested limit is

Let $h=1/N$, $x_j=jh$, and let $y_j$ approximate $y(x_j)$. The forward Euler method gives the difference equationThis geometric sequence has solutionFor fixed $\lambda$, the limit as $N\to \infty$ is $2e^{-\lambda }$, as required by the exact solution.

The amplification factor is $R=1-\lambda /N$. To reproduce decay, the forward Euler method requires $|R|<1$, equivalentlyAt $N=\lambda /2$, $R=-1$ and the approximations alternate with constant magnitude $2$; for $N<\lambda /2$, $|R|>1$ and the magnitude grows. This is the condition of absolute stability for this decaying differential equation.

Stability is only a minimum requirement. Values just inside the bound can still give a poor endpoint approximation; resolving the decay accurately generally requires a smaller step size. If positivity at every step is desired, the stronger condition $N\ge \lambda$ ensures $R\ge 0$. The figure shows the difference between decay of the exact solution and numerical oscillation.