Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 2

The characteristic polynomial of this second-order linear differential equation factors as $r^2-r-6=(r-3)(r+2)$. Its two distinct roots give the general solution $y=A{e}^{3x}+B{e}^{-2x}$. Boundedness as $x\to \infty$ forces $A=0$, and the initial condition gives $B=1$.

Collecting the shifted terms gives a second-order difference equation with coefficients $1-h/2$, $-(2+6h^2)$ and $1+h/2$. Substitute $y_n=r^n$ to obtain its characteristic equation of a linear recurrence:For real $h\ne 0,2$, the roots and general solution areIn the small-step regime, indeed for $0<h<2$, the polynomial is positive at $r=0$, negative at $r=1$ and positive for sufficiently large positive $r$. Thus $0<r_{-}<1<r_{+}$. The bounded solution of a second-order constant-coefficient recurrence discards the growing root, and $y_0=1$ fixes its remaining coefficient:The Taylor series establishes the displayed approximation to the root. Raising that approximation to the $n$th power is a leading approximation, rather than a uniform relative approximation for arbitrarily large $n$: its relative error is controlled when $n{h}^2$ is small. For completeness, the degenerate values give $y_n=A+Bn$ when $h=0$, and $y_n=C13^{-n}$ when $h=2$.

Divide the second-order difference equation by $h^2$ and set $x=nh$. The first quotient is a central finite difference approximation to $y^{\prime \prime }(x)$; the quotient $(y_{n+1}-y_{n-1})/(2h)$ approximates $y^{\prime }(x)$. Their Taylor series errors are $O(h^2)$ for a sufficiently smooth function. This is therefore a finite difference method for the second-order linear differential equation in part (a).

At a fixed $x\ge 0$, take $h\to 0$ with $n=x/h$ integral. Since $\log r_{-}=-2h+O(h^3)$, the exact bounded discrete solution satisfiesLikewise $(1-2h{)}^{x/h}\to e^{-2x}$. The decay selected by boundedness in the linear recurrence relation becomes exactly the decay selected by boundedness in the ordinary differential equation.

Start from $I_0(\lambda )=1/\lambda$. Differentiation under the integral sign givesThis interchange is justified locally around any $\lambda >0$ by the dominated convergence theorem: the differentiated integrands are bounded by an integrable polynomial times $e^{-\lambda x/2}$. Successive derivatives of ${\lambda }^{-1}$ giveThis is also the integer case of the Gamma function integral after scaling the integration variable.

Use the inverse change of variables $u=(x+y)/2$ and $v=(x-y)/2$. The chain rule gives the differential operatorsThe mixed partial derivatives cancel, assuming the twice continuously differentiable solution appropriate here. Consequently $f_{xy}=(g_{uu}-g_{vv})/4$.

The transformed equation isThe factors of $1/2$ belong to the inverse Jacobian matrix; using the forward transformation instead would give an incorrect factor.

The independent and identically distributed random variables have a continuous probability distribution, so any tie has probability zero. Their joint probability density is unchanged by a permutation of their indices: this is order symmetry of independent random variables. The $n!$ strict orderings are disjoint and exhaust the sample space apart from the zero-probability ties. Each ordering therefore has the same probability, and their probabilities sum to one.

The moment-generating function of a random variable $Z$ is $m_Z(\theta )=\mathbb{E}[e^{\theta Z}]$, at the real values of $\theta$ for which that expectation is finite. For a standard normal distribution variable $X$, combining the exponentials in its probability density function yieldsThe last equality follows by scaling the Gaussian integral. The variables $X_i^2$ are independent random variables, so the expectation of their product factorizes. ThereforeThis is the moment-generating function of a chi-squared distribution with $n$ degrees of freedom. For positive $n$ the defining integral diverges at and above $\theta =1/2$.

Away from the impulse, the harmonic oscillator equation has a homogeneous solution. Before $x=\pi /2$, the initial conditions select $y=\cos x$. The jump condition for an impulse requires continuity of $y$ and a unit jump in $y^{\prime }$: a jump in $y$ would produce a derivative of the Dirac delta distribution, which is absent from the forcing, while integrating through the impulse gives $[y^{\prime }]=1$.

Just before the impulse, $y=0$ and $y^{\prime }=-1$. Just afterwards, $y=0$ and $y^{\prime }=0$, so uniqueness for the harmonic oscillator equation makes the subsequent solution identically zero. Equivalently the causal response is $H(x-\pi /2)\sin (x-\pi /2)$, with $H$ the Heaviside step function, and it cancels the original oscillation.

The solution isThe impulse cancellation of a harmonic oscillator produces a continuous graph with a corner at $(\pi /2,0)$, followed by a horizontal zero line.

