Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 1

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_1,\dots ,m_s$, every choice of residues determines exactly one residue class modulo $M={\prod }_j{m}_j$. Equivalently $\mathbb{Z}/M\mathbb{Z}\to {\prod }_j\mathbb{Z}/m_j\mathbb{Z}$ is an isomorphism under reduction.

The first two modular congruences combine to $x=2+15k$. Reducing this expression modulo seven gives $2+k\equiv 6$, so $k=4+7j$. Consequently all integer solutions areThe moduli are pairwise coprime, so the Chinese remainder theorem guarantees that this is the entire solution class.

Define the Lagrange interpolation polynomialsDistinct interpolation nodes ensure every denominator is nonzero and $L_j(x_i)={\delta }_{ij}$. For a polynomial of degree at most $n-1$, the difference $P(x)-{\sum }_{j}P(x_j)L_j(x)$ has degree at most $n-1$ and vanishes at $n$ distinct points, so it is zero. Integrating this Lagrange interpolation identity proves the required exact quadrature formula. This also covers $n=1$, when the empty product is one and its weight is two.

Use Gaussian quadrature: choose the $n$ nodes as the roots of the degree-$n$ Legendre polynomial, which are distinct and inside $(-1,1)$. Retain the integrated Lagrange interpolation weights. With the standard normalization $P_n(1)=1$, they can be writtenThe orthogonality of the Legendre polynomial against all lower-degree polynomials makes this quadrature exact up to degree $2n-1$, twice the arbitrary-node degree apart from the endpoint count. This is the Gauss–Legendre choice of Gaussian quadrature nodes and weights.

For the unit sphere, project from its north pole $N=(0,0,1)$ onto the equatorial plane, identified with the complex plane. The line through $N$ and $(X,Y,Z)$ meets the plane at the stereographic projectionThe north pole is omitted from the plane chart; adding its image infinity gives the Riemann sphere.

For a point whose image and antipodal image are finite, stereographic projection of $(-X,-Y,-Z)$ gives $v=-(X+iY)/(1+Z)$. Thereforeusing $X^2+Y^2+Z^2=1$. Conversely $u\overline{v}=-1$ implies $v=-1/\overline{u}$. Substituting this into the inverse stereographic projection changes the signs of all three coordinates, proving the converse. Thus finite chart images correspond to antipodes exactly when $u\overline{v}=-1$. On the extended chart the exceptional antipodal pair is $0,\infty$, for which the displayed ordinary complex product is not defined.

Each test divides the current candidate set into a tested subset and its complement: failure places the defective item inside the subset, whereas success places it outside. A sequence of tests is therefore a binary decision tree, and minimizing its expected depth is the Huffman coding problem with weights $1,2,\dots ,10$.

Combine the smallest two current weights repeatedly. One choice of merges is $1+2=3$, $3+3=6$, $4+5=9$, $6+6=12$, $7+8=15$, $9+9=18$, $10+12=22$, $15+18=33$, $22+33=55$. It gives this explicit prefix code:At any node, test the candidate items whose next code digit is one. Assign failure to digit one and success to digit zero, and repeat until only a single codeword remains. This specifies every test, including the first subset $\{4,5,7,8,9\}$. Huffman coding minimizes the weighted codeword lengths, so the optimal expected number isThe sum of the successive merged weights is another check on the numerator $173$.

There is a genuinely different optimal procedure. Exchange the codewords assigned to items three and four. Both have code length four, so each item's length, and hence the expected number of tests $173/55$, remains unchanged. The first tested subset now contains item three instead of item four, so this changes the tested groups rather than merely reversing the names of the two test outcomes. The new prefix code still identifies every item uniquely and retains the minimum Huffman coding expectation.

The procedure in part (i) sometimes needs five tests, for items one or two. A binary decision tree of height $N$ has at most $2^N$ leaves, so distinguishing ten possibilities requires $N\ge \lceil {\log }_{2}10\rceil =4$.

A prefix code attaining this worst-case bound isUse the same subset-testing rule. The minimum worst-case number is four, so the expected-optimal procedure is not worst-case optimal. This four-test procedure has expectation $175/55$, illustrating the small cost of imposing the smaller maximum depth.

