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

Substitution of $y_n=r^n$ gives the characteristic equation of a linear recurrenceThe repeated characteristic root of a linear recurrence $1$ supplies the solutions $1$ and $n$, while the simple root $-2$ supplies $(-2{)}^n$. They are linearly independent: their values at three consecutive indices have nonzero determinant. A third-order linear recurrence relation is uniquely determined by three consecutive initial values, so these three solutions span its solution space. The general solution is

Let $L[y{]}_n=y_{n+3}-3y_{n+1}+2y_n$. For the exponential trial sequence $D{2}^n$,Thus $D=1/4$ gives a particular solution. The difference of any two solutions of the inhomogeneous linear recurrence satisfies the homogeneous linear recurrence relation in part (i). Therefore

The forcing base $-2$ is a root of the characteristic equation of a linear recurrence, so a constant multiple of $(-2{)}^n$ cannot be a particular solution. For $P(r)=r^3-3r+2$, direct substitution givesFor the resonant case of exponential forcing in a linear recurrence, at $r=-2$, $P(-2)=0$ and $(-2)P^{\prime }(-2)=-18$. Hence $-(n/18)(-2{)}^n$ is a particular solution of the inhomogeneous linear recurrence. The general solution is

The superposition principle applies because the recurrence operator is linear. Add the particular solutions from parts (ii) and (iii), then add the general homogeneous linear recurrence relation solution from part (i). This gives

The first-order chain rule, with $x,y$ regarded as functions of $u,v$, isApply the product rule when differentiating the first identity in $v$, and apply the chain rule to $f_x,f_y$. Equality of mixed partial derivatives for a $C^2$ function givesThus $\boxed{H=x_{uv},K=y_{uv}}$. These terms record the second derivatives of the coordinate transformation, not of $f$.

For the given transformation,The mixed-derivative coefficient is zero, while $x_u{x}_v=x$, $y_u{y}_v=-y^2/x$, and $1/v^2=y/x$. The required partial differential equation is therefore exactly $g_{uv}=0$. Integrating first in $u$ and then in $v$ on a coordinate rectangle giveswhere $A,B$ are arbitrary twice continuously differentiable functions. The Jacobian determinant of the transformation is $-2u/v$, so this calculation uses patches with $u,v\ne 0$. On a positive-quadrant patch we can take $u=\sqrt{xy}$ and $v=\sqrt{x/y}$, obtainingChanging branches merely redefines the arbitrary functions.

For completeness, the original equation also makes sense in quadrants with $xy<0$, where that particular real square-root transformation is unavailable. Multiplying the equation by $x$ givesOn any quadrant with $xy\ne 0$, put $a=\log |x|$, $b=\log |y|$; then set $\xi =a+b$, $\eta =a-b$. The equation becomes $4f_{\xi \eta }=0$. Thus an equivalent general local answer on every such quadrant isHere $\Phi ,\Psi$ are arbitrary $C^2$ functions on the relevant intervals. If a solution is required across $y=0$, its quadrant expressions must extend with matching derivatives; on that line the equation itself imposes $x{f}_{xx}(x,0)+f_x(x,0)=0$, so its trace is $a_0\log |x|+b_0$ on each interval with $x\ne 0$. The displayed coordinate transformations do not assert invertibility at $y=0$.

For $m\ge 2$, $f^{\prime \prime }(x)=m(m-1)x^{m-2}\ge 0$ on $[0,\infty )$, so $f$ is a convex function; for $m=1$ it is linear and also convex. The equally weighted random variable has expected value $EX=N^{-1}{\sum }_i{x}_i=1/N$. Applying Jensen's inequality givesMultiplying by $N$ provesFor $m>1$ equality requires all $x_i=1/N$, by strict convexity; for $m=1$ equality holds for every admissible vector.

For a fixed horse $i$, independence of the race results gives probability $p_i^m$ of winning every race. The events that different horses win every race are disjoint, soThis is a homogeneous polynomial of degree $m$. Apply part (a) to the nonnegative numbers $p_i$, whose sum is one, to obtain $\boxed{Q\ge N^{1-m}}$. For $m>1$ the smallest probability occurs when every horse has winning probability $1/N$; for a single race $Q=1$ regardless of these probabilities.

Put $U=X-EX$ and $V=Y-EY$. Their second moments are the finite positive variances of $X,Y$. The Cauchy-Schwarz inequality for square-integrable random variables givesDivide by the positive product of variances and take square roots. The correlation bound is $\boxed{-1\le \rho (X,Y)\le 1}$. As usual, non-constant here means not almost surely constant, so that the denominator is nonzero.