With a positive cooling rate $k$, Newton's law of cooling gives $T^{\prime }=-k(T-T_0)$. The temperature excess $U=T-T_0$ satisfies the first-order linear differential equation $U^{\prime }=-kU$. Applying the initial condition to its exponential decay solution givesThe temperature approaches the ambient value $T_0$, rather than zero. The intended cooling situation has $T_0>0$ and $k>0$.

At the first half-temperature time, the solution of Newton's law of cooling givesSince $\alpha >2$, this time is positive and finite. The instantaneous temperature increase supplies the new initial condition $T(t_1+)=\alpha T_0/2+\beta$. Restart the same first-order linear differential equation at $t_1$:This is Newton cooling with an instantaneous temperature jump. The time translation in the exponential decay is essential: its prefactor is the excess immediately after the jump.

Each smooth segment follows Newton's law of cooling: $T^{\prime }=-k(T-T_0)<0$ and $T^{\prime \prime }=k^2(T-T_0)>0$. Thus the graph decreases and is convex on both sides of $t_1$. It starts at $\alpha T_0$, falls to $\alpha T_0/2$, jumps upward by $\beta$, and then decreases asymptotically to $T_0$.

The right-hand limit at the jump is above the original temperature, because $\beta >\alpha T_0/2$ implies $T(t_1+)>\alpha T_0$. The vertical dotted segment in the sketch denotes an instantaneous jump, not a continuous evolution through intermediate temperatures. The example uses $\alpha =4$, $\beta /T_0=3$; its qualitative shape holds for all the stipulated parameters.

Impose the target temperature on the post-jump exponential decay:Solving for the jump and eliminating $t_1$ using $e^{k{t}_1}=2(\alpha -1)/(\alpha -2)$ givesThis is the unique required temperature increase, and it satisfies the stipulated lower bound. Indeed $t_2>t_1$ impliesThus no additional restriction on the prescribed time is needed.

For the stated order of the two solutions, define their Wronskian byTaking a derivative cancels the two mixed products: $W^{\prime }=y_1{y}_2^{\prime \prime }-y_1^{\prime \prime }{y}_2$. Substituting the second-order linear differential equation for each second derivative cancels the $q$ terms and leavesThis is the Abel identity. On an interval with continuous coefficients, linear independence means $W(x_0)\ne 0$; hence the Wronskian never vanishes anywhere on that interval.

The defining Wronskian identity gives the first-order linear differential equationWork first on an interval where $y_1\ne 0$. Dividing by $y_1$ recognizes a derivative:This is reduction of order. Choose the nonzero Wronskian from the Abel identity to obtain linear independence. The constant $C$ only adds a multiple of $y_1$. If $y_1$ has zeros, this quotient formula is local; the resulting solution can be continued across ordinary zeros using the original second-order linear differential equation.

For real parameters, work on $x>0$ so arbitrary real powers are unambiguous. Taking derivatives givesThe residual after substitution isWhen $\gamma \ne 0$, $x^{\gamma }$ ranges over $(0,\infty )$. Evaluating at the zeros of the cosine first forces the sine coefficient to vanish; then the cosine coefficient vanishes identically. If $\gamma =0$, the nonzero constant $\cos 1$ cannot satisfy the equation. Thus the necessary and sufficient conditions areUnder these conditions the normalized coefficient is $p=(1-\gamma )/x$. The Abel identity gives $W=C{x}^{\gamma -1}$. Choose $C=\gamma$ and apply reduction of order on an interval where $\cos (x^{\gamma })\ne 0$:The substitution $u=x^{\gamma }$ evaluates the integral. After continuation across the cosine zeros,This is a power substitution for an oscillatory second-order equation: in the variable $u=x^{\gamma }$, the equation reduces to the harmonic oscillator equation.

Classification and characteristic exponents. For a normalized second-order linear differential equation, an ordinary point at zero means $p$ and $q$ are real analytic functions there. A regular singular point is a singular point where $xp$ and $x^{2}q$ nevertheless extend as real analytic functions to zero. Write $p_0={\lim }_{x\to 0}xp(x)$ and $q_0={\lim }_{x\to 0}{x}^{2}q(x)$. The lowest-power coefficient in the Frobenius method gives the indicial equationIts roots are the characteristic exponents at a regular singular point. If their difference is not an integer, there are two linearly independent solutions $x^{{\sigma }_j}{A}_j(x)$, with $A_j$ real analytic and $A_j(0)\ne 0$. For distinct real roots ${\sigma }_1>{\sigma }_2$ with integer difference, a solution for the larger root exists, and a second has the form $x^{{\sigma }_2}B(x)+c{y}_1\log x$; the logarithmic coefficient can vanish. For a repeated root, the second solution has the form $y_1\log x+x^{{\sigma }_1}B(x)$ after normalization. This is a Logarithmic Frobenius solution. Complex conjugate roots $a\pm ib$ give real solutions whose leading behaviour is $x^a\cos (b\log x)$ and $x^a\sin (b\log x)$, with analytic-series corrections. All these descriptions are on $x>0$, or on a fixed complex branch.