The logit link gives ${\mu }_i=e^{\beta x_i}/(1+e^{\beta x_i})$. Independence in the Bernoulli logistic-regression model therefore gives the log-likelihoodDifferentiate using $d{\mu }_i/d\beta =x_i{\mu }_i(1-{\mu }_i)$:The maximum-likelihood estimator, if finite, solves the single score equation ${\sum }_i{x}_i(y_i-{\hat{\mu }}_i)=0$. If at least one $x_i$ is nonzero, the log likelihood is strictly concave at finite $\beta$, so any root is the unique maximizer.

Use Newton method, equivalently one-parameter iteratively reweighted fitting:A damped step or a bracketed score solver is useful if a full step overshoots. The finite maximum-likelihood estimate in a one-parameter logistic model requires the score limit at minus infinity to be positive and its limit at plus infinity to be negative. Perfect sign separation of the observations can instead send the estimate to an infinite coefficient; if every $x_i=0$, the coefficient is unidentifiable. These possibilities should be checked before claiming convergence to a finite estimate.

In the squared-denominator population map, $r$ is the low-density per-generation multiplication factor, while $b$ controls crowding: $1/b$ is the characteristic population scale. The nonzero fixed point for $r>1$ and its multiplier areSince this multiplier lies strictly between minus one and one, $N_{\ast }$ is locally asymptotically stable. This holds for every finite $r>1$, even when the map is locally decreasing at its fixed point.

For the post-initial invariant interval for a squared-denominator population map, put $M=r/(4b)$ and $L=4r^2/[b(r+4{)}^2]$. The derivative $F^{\prime }(N)=r(1-bN)/(1+bN{)}^3$ shows that the global maximum is $M$ at $N=1/b$. The first two iterates of the supplied initial condition are consequentlyFor $r>4$, $1/b<L\le M$. Hence the map decreases throughout $[L,M]$, with minimum $F(M)=L$ there, and its global maximum bound ensures $F(L)\le M$. Thus $F([L,M])\subseteq [L,M]$, and induction provesBoth endpoints are attained at $t=2,3$. The lower bound printed without a time qualification is false at $t=1$, because the given value $N_1=1/b$ is strictly below $L$ when $r>4$. The invariant bounds apply after that initial step, not to it.

The cobweb plot below uses $n=bN$ and $r=9$. The first vertical move reaches the maximum, the next reaches its image, and subsequent vertical/horizontal steps remain in the invariant interval and approach the stable fixed point.

A Lyapunov function near an equilibrium is a continuously differentiable function with $V(0)=0$, $V(x)>0$ for nonzero nearby $x$, and $\dot{V}=\nabla V\cdot f\le 0$ along trajectories there. Strict negativity away from the equilibrium gives local asymptotic stability. Lyapunov stability itself means that every prescribed small neighborhood contains a smaller neighborhood whose forward trajectories never leave the prescribed one.

For the proposed quadratic form, direct differentiation givesWhen $\beta >1$, the quadratic part is negative definite, so it dominates the cubic remainder in a sufficiently small ball; $V$ is then a strict Lyapunov function. If $0<\beta <1$, take $x=y$ to make the leading derivative positive. At $\beta =1$, that same line gives $\dot{V}=-4x^3$, positive on its negative half. Values $\beta \le 0$ fail positive definiteness of $V$. ThereforeFor $\beta =2$ the full derivative factors, with no small-amplitude truncation:Every closed sublevel set $V\le c<1$ lies in $x>-1$, is forward invariant, and has strictly decreasing $V$ away from the origin. Compactness and the Lyapunov stability argument therefore show that the ellipse $x^2+2y^2<1$ belongs to the origin's basin of attraction. Boundary points with $V=1$ other than $(-1,0)$ also have negative derivative and enter the ellipse. The exception $(-1,0)$ is another fixed point, so the largest such sublevel ellipse cannot be included wholesale in the basin. This is a basin estimate from a Lyapunov sublevel set, not a claim that no additional points outside the ellipse converge to the origin.