Zero correlation means that the variables are uncorrelated: $E[(X-EX)(Y-EY)]=0$, or equivalently $E(XY)=EXEY$. It does not imply independence. For example, if $X$ is uniform on $[-1,1]$ and $Y=X^2$, symmetry gives $EX=E(X^3)=0$, hence zero covariance, although $Y$ is determined by $X$. Both random variables are non-constant and have finite positive variances.

Perfect correlation means an affine relation almost surely: there are constants $a\ne 0,b$ such that $Y=aX+b$ almost surely. The sign of $a$ is the sign of the correlation coefficient. More precisely, equality in the Cauchy-Schwarz inequality gives

Interpret the random choice as an independent selector $B$ with $P(B=1)=r$, and write $Y=BX+(1-B)X^{\prime }$. Its distribution is again uniform on $\{-1,1\}$, so $EX=EY=0$ and $\mathrm{Var}X=\mathrm{Var}Y=1$. By independence,Consequently $\boxed{\rho (X,Y)=r}$. The independent selector is the standard meaning of the stated mixture; a choice depending on the signs would describe a different model.

Let $D=d/dx$ and write the constant-coefficient linear ordinary differential equation as $p(D)y=0$. Since $D^k{e}^{\lambda x}={\lambda }^k{e}^{\lambda x}$,The exponential never vanishes, so $\boxed{e^{\lambda x}\text{ solves the equation }⟺p(\lambda )=0}$.

For the second claim, the product rule givesfor $k\ge 1$, with the $k=0$ term treated separately. Summing the coefficients yieldsA root of multiplicity at least two has $p(\mu )=p^{\prime }(\mu )=0$, proving $x{e}^{\mu x}$ is also a solution. This directly establishes the repeated-root contribution without assuming a solution formula. If the displayed coefficient list has leading zeros, the exponential calculation still applies to its actual polynomial degree.

Set $v=u^{\prime \prime }$. The resulting second-order linear differential equation is $v^{\prime \prime }+2v=4t^2$. A polynomial particular solution $v_p=a{t}^2+b$ requires $2a=4$ and $2a+2b=0$, hence $v_p=2t^2-2$. The homogeneous characteristic roots of a constant-coefficient differential equation are $\pm i\sqrt{2}$, soIntegrating twice and renaming constants gives the general real solutionThe four independent homogeneous terms account for the four initial data of the fourth-order linear ordinary differential equation.

For the substitution $u(t)=y(t^2)$, repeated use of the chain rule, with $x=t^2$, givesThereforeFor $x>0$, the map $t=\sqrt{x}$ is invertible, and the transformed equation is exactly the equation just solved. Hence the general real solution on $x>0$ isThere is no requirement that $u$ extend as an even function through $t=0$: only the branch $t>0$ is needed, so the sine and square-root terms must be retained.

Substitute the power series and compare coefficients. The constant coefficient gives $-a_1-a_0=0$. For $k\ge 1$, the coefficient of $x^k$ givesThus $a_1=-a_0$, while the $k=1$ equation places no restriction on $a_2$. For $k\ge 2$,The power series therefore sums toRenaming the two arbitrary constants gives $\boxed{y(x)=C(1-x)+D{e}^{-x}}$.

Both functions solve the equation by direct substitution. Their Wronskian, in the order $1-x,e^{-x}$, is $x{e}^{-x}$, which is nonzero for $x\ne 0$. Hence they give the full two-dimensional solution space on either interval away from the singular point. Both are entire, and the displayed formula also gives every twice continuously differentiable solution through zero: matching $y(0)$ and $y^{\prime \prime }(0)$ fixes the same $C,D$ on the two sides.

For two solutions $y_1,y_2$, define their Wronskian byDifferentiation and substitution of the second-order linear differential equation giveThis proves the Abel identity and hence

On an interval where the known solution $y_1$ does not vanish,Integrating gives the reduction of order formulaChoosing the normalization $C=1$ makes the Wronskian nonzero, so this solution is linearly independent of $y_1$. To verify it really solves the equation, write $y_2=y_{1}h$. Its equation reduces tothe integrand gives $h^{\prime }=\exp (-\int p)/y_1^2$, which satisfies this equation on differentiation. Adding an integration constant only adds a multiple of $y_1$. The formula is local where $y_1\ne 0$; at a zero of $y_1$ with regular coefficients, the actual solution can be continued by initial-value existence and uniqueness, even if its integral representation has an apparent singularity.