For the present equation, division by $x$ gives $p=1+(1-m)/x$ and $q=(1-m)/x$. Therefore $xp=x+1-m$ and $x^{2}q=(1-m)x$ are real analytic. Zero is regular singular when $m\ne 1$; when $m=1$, it is ordinary after removing the common factor $x$. In that exceptional case the normalized equation is $y^{\prime \prime }+y^{\prime }=0$.

For the Frobenius method substitution, the lowest coefficient and the general linear recurrence relation areThese equations come respectively from the coefficients of $x^{\sigma -1}$ and $x^{n+\sigma -1}$. At $m=1$, the same formal exponents $0,1$ describe the two possible leading powers at an ordinary point, rather than singular behaviour.

For the exponent $\sigma =m$, the linear recurrence relation reduces to $(m+n)a_n=-a_{n-1}$. The excluded nonpositive integers ensure that no denominator is zero. Normalize $a_0=1$ and iterate:The ratio test gives an infinite radius of convergence for the power series factor. Hence a solution isFor nonintegral $m$, choose instead the exponent $\sigma =0$. Since $n-m\ne 0$ for every positive integer $n$, its linear recurrence relation gives $n{a}_n=-a_{n-1}$. ThusThe distinct nonintegral leading exponents establish linear independence. More explicitly, $W(e^{-x},y_m)=m{e}^{-x}{x}^{m-1}$ by the Abel identity and the leading coefficient at zero, so the Wronskian is nonzero. The factor $x^m$ uses the real branch on $x>0$.

For positive integral $m$, the exponent-zero linear recurrence relation fixes $a_n=(-1{)}^n{a}_0/n!$ for $1\le n<m$, but at $n=m$ its factor $n-m$ vanishes and leaves $a_m$ free. Choose $a_0=1$ and $a_m=0$. All later coefficients then vanish by the same linear recurrence relation.

A polynomial solution of degree $m-1$ isFor $m=1$ this is the constant solution $1$, in agreement with the ordinary point exception. The terminating Frobenius series arises because the coefficient equation at the resonant index becomes $0=0$, permitting truncation rather than forcing a logarithm.

Here the indicial equation has the repeated root $0$. The first Frobenius method solution is $y_1=e^{-x}$. Since $p=1+1/x$, the Abel identity gives $W=C{e}^{-x}/x$. Reduction of order with $C=1$ produceswhere the additive constant is absorbed into $y_1$. In particular the logarithmic coefficient is nonzero: an additional independent real analytic solution does not exist.

The general local form isThis is the repeated-root Logarithmic Frobenius solution. On the negative real side one may use $\log |x|$, or use a fixed logarithm branch for a complex solution.

Write the system as ${\mathbf{x}}^{\prime }=M\mathbf{x}$, with $M=\left(\begin{array}{cc}2& 5\\ -1& -2\end{array}\right)$. Its characteristic polynomial is ${\lambda }^2+1$, so its eigenvalues are $i$ and $-i$. An eigenvector for $i$ is $v=(5,-2+i{)}^{\mathsf{T}}$. Thus $e^{it}v$ is a complex solution, and its real part and imaginary part give real solutions:Their initial vectors are $(5,-2{)}^{\mathsf{T}}$ and $(0,1{)}^{\mathsf{T}}$, with determinant $5\ne 0$. Consequently they are linearly independent and span the two-dimensional solution space.

For a constant matrix, the matrix exponential series and its differentiated series converge uniformly on bounded time intervals, as follows by comparison with the scalar exponential in a operator norm. Termwise derivatives therefore giveHence $\mathbf{x}(t)=e^{tM}{\mathbf{x}}_0$ solves the initial value problem. For this particular matrix, direct multiplication gives $M^2=-I$. Splitting the matrix exponential into its even and odd powers provesThis is the matrix exponential when the square is minus the identity. If ${\mathbf{x}}_0=(x_0,y_0{)}^{\mathsf{T}}$, the general solution isThe constants in part (a) are $\alpha =x_0/5$ and $\beta =y_0+2x_0/5$, which makes the two forms identical.

Set $U=X/(X+Y)$ and $V=X+Y$. Their inverse change of variables is $X=UV$, $Y=(1-U)V$, with domain $0<U<1$, $V>0$. The absolute Jacobian determinant of this inverse transformation isUse the independence of random variables to multiply the two original Gamma distribution densities. The change of variables formula then gives the joint probability densityFactor this into two normalized densities:The support is a product domain, and the factors are precisely a Beta distribution density and a Gamma distribution density. ThereforeThis beta-gamma independence uses the common rate $\theta$; it is a rate parameter, not the scale parameter $1/\theta$.