Normalize the second-order equation as $y^{\prime \prime }+P(z)y^{\prime }+Q(z)y=0$, with $P,Q$ holomorphic at all finite nonzero points. The regular singular point criterion for a second-order equation at zero says that $zP(z)$ and $z^{2}Q(z)$ extend holomorphically across zero.

To impose the condition at infinity, set $w=1/z$ and $Y(w)=y(1/w)$. Since $y^{\prime }=-w^2{Y}^{\prime }$ and $y^{\prime \prime }=w^4{Y}^{\prime \prime }+2w^3{Y}^{\prime }$, the transformed equation isRegular singularity at $w=0$ makes $2-P(1/w)/w$ and $Q(1/w)/w^2$ bounded and holomorphic there. Equivalently $zP(z)$ and $z^{2}Q(z)$ are bounded at infinity. They are entire functions by the zero-endpoint condition, so Liouville's theorem makes both constants. The Euler-Cauchy classification from two regular singular points is thereforeConversely these equations have ordinary coefficients everywhere on ${\mathbb{C}}^{\ast }$ and meet both regular-singularity bounds. If “regular singular” is required to exclude an ordinary point, omit $(A,B)=(0,0)$, which makes zero ordinary, and $(2,0)$, which makes infinity ordinary. Under the common “at worst regular singular” convention these two cases are included. Multiplication by a nonvanishing coefficient does not change the normalized equation or this classification.

Assume the velocity-to-momentum Legendre map is locally invertible. Differentiate the Hamiltonian while regarding $q,p,t$ as independent:The velocity variations cancel because $p_i=\partial L/\partial {\dot{q}}_i$. Combining the remaining coefficients with the Euler-Lagrange equations gives Hamilton's equationsAn ignorable coordinate does not occur explicitly in the Lagrangian, so its conjugate momentum is conserved. For the spherical motion, $\varphi$ is ignorable and the Hamiltonian has no explicit time dependence. The two constants are $p_{\varphi }$ and $H$.

The polar Hamilton equations areA constant polar angle therefore requires $p_{\theta }=0$ and vanishing of the second right-hand side. For $0<\theta <\pi$ with $\cos \theta \ne 0$, this isThe expression must be nonnegative to represent a real momentum. Once it holds, $\varphi$ advances uniformly at $p_{\varphi }/(m{a}^2{\sin }^2\theta )$, so it is also sufficient with those initial data. At the equator the undivided equation instead requires $V^{\prime }(\pi /2)=0$, with any $p_{\varphi }$; dividing by cosine would wrongly discard this special case. The polar coordinate chart itself excludes the poles.

Assume dilute nondegenerate nonrelativistic particles, a common temperature, chemical equilibrium, charge neutrality $n_p=n_e$, and photons with zero chemical potential. The reaction balance gives ${\mu }_p+{\mu }_e={\mu }_H$. Dividing the two charged-species equilibrium densities by the neutral density cancels their chemical-potential factors and leavesFor ground-state hydrogen, $g_p=g_e=2$ and $g_H=4$, and $m_H\simeq m_p$ in the thermal prefactor. The rest-mass difference is $I/c^2$. These approximations give the Saha ionization equationExcited levels or different degeneracy conventions would change the prefactor; the stated assumptions give the printed normalization.

Write the right side as $S(T)$. Since $n_e=X_e{n}_B$ and $n_H=(1-X_e)n_B$, the hydrogen ionization fraction obeys $X_e^2/(1-X_e)=S(T)/n_B$. With $n_B=\eta n_{\gamma }$, the given blackbody photon density then yieldsThere are vastly more photons than baryons. Even when the typical photon energy is below the ionization energy, the high-energy tail can contain enough ionizing photons to keep nearly every baryon ionized. Neutral hydrogen forms only when that tail becomes sufficiently depleted relative to the very small baryon-to-photon ratio. This entropy/number-density effect explains why cosmological recombination occurs at a temperature far below $I$, rather than simply when $kT$ first falls below the binding energy. The Saha ionization equation describes the equilibrium estimate; late kinetic freeze-out is a separate limitation of that approximation.