Multiply the equation by $x$ to obtain $x{y}^{\prime \prime }-P(x)y^{\prime }-Q(x)y=0$. The leading terms after a Frobenius method trial $y=x^r$ arethe term involving $Q_0$ first appears at order $x^r$. The indicial equation is therefore

To obtain the first correction to a regular singular solution by reduction of order, start from the assumed solution $y_1=1+\beta x+O(x^2)$ and use the Abel identity:We work initially on $x>0$ near zero; since $P_0$ is a positive integer, the resulting expansion is an ordinary power series. Also $y_1^{-2}=1-2\beta x+O(x^2)$, so the reduction of order integral has integrandChoose its integration constant to be zero, eliminating an added multiple of $y_1$. Integrating and multiplying by $y_1$ givesWith $C=P_0+1$ the requested normalized answer isIts nonzero Wronskian makes it independent of $y_1$. The existence of the asserted $y_1$ also forces $P_0\beta +Q_0=0$; there is no need to introduce $Q_0$ into the normalized second coefficient.

Write the coefficient matrix as $M$. Its characteristic polynomial is $\det (rI-M)=r(r-2)(r+2)$. Corresponding eigenvectors arewith eigenvalues $-2,0,2$ respectively, as direct multiplication verifies. Distinct eigenvalues make these vectors a basis. Expanding a solution as $z_{-}{v}_{-}+z_0{v}_0+z_{+}{v}_{+}$ decouples the linear ordinary differential equations into ${\dot{z}}_{-}=-2z_{-}$, ${\dot{z}}_0=0$, ${\dot{z}}_{+}=2z_{+}$. Thus the general solution is

The forcing vector has the eigenvector decompositionThere is no component in the zero eigenvalue direction. The scalar inhomogeneous linear differential equations in this basis areFor the first, a particular solution is $(\lambda +1)e^{2t}/4$. For the third, multiplying by the integrating factor $e^{-2t}$ gives $(e^{-2t}{z}_{+}{)}^{\prime }=\lambda -1$. Consequently for every real $\lambda$When $\lambda =1$, the resonant component vanishes and a particular solution is $\frac{1}{2}{v}_{-}{e}^{2t}$, of the stipulated constant-vector form. If $\lambda \ne 1$, substituting $c{e}^{2t}$ would require $(2I-M)c=2(-\lambda ,1,\lambda {)}^T$. In the eigenbasis the left side has zero $v_{+}$ component, while the right side has component $\lambda -1$. This is impossible. The factor $t$ is therefore unavoidable: it is resonance in a differential equation.

At $\lambda =-1$ the $v_{-}$ forcing vanishes and the $v_{+}$ forcing coefficient is $-2$. The initial vector decomposes asThus $A=1/2$, $B=0$, $C=-1/2$ in part (b), and the requested solution isEquivalently,These expressions have the required initial values and solve all three linear ordinary differential equations.

At a critical point $p$ of a twice continuously differentiable function, the linear term in the Taylor expansion vanishes:The real symmetric Hessian matrix has an orthonormal basis of eigenvectors. If all its eigenvalues are positive, its quadratic term is bounded below by a positive multiple of $\Vert h{\Vert }^2$, giving a strict local minimum. If all are negative, it gives a strict local maximum. If positive and negative eigenvalues both occur, directions along their eigenvectors give values on both sides of $f(p)$, so the point is a saddle point of a scalar function. The non-singularity assumption excludes zero eigenvalues; with them the quadratic test may be inconclusive and higher-order terms are needed.

The gradient components areIf $x=0$ or $y=0$, their simultaneous zeros give $(0,0),(0,1),(1,0)$. If $xy\ne 0$, solving $2x+y=1$, $x+2y=1$ gives $(1/3,1/3)$. These are all the critical points. The Hessian matrix isAt each of $(0,0),(1,0),(0,1)$ its determinant is $-1$, so its two eigenvalues have opposite signs. All three are saddle points of a scalar function. At $(1/3,1/3)$,This point is a strict local maximum, of value $\boxed{1/27}$.

The zero level set is exactlyThese three lines form a triangle containing the maximum. Inside it $f>0$; near the maximum positive level sets are nested closed curves, with their leading shapes elliptical because the Hessian matrix is negative definite. At each vertex the zero lines cross, separating alternating signs, and nearby nonzero level sets have hyperbolic branches. For example, the leading quadratic terms are $xy$ at $(0,0)$, $-\eta (\xi +\eta )$ for $\xi =x-1,\eta =y$ at $(1,0)$, and $-\xi (\xi +\eta )$ for $\xi =x,\eta =y-1$ at $(0,1)$.