For any fixed bin, each ball supplies an independent Bernoulli distribution indicator with success probability $1/m$. Summing the $n$ indicator variables givesThe full occupancy vector has a multinomial distribution, the basic uniform balls-in-bins allocation. Distinct bin counts are not independent when $n\ge 1$ and $m\ge 2$. To see this, write $B_i={\sum }_{r=1}^n{I}_{r,i}$. For the same ball, $I_{r,i}{I}_{r,j}=0$ if $i\ne j$, while indicators from distinct balls are independent. Their covariance is thereforeWith no balls the counts are deterministic; with one bin there are no distinct bin pairs. These degenerate cases do not contradict the conclusion.

Express the three counts as sums of indicator variables for $B_i=0$, $B_i=1$ and $B_i\ge 2$. The linearity of expectation applies even though the bin counts are dependent. The binomial distribution givesThusThe relation $E+S+C=m$ checks the sum of these expectations. For $m=1$, use the direct deterministic occupancies, or the usual binomial convention $0^0=1$ when $n=1$.

There are more bins than balls, so the pigeonhole principle forces at least one empty bin. In fact $E\ge m-n=(a-1)n$. ConsequentlyFor the expected fraction, substitute $m=an$ into part (b). The elementary exponential limit, obtained by taking logarithms, givesThis is the empty-bin case of the Poisson limit for occupancy fractions, with limiting mean occupancy $1/a$.

If $C=0$, every bin contains at most one ball, so the total number of balls is at most $m$. Since $n=dm>m$, the pigeonhole principle makes that event impossible:As $n\to \infty$ along these values, $m\to \infty$ and the mean occupancy $n/m$ is $d$. Apply part (b):Both powers tend to $e^{-d}$. HenceThe Poisson limit for occupancy fractions interprets the answer as the probability that a Poisson distribution variable with mean $d$ is at least two.

Write $\mu =\mathbb{E}[X]$ and $A=\{X>\theta \mu \}$. The finite second moment implies a finite first moment, and nonnegativity with $\mathbb{E}[X^2]>0$ implies $\mu >0$. On $A^c$, one has $0\le X\le \theta \mu$. ThereforeSubtract this from $\mathbb{E}[X]=\mu$ to obtain the truncated first moment bound:The indicator function uses the strict event specified in the question; any mass at the threshold belongs to $A^c$.

For real random variables with finite second moments, the Cauchy-Schwarz inequality isThe product is integrable because $2|Y_1{Y}_2|\le Y_1^2+Y_2^2$. If $\mathbb{E}[Y_2^2]=0$, then $Y_2=0$ almost surely and the result is immediate. Otherwise the nonnegative expectation of a square gives, for every real $t$,Choose $t=\mathbb{E}[Y_1{Y}_2]/\mathbb{E}[Y_2^2]$. The resulting inequality is exactly the claimed Cauchy-Schwarz inequality. Equality holds precisely when $Y_1$ is a constant multiple of $Y_2$ almost surely in this nondegenerate case.

Apply the Cauchy-Schwarz inequality to $Y_1=X$ and the indicator variable $Y_2=1_A$. Since $1_A^2=1_A$, it givesBoth sides of the truncated first moment bound in part (a) are nonnegative, so squaring it preserves the inequality. Combining the bounds and dividing by the positive second moment provesThis is the Paley-Zygmund inequality. It includes $\theta =0$; at $\theta =1$ the lower bound is zero and remains valid.

For each unordered triple of distinct vertices, let $I_A$ be the indicator variable that its three edges are present. This is a binomial random graph, so edge independence gives $\mathbb{E}[I_A]=p^3$. The triangle count in a binomial random graph is $T={\sum }_A{I}_A$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ such triples; all are triangles in the complete graph.

The combinatorial maximum and expectation areThe maximum is attainable with positive probability if $p>0$; for $p=0$, the random variable is identically zero. The linearity of expectation requires no independence between different triangle indicators.

The Markov inequality states that for a nonnegative random variable $Z$ and $a>0$,Because $T$ is integer-valued, apply it with $a=1$. With $p=n^{-\alpha }$,ThereforeThis is the first moment method: if the expected triangle count in a binomial random graph tends to zero, triangles occur with vanishing probability.

The Chebyshev inequality states that for a random variable $Z$ with finite variance and $a>0$,Write ${\mu }_n=\mathbb{E}[T]$. The ratio in the hypothesis presupposes ${\mu }_n>0$ for all sufficiently large $n$. On the event $T=0$, the deviation from the mean equals ${\mu }_n$. Thus the Chebyshev inequality with $a={\mu }_n$ givesThis is the second moment method. It uses only the stipulated relative variance bound; no assumption that triangle indicators are independent is needed.