A frieze group is a discrete subgroup of Euclidean isometries whose translation subgroup is generated by one nonzero vector and has finite index. A plane crystallographic group is a discrete subgroup of Euclidean isometries with a rank-two translation lattice of finite index; equivalently its action has a compact fundamental region.

Here are three frieze groups, with explicit generators. The translation $T(x,y)=(x+1,y)$ alone gives $\mathbb{Z}$. Adding the vertical reflection in mathematics $S(x,y)=(-x,y)$ gives $\mathbb{Z}⋊C_2$, the infinite dihedral group, since $STS=T^{-1}$. Instead adding the horizontal reflection in mathematics $H(x,y)=(x,-y)$ gives $\mathbb{Z}\times C_2$, since $HT=TH$. Their translation parts are exactly $⟨T⟩$ and their point parts have respectively one, two and two elements.

For plane crystallographic groups, let $T_1(x,y)=(x+1,y)$ and $T_2(x,y)=(x,y+1)$. These generate ${\mathbb{Z}}^2$. Adding the half-turn $R_2(x,y)=(-x,-y)$ gives ${\mathbb{Z}}^2⋊C_2$, with inversion on both translation generators. Adding the quarter-turn $R_4(x,y)=(-y,x)$ gives ${\mathbb{Z}}^2⋊C_4$, with $R_4{T}_1{R}_4^{-1}=T_2$ and $R_4{T}_2{R}_4^{-1}=T_1^{-1}$. These are the translation, half-turn and square-rotation wallpaper groups. Integer translation vectors and a finite point part make each group a discrete subgroup; the unit square meets every orbit, establishing a cocompact group action.

For the final claim, suppose a Euclidean isometry $R$ has order five. An orientation-reversing planar isometry has finite order only when it is a reflection in mathematics, so $R$ is a rotation through $\theta =2\pi j/5$, $j=1,2,3,4$, about some centre. Write $A$ for its linear rotation part. If $t_v\in G$ is a nonzero translation, conjugation gives $R{t}_v{R}^{-1}=t_{Av}$. Thus $G$ contains translations by $v$ and by $(A+A^{-1})v=cv$, where $c=2\cos \theta$.

For a primitive fifth root $\zeta$, dividing $1+\zeta +{\zeta }^2+{\zeta }^3+{\zeta }^4=0$ by ${\zeta }^2$ gives $c^2+c-1=0$. Hence $c$ is irrational. The pigeonhole principle, applied to $N+1$ fractional parts of $0,c,\dots ,Nc$ in $N$ equal intervals, gives integers $m,n$ with $0<|nc-m|\le 1/N$. Consequently $G$ contains nonidentity translations by $(nc-m)v$ tending to the identity. This contradicts the discrete subgroup hypothesis. There is no element of order five. This argument needs only the given nonzero translation, not a rank-two lattice.

For probability distributions $p,q$ with positive entries, Gibbs inequality iswith equality exactly when $p=q$. Indeed, $\log x\le x-1$, with equality only at $x=1$, givesThis also proves the equality condition. With zero entries the same Kullback-Leibler divergence statement holds using $0\log (0/q)=0$ and $p\log (p/0)=+\infty$ for $p>0$, or by restricting to the support and taking limits.

Let $J_1,J_2,\dots$ be independent rolls with the specified probability distribution, and let $F_m$ be the fortune after $m$ games. Its multiplicative evolution givesby the strong law of large numbers. The summands have finitely many finite values, so its hypotheses hold. For any $\epsilon >0$, the probability that $f{e}^{m(g-\epsilon )}\le F_m\le f{e}^{m(g+\epsilon )}$ tends to one. Thus maximizing $g(a)$ maximizes the typical exponential growth rate, the objective of log-optimal multiplicative betting. Maximizing expected fortune would be a different objective and would not control the typical repeated-game outcome.