Put $\xi =x$ and $\eta =y-1$. The polynomial becomesThere are no terms of degree one or two, so the gradient and the entire Hessian matrix vanish at $(0,1)$. It is a critical point with singular Hessian matrix. The lowest nontrivial approximation isunderstood as the fourth-degree leading term rather than a uniform ratio asymptotic along its zero directions.

On the path $\eta =0$ the exact value is $-{\xi }^4<0$ for $\xi \ne 0$. On the path $\eta =-2\xi$ it is ${\xi }^4(1-2\xi {)}^2>0$ for sufficiently small nonzero $\xi$. Both paths approach the point, where $g=0$. It is neither a local maximum nor a local minimum; it is a degenerate saddle point of a scalar function. The higher-order saddle test supplies the conclusion the singular Hessian matrix cannot supply.

A geometric distribution with parameter $p$ on $\{1,2,\dots \}$ has probability mass functionIt counts the trial on which the first success occurs in independent trials with success probability $p$. Its probability generating function is $ps/[1-(1-p)s]$. Differentiating at $s=1$ givesThis support convention is important: a count of failures before the first success would start at zero.

This is the waiting time to observe both Bernoulli outcomes. Write $q=1-p$, and let $S$ record the sex of the first captured animal. That first capture is always needed. If $S$ is male, every subsequent trial independently produces the required female with probability $q$, so $N-1$ has a geometric distribution with parameter $q$. If $S$ is female, $N-1$ has a geometric distribution with parameter $p$. By the law of total expectation,Since $p+q=1$, this simplifies to $\boxed{EN=1/(pq)-1}$, orThe expectation includes both the first capture and the final capture completing the pair.

Use the same first-sex conditioning as in part (b). The conditional variances are $p/q^2$ after a male first capture and $q/p^2$ after a female first capture. ThusThe conditional expected values are $1+1/q$ and $1+1/p$, with probabilities $p,q$. A variable taking two values $a,b$ with probabilities $p,q$ has variance $pq(a-b{)}^2$, soThe law of total variance now givesAt $p=q=1/2$ this gives variance $2$, consistent with $N$ being one plus a geometric waiting time of parameter $1/2$.

The event $Y_n\le z$ occurs precisely when every one of the first $n$ levels is at most $z$. Their independence gives the cumulative distribution functionFor any nonnegative random variable, the pointwise identity $Y_n={\int }_0^{\infty }{1}_{\{Y_n>z\}}dz$ and the Tonelli theorem allow interchange of expectation and integral. HenceThis identity holds as an extended nonnegative integral; finiteness of the mean is not guaranteed by continuity of $F$.

The future levels are independent of the observed maximum. Given $Y_n=z$, the first $k-1$ future levels must be at most $z$, and the $k$th must exceed $z$. Each non-overflow has probability $F(z)$ and an overflow has probability $1-F(z)$. ThereforeThis is a geometric distribution of parameter $1-F(z)$ when $F(z)<1$. Since $Y_n$ has a continuous distribution, conditioning on an exact value is understood via a regular conditional distribution, rather than division by $P(Y_n=z)=0$. The formula specifies its usual version. If $F(z)=1$ there is no possible overflow at that threshold, but such thresholds have probability zero for the random observed maximum.

The continuity of the cumulative distribution function gives the probability integral transform: $F(X_i)$ is uniform on $[0,1]$. Strict monotonicity or a probability density for $F$ is not required. Since $F$ is nondecreasing,By independence, $P(U\le u)=u^n$ for $0\le u\le 1$, so $U$ has probability density function $n{u}^{n-1}$. Average the conditional probability in part (b) using this distribution:Thus $\boxed{P(\tau =k)=n/[(k+n-1)(k+n)]}$. The expression telescopes to total mass one, so the waiting time is finite almost surely.

For the waiting time for a new record after a fixed sample, given $U=F(Y_n)$, no overflow in the first $k$ subsequent years has probability $U^k$. Averaging as in part (c) yieldsThe tail-sum formula for expectation therefore givesThe answer is $\boxed{E\tau =\infty }$. This does not contradict almost-sure finiteness: the tail probability tends to zero, but too slowly for its sum to converge.

Conditional on $X_n=m$, the next generation is the sum of $m$ independent offspring counts, each with probability generating function $F_1(s)$. HenceThis also holds for $m=0$, when the empty sum is zero and the empty product is one. The law of total expectation givesFor complex $|s|\le 1$, the expectations are absolutely bounded because $|F_1(s)|\le 1$. This proves the branching-process generating-function iteration, with $F_0(s)=s$.