By Gibbs inequality,with equality exactly when $\boxed{a_j=p_j}$. Put $q_j=u_j/U$, a probability distribution. The optimal log-optimal multiplicative betting rate isFor $U<1$ this is strictly positive by Gibbs inequality; taking $0<\epsilon <g_{\ast }$ in the preceding strong law of large numbers bound proves growth with probability tending to one.

For $U>1$ the casino can set $u_j=U{p}_j$. Every optimal return multiplier is then exactly $1/U$, so the fortune decreases deterministically as $f{U}^{-m}$. More generally $g_{\ast }=-\log U<0$ for that choice. An arbitrary choice with $U>1$ need not cause decline. For example, take $p_1=p_2=1/2$, $u_1=0.01$, $u_2=1.99$. Then $U=2$ but $g_{\ast }=(1/2)\log [0.25/(0.01\cdot 1.99)]>0$. For any fixed positive $p$, making one $u_j$ sufficiently small while preserving $U$ also makes the optimal rate positive.

The first fit is grouped-binomial logistic regression: independently, $Y_i\sim \mathrm{Bin}(N_i,{\pi }_i)$, with the observed group sizes $N_i$ andThe reference group is under 50 with a nonmalignant initial tumour. The weights specify binomial numbers of trials, not six equally weighted individual observations. There is no age-by-malignancy interaction. Each age coefficient compares that age group with the reference age at fixed malignancy; $\exp {\beta }_3$ is the common malignancy odds ratio.

The maximum-likelihood estimates are obtained by maximizing the binomial likelihood. The reported standard errors come from the inverse fitted Fisher information. Each displayed Wald test tests a coefficient equal to zero, using $z=\hat{\beta }/\mathrm{se}(\hat{\beta })$ and the approximate standard normal distribution; its two-sided probability is $2\Phi (-|z|)$. At the 5% level the middle age coefficient and the malignancy coefficient are significant, with negative signs; the oldest age coefficient is not, although its 9.17% probability is weaker evidence in the same direction. The oldest group has only 19 observations and its larger standard error does not establish absence of an age effect. The intercept tests reference log-odds zero, equivalently reference survival probability $1/2$, rather than an age contrast. The reference fitted probability is about $0.888$; the fitted malignancy odds ratio is about $0.481$.

The binomial deviance is twice the saturated-minus-fitted log-likelihood. The null fit has one parameter, hence $6-1=5$ residual degrees of freedom; the first fit has four parameters, hence $6-4=2$. The improvement $12.65585-0.49409=12.16176$ is an approximate likelihood-ratio test on three degrees of freedom, with probability about $0.0069$. The residual deviance $0.49409$, compared with ${\chi }_2^2$, gives about $0.781$, so there is no evidence of lack of fit. These are asymptotic comparisons, especially approximate for the small oldest strata. The Akaike information criterion is $-2\ell +2p$, here with $p=4$.

Pooling the two older age groups gives a grouped-binomial logistic regression with a common coefficient for age at least 50 and three parameters in total. The similar older-age estimates and the sparse oldest group motivate examining this restriction, but the significance of either coefficient separately is not a test of their equality. The actual analysis of deviance for pooling compares the nested fits: the deviance increases by only $0.784-0.49409\simeq 0.28991$ for one lost parameter, giving a ${\chi }_1^2$ probability about $0.590$. The pooled model also has smaller Akaike information criterion, $28.723$ rather than $30.433$. Prefer the pooled model for its simpler adequate fit. Its common age and malignancy coefficients are negative and significant at 5% in the reported Wald tests.

There is a literal parenthesis error in the printed final R fragment: the first sum is not closed before subtracting the second sum. As printed, the expression is incomplete. Closing that sum gives twice the saturated-minus-fitted log-likelihood, including the binomial constants which cancel. Its intended final value is therefore the second fit's binomial deviance, $\boxed{0.784\text{ approximately}}$.

Parameterize the second contour by $\zeta =-is$, $s\ge 0$. ThenThe exponential decays when $\mathrm{Im}z>0$, uniformly on compact subsets of that half-plane. Differentiation under the integral there proves holomorphy. Thus the maximal open sector of convergence and holomorphy in this representation is $\boxed{\alpha =0,\beta =\pi }$. The boundary integrals themselves can converge, but that does not enlarge this open analytic sector.

For $0<\arg z<\pi /2$, rotate the original contour clockwise through the fourth quadrant. On a large quarter-circle the integrand is $O(R^{-3})$ times a decaying exponential, so the arc integral tends to zero. The only enclosed pole is ${\zeta }_0=e^{-i\pi /3}$, and its residue is $e^{-2z{\zeta }_0}/(3{\zeta }_0^2)$. The clockwise orientation gives, by the residue theorem,Consequently the desired analytic continuation for $\pi /2\le \arg z<\pi$ isBoth terms are holomorphic in the upper half-plane and the expression agrees with the original function in the overlap, so it is an analytic continuation. The residue term is essential: the pole lies between the two rays.

Multiply the Friedmann equation by $a^2$ and differentiate:Insert the cosmological continuity equation to obtainOn a nonstatic branch divide by $2a\dot{a}$; continuity extends the result across isolated turning points. The resulting Friedmann acceleration equation isAn everywhere static branch needs the independent spatial Einstein field equations: the two differentiated constraints alone cannot determine the pressure when $\dot{a}\equiv 0$. This is the qualification to deriving the acceleration equation solely by division.

For constant equation-of-state parameter $w$, the cosmological continuity equation integrates to $\rho ={\rho }_0{a}^{-3(1+w)}$ using today's normalization. In conformal time, $\mathcal{H}=a^{\prime }/a=\dot{a}$, so the Friedmann equation becomesSince ${\mathcal{H}}^{\prime }=a\ddot{a}$, the Friedmann acceleration equation givesFor $k{c}^2=1$, put $q=(1+3w)/2$. When $q\ne 0$, integration gives $\mathcal{H}=\cot (q(\tau -{\tau }_0))$. Integrating $a^{\prime }/a=\mathcal{H}$ then yields the closed constant-equation-of-state Friedmann scale factorChoose a connected interval with positive sine; the origin of conformal time can absorb ${\tau }_0$. For $w>-1/3$ this is the expansion and recollapse branch between consecutive zeros of the sine. Negative $q$ instead gives the corresponding minimum-radius branch on its positive-sine interval. The printed power formula excludes $w=-1/3$: in that exceptional case $\mathcal{H}=H_0$ is constant and $a=A{e}^{H_0\tau }$, with $H_0^2+1=8\pi G{\rho }_0/3$. A real solution requires the latter constant to be at least one; equality permits a static solution.

For pressure-free matter, $w=0$, so $\beta =1/2$. Set the big-bang origins to zero. The closed matter-dominated Friedmann solution follows by ${\sin }^2(\beta \tau )=(1-\cos 2\beta \tau )/2$ and integrating $dt=ad\tau$:The entire cycle is $0\le 2\beta \tau \le 2\pi$; maximum expansion has $a=\alpha$ at $2\beta \tau =\pi$, and the big crunch occurs at $t=\alpha \pi /(2\beta )$.

Call a set function $f$ with ordinal domain $\gamma$ good if $f(\xi )=G(\xi ,\mathrm{ran}(f{|}_{\xi }))$ for every $\xi <\gamma$. Any two good functions agree on their common domain: otherwise their first disagreement has identical earlier ranges and hence identical values under $G$. This is transfinite induction, not an assumption of the desired recursion.

Good functions exist with every ordinal domain. At a successor stage extend the unique previous function by its prescribed value under $G$. At a limit stage, Axiom schema of replacement collects the unique good functions on all smaller domains into a set, and their compatible union is a good function on the limit domain. Each earlier range is a set, so $G$ is applied only to sets. Transfinite induction now establishes existence at all stages. Define $F(\alpha )$ to be the value at $\alpha$ of the unique good function on $\alpha +1$. This is a definable class function because goodness and the uniqueness assertion are formulas in the defining formula for $G$. Compatibility gives

An initial ordinal is an ordinal not bijective with any smaller ordinal. It is the canonical ordinal representative of a well-orderable cardinal, so cardinal arithmetic can be defined by taking the initial ordinal equinumerous with a disjoint union, Cartesian product or function set. In the usual setting with the axiom of choice, every cardinal has such a representative. Hartogs theorem says that for every set $A$ there is an ordinal $h(A)$ which does not inject into $A$, and there is a least such ordinal. For an initial ordinal $\kappa$ it is the next larger initial ordinal: every smaller ordinal injects into $\kappa$, and if $h(\kappa )$ were equinumerous with a smaller ordinal it too would inject into $\kappa$.

Use the recursion just proved to set ${\omega }_0=\omega$, ${\omega }_{\beta +1}=h({\omega }_{\beta })$ and ${\omega }_{\lambda }={\sup }_{\beta <\lambda }{\omega }_{\beta }$ for nonzero limit $\lambda$. These instructions use the earlier value set alone: at a successor it has a maximum, and at a limit its supremum is taken. They are therefore implemented by an appropriate definable $G$. The limit supremum is initial: if it were bijective with $\gamma$ below it, choose an earlier ${\omega }_{\beta }>\gamma$; then ${\omega }_{\beta }$ would inject into $\gamma$, contradicting initiality. The sequence is strictly increasing and continuous. There are no omitted infinite initial ordinals, since each successor chooses the least next one and each limit is the supremum; more formally, a least omitted initial ordinal cannot lie between successive terms, and the least term above it cannot be a limit term. Terms eventually exceed any prescribed ordinal, since a strictly increasing ordinal sequence satisfies ${\omega }_{\beta }\ge \beta$.

There is a fixed point of a normal ordinal function. Explicitly let ${\alpha }_0=0$, ${\alpha }_{n+1}={\omega }_{{\alpha }_n}$ and $\alpha ={\sup }_{n<\omega }{\alpha }_n$. The sequence is strictly increasing, by induction from $0<{\omega }_0$ and strict increase of the enumeration. It is cofinal in the limit $\alpha$, so continuity gives

Hall's marriage theorem states that a finite bipartite graph with parts $A,B$ has a matching in a graph saturating $A$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq A$. Necessity follows because the matched neighbours of $S$ are distinct.

For sufficiency use induction on $|A|$. The empty case is immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, the induced graph on $S,N(S)$ satisfies Hall's condition and has a saturating matching in a graph by induction. The remaining graph on $A\setminus S,B\setminus N(S)$ also satisfies it: for $T\subseteq A\setminus S$,Apply induction again and unite the two matchings in a graph. If there is no such tight proper subset, every nonempty proper $S$ has $|N(S)|\ge |S|+1$. Choose a vertex $a$ and a neighbour $b$, which exists by Hall's condition. Delete both. Every remaining subset loses at most one neighbour and still satisfies Hall's condition. Induction supplies a matching in a graph of the remainder; add $ab$. For $|A|=1$ this last step directly proves the assertion.

Let $A,B$ be the two parts of the bipartite graph. Counting edges gives $k|A|=k|B|$, hence $|A|=|B|=n/2$. For $S\subseteq A$, the $k|S|$ edges incident to $S$ all end in $N(S)$, whose vertices have total capacity $k|N(S)|$. Thus $|N(S)|\ge |S|$. Hall's marriage theorem gives a perfect matching, and no matching in a graph can have more than $n/2$ edges. The matching number is $\boxed{n/2}$.

Take a maximal matching in a graph with $m$ edges and let $S$ be its $2m$ endpoints. Maximality makes its complement an independent set, since an edge wholly outside $S$ could be added. Every vertex outside $S$ therefore sends all its $k$ edges into $S$, giving $k(n-2m)$ crossing edges. Every vertex in $S$ already uses at least one incident edge inside $S$, its matched edge, so it sends at most $k-1$ outside. HenceThe maximum matching in a graph is at least this large. For $k=2$, take any disjoint union of $r$ triangles. It is 2-regular, has $n=3r$ vertices and matching number $r=n/3$, since each triangle contributes exactly one edge. As $r$ varies this gives infinitely many equality examples.