STEP 2 Mock Paper 1

(i)

The three denominators $x$, $y$ and $x+y$ are all positive, so $xy(x+y)$ is a common denominator and is positive. Putting the difference over it, $$\frac{p^2}{x}+\frac{q^2}{y}-\frac{(p+q)^2}{x+y}=\frac{p^2y(x+y)+q^2x(x+y)-(p+q)^2xy}{xy(x+y)}.$$ Expanding the numerator, $$p^2xy+p^2y^2+q^2x^2+q^2xy-(p^2+2pq+q^2)xy=p^2y^2-2pq\,xy+q^2x^2=(py-qx)^2 .$$ So, for all real $p$ and $q$ and all positive $x$ and $y$, $$\frac{p^2}{x}+\frac{q^2}{y}-\frac{(p+q)^2}{x+y}=\frac{(py-qx)^2}{xy(x+y)}. \qquad (\star)$$

Two things are worth saying about how this was obtained, because both are places where marks are lost. First, $(\star)$ is an identity: it holds whenever the denominators are non-zero, and no inequality has been used to reach it. Replace with: Second, the two hypotheses on $x$ and $y$ do different jobs and are used at different points. Forming the common denominator needs only that $x$, $y$ and $x+y$ are non-zero, which is why $(\star)$ is an identity rather than an inequality; the sign of $x$ and $y$ is used only now, to say that $xy(x+y) \gt 0$, and $(py-qx)^2 \ge 0$ because a real square is never negative, so the right-hand side of $(\star)$ is at least $0$.: since $x \gt 0$ and $y \gt 0$ we have $xy(x+y) \gt 0$, and $(py-qx)^2 \ge 0$ because a real square is never negative, so the right-hand side of $(\star)$ is at least $0$. Hence $$\frac{p^2}{x}+\frac{q^2}{y}\ \ge\ \frac{(p+q)^2}{x+y}.$$ The alternative route, multiplying the inequality through by $xy(x+y)$ from the start, reaches the same place but only if the solution states that this quantity is positive, Replace with: since multiplying an inequality by a negative quantity reverses it, so a solution that multiplies through by $xy(x+y)$ without first establishing that this quantity is positive has established neither direction..

Equality holds exactly when the right-hand side of $(\star)$ is zero, and since its denominator is positive that happens exactly when $(py-qx)^2=0$, that is exactly when $py=qx$. As $x$ and $y$ are positive this may be written $\dfrac{p}{x}=\dfrac{q}{y}$.

(ii)

Write $P_k=p_1+\cdots+p_k$ and $X_k=x_1+\cdots+x_k$. Every $X_k$ is a sum of positive numbers and so is positive, which is what allows part (i) to be applied to it later.

Let $S(n)$ be the statement: for all real numbers $p_1,\dots,p_n$ and all positive real numbers $x_1,\dots,x_n$, $$\sum_{i=1}^{n}\frac{p_i^2}{x_i}\ \ge\ \frac{P_n^2}{X_n},$$ with equality if and only if $\dfrac{p_1}{x_1}=\cdots=\dfrac{p_n}{x_n}$.

The quantifiers matter and are a choice worth making explicit: $S(n)$ is a statement about every admissible list of length $n$, not about one fixed list. The inductive step below applies $S(n)$ to the first $n$ entries of a longer list, which is a different list from the one being studied, so a proposition stated for a fixed list would not support the step.

Base case. $S(2)$ is exactly part (i), with $(p,q,x,y)=(p_1,p_2,x_1,x_2)$, and the equality condition $p_1x_2=p_2x_1$ is the same as $\dfrac{p_1}{x_1}=\dfrac{p_2}{x_2}$ because $x_1$ and $x_2$ are positive. So $S(2)$ is true.

(The induction is started at $n=2$ rather than $n=1$ deliberately. At $n=1$ the inequality is an identity and the chain of ratios has a single entry, so the equality criterion asserts nothing there.)

Inductive step. Suppose $S(n)$ holds for some $n \ge 2$. Let $p_1,\dots,p_{n+1}$ be real and $x_1,\dots,x_{n+1}$ positive. Split off the last term: this is the one free choice in the step, and it is made because part (i) merges exactly two fractions, so the sum must first be reduced to two fractions. $$\sum_{i=1}^{n+1}\frac{p_i^2}{x_i}=\left(\sum_{i=1}^{n}\frac{p_i^2}{x_i}\right)+\frac{p_{n+1}^2}{x_{n+1}}\ \overset{(1)}{\ge}\ \frac{P_n^2}{X_n}+\frac{p_{n+1}^2}{x_{n+1}}\ \overset{(2)}{\ge}\ \frac{(P_n+p_{n+1})^2}{X_n+x_{n+1}}=\frac{P_{n+1}^2}{X_{n+1}}.$$ Step (1) is $S(n)$ applied to $p_1,\dots,p_n$ and $x_1,\dots,x_n$. Step (2) is part (i) applied with $p=P_n$, $q=p_{n+1}$, $x=X_n$ and $y=x_{n+1}$; this is legitimate because $X_n \gt 0$ and $x_{n+1} \gt 0$. That proves the inequality in $S(n+1)$.

For the equality criterion, note first that in a chain $A \ge B \ge C$ the statement $A=C$ forces $A=B=C$, since $A=C$ gives $C \ge B \ge C$. Insert after the chain remark: equality at (1) says $\left(\sum_{i=1}^{n}\frac{p_i^2}{x_i}\right)+\frac{p_{n+1}^2}{x_{n+1}}=\frac{P_n^2}{X_n}+\frac{p_{n+1}^2}{x_{n+1}}$, and since $x_{n+1} \gt 0$ the common term $\frac{p_{n+1}^2}{x_{n+1}}$ is a finite real and may be subtracted from both sides, giving $\sum_{i=1}^{n}\frac{p_i^2}{x_i}=\frac{P_n^2}{X_n}$, which is exactly equality in $S(n)$.

Suppose $\dfrac{p_1}{x_1}=\cdots=\dfrac{p_{n+1}}{x_{n+1}}=k$. Then $p_i=kx_i$ for every $i$, so $P_n=kX_n$. The first $n$ ratios are equal, so $S(n)$ gives equality at (1). And $P_n\,x_{n+1}=kX_nx_{n+1}=p_{n+1}X_n$, which is the equality condition of part (i) for step (2). So equality holds throughout.

Conversely, suppose equality holds. Equality at (1) forces, by the equality criterion in $S(n)$, that $\dfrac{p_1}{x_1}=\cdots=\dfrac{p_n}{x_n}=k$ for some $k$; then $P_n=kX_n$, and since $X_n \gt 0$ this says $\dfrac{P_n}{X_n}=k$. Equality at (2) forces, by part (i), $P_n\,x_{n+1}=p_{n+1}X_n$, that is $\dfrac{p_{n+1}}{x_{n+1}}=\dfrac{P_n}{X_n}=k$. Hence all $n+1$ ratios equal $k$. This converse direction is the delicate half: it is not enough to observe that equal ratios give equality, because the criterion claims the two conditions are the same condition.

Therefore $S(n)$ implies $S(n+1)$, and since $S(2)$ holds, $S(n)$ holds for every integer $n \ge 2$ by induction.

(iii)

Part (ii) applies to any sum whose terms are a square divided by a positive number, and here the terms are already in that shape. The choice to be made is which quantities to call $p_i$ and which to call $x_i$, and the choice is guided by wanting the right-hand side of (ii) to simplify. Take $p_i=a_i$ and $x_i=a_{i+1}$ for $i=1,\dots,n$, with $a_{n+1}$ meaning $a_1$; every $x_i$ is positive. The reason this choice is the useful one is that $x_1,\dots,x_n$ is a rearrangement of $a_1,\dots,a_n$, so $$x_1+\cdots+x_n=a_2+a_3+\cdots+a_n+a_1=a_1+a_2+\cdots+a_n=p_1+\cdots+p_n .$$ Part (ii) therefore gives $$\sum_{i=1}^{n}\frac{a_i^2}{a_{i+1}}\ \ge\ \frac{(a_1+\cdots+a_n)^2}{a_1+\cdots+a_n}=a_1+a_2+\cdots+a_n,$$ the cancellation being legitimate because $a_1+\cdots+a_n \gt 0$.

By the equality criterion in (ii), equality holds if and only if $$\frac{a_1}{a_2}=\frac{a_2}{a_3}=\cdots=\frac{a_n}{a_1}.$$ Call this common value $k$; it is positive, being a quotient of positive numbers. It is tempting to say at once that all the $a_i$ are equal, but that does not follow from the ratios being equal: a geometric progression $a_i=a_1t^{\,i-1}$ makes $\dfrac{a_1}{a_2}=\cdots=\dfrac{a_{n-1}}{a_n}$ for any $t \gt 0$. What rules it out is the last ratio, the one that closes the cycle. Multiplying all $n$ equal fractions together, the numerators are $a_1a_2\cdots a_n$ and the denominators are the same $n$ numbers in a different order, so the product is $1$; on the other hand the product is $k^n$. Hence $k^n=1$. Since $k \gt 0$ and $t \mapsto t^n$ is strictly increasing on the positive reals, $k=1$ is the only positive solution, so $k=1$ and therefore $a_1=a_2=\cdots=a_n$.

Conversely, if all the $a_i$ are equal then both sides equal $na_1$. So equality holds precisely when $a_1=a_2=\cdots=a_n$.

(iv)

Since $n \ge 2$ and every $a_j$ is positive, $S-a_i=\sum_{j \ne i}a_j$ is a sum of at least one positive number, so $S-a_i \gt 0$ and every term is defined and positive.

The construction. Part (ii) needs each term written as a square over a positive number, and $\dfrac{a_i}{S-a_i}$ is not in that form. Multiplying numerator and denominator by $a_i$ puts it in that form: $$\frac{a_i}{S-a_i}=\frac{a_i^2}{a_i(S-a_i)},$$ with $a_i(S-a_i) \gt 0$. This is a choice, and it is the step the question does not signpost. It is not the only way to force the terms into the required shape: one could instead write $\dfrac{a_i}{S-a_i}=\dfrac{(\sqrt{a_i})^2}{S-a_i}$, which is legal and gives $$\sum_{i=1}^{n}\frac{a_i}{S-a_i}\ \ge\ \frac{\left(\sqrt{a_1}+\cdots+\sqrt{a_n}\right)^2}{(n-1)S},$$ since $\sum_i (S-a_i)=nS-S=(n-1)S$. Replace the closing sentence of that paragraph with: dividing $\left(\sum\sqrt{a_i}\right)^2 \le nS$ by the positive quantity $(n-1)S$ gives $\frac{\left(\sum\sqrt{a_i}\right)^2}{(n-1)S} \le \frac{n}{n-1}$, with equality only when all the $a_i$ are equal. So the bound that route produces is never larger than the target, and no further argument from it can reach $\frac{n}{n-1}$: the square roots have to go in the denominator, not the numerator.: closing it would need $\left(\sum\sqrt{a_i}\right)^2 \ge nS$, whereas part (ii) applied with $p_i=\sqrt{a_i}$ and $x_i=1$ gives $\sum a_i \ge \frac{1}{n}\left(\sum \sqrt{a_i}\right)^2$, that is $\left(\sum\sqrt{a_i}\right)^2 \le nS$, the opposite inequality. So the square roots have to go in the denominator, not the numerator: the useful choice is the one that makes the numerators $a_i^2$, whose bases $a_i$ add up to $S$, the only quantity in the problem that is under control.

First application of (ii). With $p_i=a_i$ and $x_i=a_i(S-a_i) \gt 0$, $$\sum_{i=1}^{n}\frac{a_i}{S-a_i}=\sum_{i=1}^{n}\frac{a_i^2}{a_i(S-a_i)}\ \ge\ \frac{(a_1+\cdots+a_n)^2}{\sum_{i=1}^{n}a_i(S-a_i)}=\frac{S^2}{S^2-Q},\qquad Q:=a_1^2+\cdots+a_n^2,$$ because $\sum_i a_i(S-a_i)=S\sum_i a_i-\sum_i a_i^2=S^2-Q$. This denominator is positive: $S^2-Q=2\sum_{i \lt j}a_ia_j \gt 0$, since $n \ge 2$ and all the $a_i$ are positive. Without that remark the next step would be manipulating a fraction that might have a negative denominator.

What is now needed. The bound $\dfrac{S^2}{S^2-Q}$ is large when $Q$ is large, so to finish we need a lower bound for $Q$. Getting the direction right is the point at which a plausible piece of work proves nothing: an upper bound for $Q$ would give an upper bound for the fraction, which is useless here.

Second application of (ii). Apply part (ii) again, this time with $p_i=a_i$ and $x_i=1$, all of which are positive: $$Q=\sum_{i=1}^{n}\frac{a_i^2}{1}\ \ge\ \frac{(a_1+\cdots+a_n)^2}{1+1+\cdots+1}=\frac{S^2}{n}.$$ Hence $S^2-Q \le S^2-\dfrac{S^2}{n}=\dfrac{(n-1)S^2}{n}$. Both $S^2-Q$ and $\dfrac{(n-1)S^2}{n}$ are positive, so taking reciprocals reverses the inequality and $$\frac{S^2}{S^2-Q}\ \ge\ \frac{S^2}{(n-1)S^2/n}=\frac{n}{n-1}.$$ Combining the two displayed bounds, $$\frac{a_1}{S-a_1}+\frac{a_2}{S-a_2}+\cdots+\frac{a_n}{S-a_n}\ \ge\ \frac{n}{n-1}.$$

Equality. The argument is a chain of two inequalities, so equality in the conclusion forces equality in both. Equality in the first application of (ii) requires the ratios $\dfrac{p_i}{x_i}=\dfrac{a_i}{a_i(S-a_i)}=\dfrac{1}{S-a_i}$ to be equal for all $i$, that is all the $S-a_i$ equal, that is all the $a_i$ equal. Replace with: equality in the second link means $\frac{S^2}{S^2-Q}=\frac{n}{n-1}$, which cross-multiplies to $(n-1)S^2=n(S^2-Q)$ and so to $Q=\frac{S^2}{n}$, that is equality in the second application of part (ii), which requires the ratios $\frac{a_i}{1}$ to be equal. That is the same condition again, so the two links are tight together and neither adds a constraint the other does not. Conversely, if $a_1=\cdots=a_n=a \gt 0$ then $S=na$ and $S-a_i=(n-1)a$, so each term equals $\dfrac{1}{n-1}$ and the sum is exactly $\dfrac{n}{n-1}$. Hence equality holds precisely when $a_1=a_2=\cdots=a_n$.

Why squaring is the move, before any of it is done.

The increment in $x_{n+1}=x_n+\frac{1}{x_n}$ depends on $x_n$, so nothing telescopes as the recurrence stands and no closed form is available. Squaring is a choice, and this is what motivates it: squaring turns the increment into $2$ plus a term that is small once $x_n$ is large, so the increments of $x_n^{\,2}$ are almost constant. A sum of almost constant increments telescopes to something exact, and the whole question is then about the error term that survives.

(i)

Every term is defined and at least $1$. We have $x_1=1$. Suppose $x_n\geqslant1$ for some $n$. Then $x_n\neq0$, so $x_{n+1}$ is defined, and $\frac{1}{x_n}\gt0$, so $$x_{n+1}=x_n+\frac{1}{x_n}\gt x_n\geqslant1 .$$ By induction $x_n\geqslant1$ for every $n\geqslant1$, and the sequence is strictly increasing. This is the fact that every later part leans on, because it is what makes $\frac{1}{x_k^{\,2}}$ both defined and at most $1$.

The identity. Squaring the recurrence, for every $n\geqslant1$, $$x_{n+1}^{\,2}=\left(x_n+\frac{1}{x_n}\right)^{2}=x_n^{\,2}+2+\frac{1}{x_n^{\,2}} .$$ The cross term is $2x_n\cdot\frac{1}{x_n}=2$, a constant, and that is the entire reason the substitution is worth making.

So the increments of the sequence $x_1^{\,2},x_2^{\,2},\ldots$ are $2+\frac{1}{x_k^{\,2}}$, and a sum of consecutive increments telescopes. For $n\geqslant2$, $$x_n^{\,2}-x_1^{\,2}=\sum_{k=1}^{n-1}\left(x_{k+1}^{\,2}-x_k^{\,2}\right)=\sum_{k=1}^{n-1}\left(2+\frac{1}{x_k^{\,2}}\right)=2(n-1)+\sum_{k=1}^{n-1}\frac{1}{x_k^{\,2}} .$$ Since $x_1^{\,2}=1$, this rearranges to $$x_n^{\,2}=2n-1+\sum_{k=1}^{n-1}\frac{1}{x_k^{\,2}}\qquad(n\geqslant2),$$ as required. (An induction on $n$ does the same job: the base case $n=2$ reads $x_2^{\,2}=4=3+\frac{1}{x_1^{\,2}}$, and the inductive step is one application of the squared recurrence. Either is a complete proof; the telescope is shorter and shows where the terms come from.)

The bounds. Because $x_k\geqslant1$ for every $k$, each term satisfies $0\lt\frac{1}{x_k^{\,2}}\leqslant1$. The sum in the identity has $n-1$ such terms, so it lies strictly above $0$ and is at most $n-1$. Hence for $n\geqslant2$, $$2n-1\;\lt\;x_n^{\,2}\;\leqslant\;2n-1+(n-1)=3n-2 .$$ For $n=1$ the two bounds read $1\leqslant x_1^{\,2}\leqslant1$, which is true, so $2n-1\leqslant x_n^{\,2}\leqslant3n-2$ holds for every $n\geqslant1$. All three quantities are positive, so taking square roots preserves the inequalities and $$\sqrt{2n-1}\;\leqslant\;x_n\;\leqslant\;\sqrt{3n-2}\qquad(n\geqslant1).$$

(ii)

Rearranging the identity of part (i), for $n\geqslant2$, $$x_n^{\,2}-2n=\sum_{k=1}^{n-1}\frac{1}{x_k^{\,2}}\;-\;1 ,$$ so the claim to be proved is exactly that $\sum_{k=1}^{n-1}\frac{1}{x_k^{\,2}}$ is unbounded above.

Which of the two bounds from part (i) is the useful one is the decision in this part, and the instinctive choice is the wrong one. We want a lower bound on a sum of terms $\frac{1}{x_k^{\,2}}$, so we need an upper bound on each $x_k^{\,2}$. The lower bound $x_k^{\,2}\geqslant2k-1$ gives $\frac{1}{x_k^{\,2}}\leqslant\frac{1}{2k-1}$, which bounds the sum above and settles nothing here. It is the crude upper bound that does the work: $$x_k^{\,2}\leqslant3k-2\quad\Longrightarrow\quad\frac{1}{x_k^{\,2}}\geqslant\frac{1}{3k-2}\qquad(k\geqslant1).$$

The comparison sum is unbounded. Compare it with an integral, which is legitimate because $t\mapsto\frac{1}{3t-2}$ is positive and decreasing on $[1,\infty)$: for $k\geqslant1$ and $t\in[k,k+1]$ we have $3t-2\geqslant3k-2\gt0$, so $\frac{1}{3t-2}\leqslant\frac{1}{3k-2}$, and integrating that inequality over an interval of length $1$ gives $$\int_k^{k+1}\frac{\mathrm{d}t}{3t-2}\;\leqslant\;\frac{1}{3k-2} .$$ Adding these for $k=1,2,\ldots,n-1$, the integrals join up: $$\sum_{k=1}^{n-1}\frac{1}{3k-2}\;\geqslant\;\int_1^{n}\frac{\mathrm{d}t}{3t-2}=\left[\tfrac13\ln(3t-2)\right]_1^{n}=\tfrac13\ln(3n-2).$$

Putting the two steps together, for every $n\geqslant2$, $$x_n^{\,2}-2n\;\geqslant\;\tfrac13\ln(3n-2)-1 ,$$ and $\ln(3n-2)\to\infty$ as $n\to\infty$, so $x_n^{\,2}-2n\to\infty$.

Any proof that the comparison sum is unbounded is worth the same. Replace with: the usual alternative avoids integration altogether. Since $3k-2\leqslant3k$ we have $\frac{1}{3k-2}\geqslant\frac{1}{3k}$, so $\sum_{k=1}^{n-1}\frac{1}{3k-2}\geqslant\frac13\sum_{k=1}^{n-1}\frac{1}{k}$, and the harmonic sum is unbounded because its terms grouped into blocks running from $2^{\,j}+1$ to $2^{\,j+1}$ each total at least $\frac12$.

Two remarks are worth making. First, the result says the lower bound of part (i) is not merely unattained: $x_n^{\,2}$ eventually exceeds $2n+C$ for every constant $C$, so no bound of the form $x_n^{\,2}\leqslant2n+C$ can hold. Second, the growth is logarithmic and therefore invisible early on. Write the fifth term as $3.24482\ldots$, or give both as rounded values with no ellipsis: the first six terms are $1$, $2$, $2.5$, $2.9$, $3.2448$ and $3.5530$ to four decimal places., and $x_6^{\,2}-12$ is only about $0.62$, so a numerical experiment over the first few terms would suggest the opposite conclusion. That is a good reason to trust the argument rather than the table.

(iii)

Both sequences obey the same recurrence, so subtract the two recurrences rather than trying to control each sequence separately. Add to the inductive step, immediately after "Assume $S(n)$": in particular $y_n\geqslant1\gt0$, so $y_n\ne0$ and $y_{n+1}=y_n+\frac{1}{y_n}$ is defined, which is what allows the displayed identity to be applied at this $n$; the induction therefore establishes that every term of $y$ exists at the same time as it establishes the inequality. $$y_{n+1}-x_{n+1}=(y_n-x_n)+\left(\frac{1}{y_n}-\frac{1}{x_n}\right)=(y_n-x_n)-\frac{y_n-x_n}{x_ny_n}=(y_n-x_n)\left(1-\frac{1}{x_ny_n}\right).$$ This factorisation is the content of the part: at each step the difference is multiplied by a factor that is non-negative as soon as $x_ny_n\geqslant1$.

Now the induction. Let $S(n)$ be the statement $y_n\geqslant x_n\geqslant1$.

Base case. $y_1=c\geqslant1=x_1$, so $S(1)$ holds.

Inductive step. Assume $S(n)$. Then $x_ny_n\geqslant1\times1=1$, so $1-\frac{1}{x_ny_n}\geqslant0$, and since $y_n-x_n\geqslant0$ the displayed identity gives $y_{n+1}-x_{n+1}\geqslant0$. Also $x_{n+1}\geqslant1$ by part (i). So $S(n+1)$ holds, and by induction $y_n\geqslant x_n\geqslant1$ for every $n\geqslant1$.

Two things are worth flagging. If instead one argues that the comparison propagates because $t\mapsto t+\frac{1}{t}$ is increasing, the restriction to $t\geqslant1$ has to be stated and used: that function is decreasing on $(0,1)$, so the argument is simply false without it, and part (i) is what supplies the restriction. And the same identity shows $y_{n+1}-x_{n+1}\leqslant y_n-x_n$, so the difference never increases. That is not yet part (iv): a non-increasing sequence of non-negative numbers has a limit, but the limit need not be $0$, and closing that gap is the whole of the next part.

(iv)

The difference $y_n-x_n$ is awkward to estimate directly, and part (iii) has taken it as far as it goes. The choice that unlocks the part is to compare the squares instead, because part (i) computes squares exactly.

Nothing in the derivation in part (i) used the value of the first term until the last line: the squared recurrence and the telescope are the same for any starting value that keeps the terms at least $1$, and $y_n\geqslant1$ for every $n$ by part (iii). So the same telescope applied to $y$ gives, for $n\geqslant2$, $$y_n^{\,2}=c^{2}+2(n-1)+\sum_{k=1}^{n-1}\frac{1}{y_k^{\,2}} .$$ Writing the identity of part (i) in the same shape, $x_n^{\,2}=1+2(n-1)+\sum_{k=1}^{n-1}\frac{1}{x_k^{\,2}}$, and subtracting, the term $2(n-1)$ cancels: $$y_n^{\,2}-x_n^{\,2}=(c^{2}-1)+\sum_{k=1}^{n-1}\left(\frac{1}{y_k^{\,2}}-\frac{1}{x_k^{\,2}}\right).$$ By part (iii), $y_k\geqslant x_k\geqslant1\gt0$ for every $k$, so $\frac{1}{y_k^{\,2}}\leqslant\frac{1}{x_k^{\,2}}$ and every term of that sum is at most $0$. Combining with $y_n^{\,2}\geqslant x_n^{\,2}$, which is part (iii) again, $$0\;\leqslant\;y_n^{\,2}-x_n^{\,2}\;\leqslant\;c^{2}-1\qquad\text{for every }n\geqslant1 .$$ So the gap between the squares stays bounded, while by part (i) the squares themselves grow without bound. That is the tension that forces the difference to close, and the last step only makes it quantitative.

Since $y_n\geqslant x_n\geqslant1$, we have $y_n+x_n\geqslant2x_n\geqslant2\sqrt{2n-1}\gt0$, using the lower bound of part (i), so we may divide: $$0\;\leqslant\;y_n-x_n=\frac{y_n^{\,2}-x_n^{\,2}}{y_n+x_n}\;\leqslant\;\frac{c^{2}-1}{2\sqrt{2n-1}} .$$ The right-hand side tends to $0$ as $n\to\infty$, and the left-hand bound is $0$, so by the squeeze $y_n-x_n\to0$.

What the result does and does not say. When $c=1$ the two sequences are identical and every inequality above reads $0\leqslant0\leqslant0$, so the argument covers that case unchanged. Replace the first clause with: subtracting the squared recurrences gives $y_{n+1}^{\,2}-x_{n+1}^{\,2}=\left(y_n^{\,2}-x_n^{\,2}\right)\left(1-\frac{1}{x_n^{\,2}y_n^{\,2}}\right)$, so for $c\gt1$ every factor lies strictly between $0$ and $1$ and the sequences differ at every stage; moreover $\sum_k\frac{1}{x_k^{\,2}y_k^{\,2}}$ converges, because $x_k^{\,2}y_k^{\,2}\geqslant(2k-1)^{2}$, so the product of the factors converges to a positive limit and $y_n^{\,2}-x_n^{\,2}$ does not tend to $0$. The case $c=2$ makes this visible without the product, since then $y_1=2=x_2$., hence $y_n=x_{n+1}$ for every $n$, and then $y_n^{\,2}-x_n^{\,2}=x_{n+1}^{\,2}-x_n^{\,2}=2+\frac{1}{x_n^{\,2}}\to2$, while $y_n-x_n=x_{n+1}-x_n=\frac{1}{x_n}\to0$. So the conclusion really is a statement about a bounded quantity divided by an unbounded one, and not about the two sequences becoming equal: the sequence forgets its starting value in the limit while remembering it in every square.

Notation, and two small facts used more than once. Throughout, $f(x)=x^4+ax^3+bx^2+cx+d$ and $C$ is the curve $y=f(x)$. The question supplies two definitions and this solution uses them exactly as given: $y=mx+k$ touches $C$ at $x=u$ when $f(u)=mu+k$ and $f'(u)=m$, and $C$ is symmetric about $x=p$ when $f(p+t)=f(p-t)$ for every real $t$.

Fact 1 (a point of contact gives a repeated factor). If $P$ is a polynomial with $P(u)=0$ and $P'(u)=0$, then $(x-u)^2$ is a factor of $P(x)$. To see this, the factor theorem gives $P(x)=(x-u)Q(x)$ for some polynomial $Q$; differentiating by the product rule, $P'(x)=Q(x)+(x-u)Q'(x)$, so $P'(u)=Q(u)$. Hence $Q(u)=0$, and the factor theorem applied to $Q$ gives $Q(x)=(x-u)R(x)$, so $P(x)=(x-u)^2R(x)$.

Fact 2 (comparing coefficients). If two polynomials take the same value for every real number, their coefficients agree, because a non-zero polynomial of degree $n$ has at most $n$ real roots. This is what licenses reading coefficients off an identity that holds for all $x$, and it is used in (ii), (iii) and (iv).

(i)(a) For $f(x)=x^4-4x^3-2x^2+12x+4$, $$f'(x)=4x^3-12x^2-4x+12=4\big(x^2(x-3)-(x-3)\big)=4(x-3)(x^2-1)=4(x+1)(x-1)(x-3).$$ The grouping is a choice rather than a consequence, and what motivates it is that $x=3$ is visible as a root of $x^3-3x^2-x+3$; any correct factorisation does the same job. So the stationary points are at $x=-1$, $x=1$ and $x=3$, and $$f(-1)=1+4-2-12+4=-5,\qquad f(1)=1-4-2+12+4=11,\qquad f(3)=81-108-18+36+4=-5.$$ The stationary points are therefore $(-1,-5)$, $(1,11)$ and $(3,-5)$.

For their nature, use the sign of $f'$, which changes at each of the three simple roots: $f'\lt 0$ for $x\lt -1$, $f'\gt 0$ on $-1\lt x\lt 1$, $f'\lt 0$ on $1\lt x\lt 3$, and $f'\gt 0$ for $x\gt 3$. Hence $(-1,-5)$ and $(3,-5)$ are local minima and $(1,11)$ is a local maximum. (Equivalently $f''(x)=12x^2-24x-4$ gives $f''(-1)=32\gt 0$, $f''(1)=-16\lt 0$ and $f''(3)=32\gt 0$.)

(i)(b) At $x=-1$ and at $x=3$ we have $f(x)=-5$ and $f'(x)=0$. The line $y=-5$ is the line $y=mx+k$ with $m=0$ and $k=-5$, so the two conditions in the definition, $f(u)=mu+k$ and $f'(u)=m$, both hold at $u=-1$ and at $u=3$. These two values of $x$ are distinct, so $y=-5$ is a double tangent of $C_1$. It is worth noticing what has been used: the two minima having equal height is what makes one horizontal line work at both points, and that is the feature the rest of the question is about.

For the second claim, consider $f(x)+5$. It vanishes together with its derivative at $x=-1$ and at $x=3$, Write $f(x)+5=(x+1)^2S(x)$ with $S$ monic of degree $2$; then $S(3)=S'(3)=0$, because $(x-3)^2$ divides $f(x)+5$ and $(3+1)^2\ne 0$, so Fact 1 applied to $S$ gives $S(x)=(x-3)^2$ and hence $f(x)+5=(x+1)^2(x-3)^2$. $$f(x)+5=(x+1)^2(x-3)^2=\big((x+1)(x-3)\big)^2=(x^2-2x-3)^2,$$ which expanding confirms: $(x^2-2x-3)^2=x^4-4x^3-2x^2+12x+9$. Hence $f(x)+5\ge 0$ for every real $x$, with equality exactly when $x^2-2x-3=0$, that is exactly when $x=-1$ or $x=3$. So the line $y=-5$ meets $C_1$ at those two points and nowhere else, and $C_1$ lies on or above that line everywhere.

(i)(c) The substitution to try is $x=1+t$, and the choice of $1$ is not arbitrary: The substitution $x=1+t$ is a guess, and here is what motivates it: differentiating $f(p+t)=f(p-t)$ with respect to $t$ gives $f'(p+t)=-f'(p-t)$, so a vertical axis of symmetry permutes the three stationary points $x=-1,1,3$ and preserves the value of $f$ at them; since $f(1)=11$ and $f(-1)=f(3)=-5$, the only permutation available swaps $-1$ with $3$ and fixes $1$, so the only possible axis is $x=1$. Nothing below depends on this paragraph, because the symmetry about $x=1$ is proved outright by the substitution.. Using the factorisation just found, $$f(1+t)+5=\big((1+t)^2-2(1+t)-3\big)^2=(1+2t+t^2-2-2t-3)^2=(t^2-4)^2,$$ so $f(1+t)=(t^2-4)^2-5=t^4-8t^2+11$. Replacing $t$ by $-t$ leaves this unchanged, because only even powers of $t$ occur. Hence $f(1+t)=f(1-t)$ for every real $t$, which is precisely the statement that $C_1$ is symmetric about the line $x=1$.

(ii) The condition to be analysed is a statement about $f$ near $p$ in the variable $t$, so the move is to expand $f$ about $x=p$. That is the only step in this part which is a choice rather than a consequence, and part (i)(c) is where it was seen to work.

By the binomial theorem, $$f(p+t)=t^4+(4p+a)t^3+(6p^2+3ap+b)t^2+\big(4p^3+3ap^2+2bp+c\big)t+f(p).$$ Replacing $t$ by $-t$ changes the sign of the odd powers of $t$ only, so $$f(p+t)-f(p-t)=2\Big[(4p+a)t^3+\big(4p^3+3ap^2+2bp+c\big)t\Big].$$ So $C$ is symmetric about $x=p$ if and only if this polynomial in $t$ vanishes for every real $t$, and by Fact 2 that happens if and only if both of its coefficients vanish: $$4p+a=0\qquad\text{and}\qquad 4p^3+3ap^2+2bp+c=0.$$ The first equation determines $p$ completely: $p=-\frac{a}{4}$. So a quartic has at most one vertical line of symmetry, and the only candidate is $x=-\frac{a}{4}$. Substituting $p=-\frac{a}{4}$ into the second expression, $$4\left(-\frac{a^3}{64}\right)+3a\cdot\frac{a^2}{16}+2b\left(-\frac{a}{4}\right)+c=-\frac{a^3}{16}+\frac{3a^3}{16}-\frac{ab}{2}+c=\frac{a^3}{8}-\frac{ab}{2}+c=\frac{a^3-4ab+8c}{8}.$$ Hence the second condition is exactly $a^3-4ab+8c=0$.

Both directions now follow, and since the statement is an equivalence it is worth saying which is which. If $C$ is symmetric about some vertical line $x=p$, then both coefficients vanish, so $p=-\frac{a}{4}$ and $a^3-4ab+8c=0$. Conversely, if $a^3-4ab+8c=0$, take $p=-\frac{a}{4}$: the first coefficient vanishes by that choice of $p$, and the second vanishes by the computation above, so $f(p+t)-f(p-t)=0$ for every $t$, which is symmetry about $x=-\frac{a}{4}$.

As a check, the curve of part (i) has $a=-4$, $b=-2$ and $c=12$, so $a^3-4ab+8c=-64-32+96=0$ and $-\frac{a}{4}=1$, which agrees with (i)(c).

(iii) Write $P(x)=f(x)-(mx+k)$. Subtracting a linear function changes only the coefficients of $x$ and of $1$, so $P$ is a quartic with leading coefficient $1$ whose coefficients of $x^3$ and $x^2$ are still $a$ and $b$. That observation is what makes the coefficient comparison at the end possible, so it is worth making before any work is done.

The hypothesis that $y=mx+k$ touches $C$ at $x=u$ and at $x=v$ says exactly that $$P(u)=0,\qquad P'(u)=0,\qquad P(v)=0,\qquad P'(v)=0.$$ By Fact 1, $P(x)=(x-u)^2R(x)$ for some polynomial $R$, and comparing degrees and leading coefficients shows that $R$ is monic of degree $2$. Now use the two conditions at $v$. First, $0=P(v)=(v-u)^2R(v)$, and $v\ne u$, so $R(v)=0$. Second, differentiating the product, $$P'(x)=2(x-u)R(x)+(x-u)^2R'(x),$$ so $0=P'(v)=2(v-u)R(v)+(v-u)^2R'(v)=(v-u)^2R'(v)$, and again $v\ne u$ gives $R'(v)=0$. Applying Fact 1 to $R$ shows that $(x-v)^2$ divides $R$, and since $R$ is monic of degree $2$ this forces $R(x)=(x-v)^2$. Therefore $$f(x)-(mx+k)=(x-u)^2(x-v)^2\qquad\text{for every real }x.$$ Note where the hypothesis $u\ne v$ was used: twice, and without it the argument delivers nothing beyond the single factor $(x-u)^2$.

Now compare coefficients, which Fact 2 permits. Writing $(x-u)^2(x-v)^2=\big(x^2-(u+v)x+uv\big)^2$ and expanding, the coefficient of $x^3$ is $-2(u+v)$ and the coefficient of $x^2$ is $(u+v)^2+2uv$. The corresponding coefficients on the left are $a$ and $b$, so $$u+v=-\frac{a}{2},\qquad uv=\frac{1}{2}\left(b-\frac{a^2}{4}\right),$$ and therefore $$(u-v)^2=(u+v)^2-4uv=\frac{a^2}{4}-2b+\frac{a^2}{2}=\frac{3a^2-8b}{4}.$$ The coefficients of $x$ and of $1$ were deliberately left alone here: they involve $m$ and $k$, so they carry information about the line rather than about the two points of contact. They are used in (iv), for exactly that reason.

Finally, $u+v$ and $uv$ are determined by $a$ and $b$ alone, so the unordered pair $\{u,v\}$ is determined by $f$; and then $mx+k=f(x)-(x-u)^2(x-v)^2$ is determined as well. Hence $C$ has at most one double tangent.

As a check, the curve of part (i) has $a=-4$ and $b=-2$, giving $u+v=2$ and $(u-v)^2=\frac{48+16}{4}=16$, so $\{u,v\}=\{-1,3\}$, which is what part (i)(b) found.

(iv) Existence of a double tangent. Necessity is immediate from part (iii): if $C$ has a double tangent, touching at distinct values $u$ and $v$, then $\frac{3a^2-8b}{4}=(u-v)^2\gt 0$, so $3a^2\gt 8b$.

Sufficiency needs a line to be produced, and this is the one genuinely free step in the question. Part (iii) says what any such line must look like: $f$ minus the line is the square of a monic quadratic. So the thing to attempt is to build that quadratic. Look for real numbers $\alpha$ and $\beta$ making $f(x)-(x^2+\alpha x+\beta)^2$ of degree at most $1$. Expanding, $$(x^2+\alpha x+\beta)^2=x^4+2\alpha x^3+(\alpha^2+2\beta)x^2+2\alpha\beta x+\beta^2.$$ The coefficients of $x^4$ agree already. Taking $\alpha=\frac{a}{2}$ makes the coefficients of $x^3$ agree, and then taking $\beta=\frac{b-\alpha^2}{2}=\frac{b}{2}-\frac{a^2}{8}$ makes the coefficients of $x^2$ agree. These values are forced, not chosen: no others work. With them, $$f(x)-(x^2+\alpha x+\beta)^2=mx+k,\qquad\text{where }m=c-2\alpha\beta\ \text{ and }\ k=d-\beta^2,$$ which is a linear function of $x$, so $y=mx+k$ is a line. Nothing so far has used the hypothesis; the construction works for every quartic.

The hypothesis enters when we check that this line really touches $C$ at two distinct points. The quadratic $x^2+\alpha x+\beta$ has discriminant $$\alpha^2-4\beta=\frac{a^2}{4}-4\left(\frac{b}{2}-\frac{a^2}{8}\right)=\frac{a^2}{4}-2b+\frac{a^2}{2}=\frac{3a^2-8b}{4}\gt 0,$$ so it has two distinct real roots $u$ and $v$ and factorises as $x^2+\alpha x+\beta=(x-u)(x-v)$. Hence $f(x)-(mx+k)=(x-u)^2(x-v)^2$. The right hand side vanishes at $x=u$, and so does its derivative $2(x-u)(x-v)(2x-u-v)$, so $f(u)=mu+k$ and $f'(u)=m$: the line touches $C$ at $x=u$. The same holds at $x=v$, and $u\ne v$, so $y=mx+k$ is a double tangent of $C$. Together with the necessity above, $C$ has a double tangent if and only if $3a^2\gt 8b$.

(The excluded case is worth naming, since it is where a careless statement would be false. When $3a^2=8b$ the construction still produces a line, but the two roots coincide and the contact happens at a single point with contact of order four, as with the line $y=0$ and the curve $y=x^4$. The requirement in the question that the two values of $x$ be distinct is exactly what rules this out.)

(iv) When the double tangent is horizontal. Suppose $C$ has a double tangent $y=mx+k$, touching at $u\ne v$, and set $$s=\frac{u+v}{2},\qquad w=\frac{v-u}{2}\ne 0,$$ so that $u=s-w$ and $v=s+w$. Shifting to $s$ is the move from part (i)(c), now performed at the midpoint of the two points of contact. By part (iii), $f(x)=(x-u)^2(x-v)^2+mx+k$, and for any real $t$, $$(s+t-u)(s+t-v)=(t+w)(t-w)=t^2-w^2,$$ so $f(s+t)=(t^2-w^2)^2+m(s+t)+k$. Replacing $t$ by $-t$ leaves $(t^2-w^2)^2$ and $ms+k$ unchanged and changes $mt$ to $-mt$, so $$f(s+t)-f(s-t)=2mt\qquad\text{for every real }t.$$ This single identity settles both directions.

If $m=0$, then $f(s+t)=f(s-t)$ for every $t$, which is exactly the statement that $C$ is symmetric about the vertical line $x=s$.

Conversely, suppose $C$ is symmetric about some vertical line. The hypothesis is useless until that line is identified, and part (ii) identifies it: the line can only be $x=-\frac{a}{4}$. By part (iii), $u+v=-\frac{a}{2}$, so $s=-\frac{a}{4}$ and the line of symmetry is exactly $x=s$. Then $f(s+t)-f(s-t)=0$ for every $t$, so $2mt=0$ for every $t$; taking any $t\ne 0$ gives $m=0$, that is, the double tangent is horizontal.

An alternative for this last equivalence, for a reader who prefers coefficients. Comparing the coefficients of $x$ in the identity $f(x)-(mx+k)=(x-u)^2(x-v)^2$ gives $c-m=-2(u+v)uv$, and substituting $u+v=-\frac{a}{2}$ and $uv=\frac{b}{2}-\frac{a^2}{8}$ from part (iii) gives $$m=\frac{a^3-4ab+8c}{8}.$$ So $m=0$ if and only if $a^3-4ab+8c=0$, which by part (ii) is exactly the condition for $C$ to be symmetric about a vertical line. This route computes $m$; the route above avoids computing it, which is why it is shorter.

As a final check, the curve of part (i) has $a=-4$ and $b=-2$, so $3a^2-8b=64\gt 0$ and a double tangent exists; and $a^3-4ab+8c=0$, so it is horizontal. It is the line $y=-5$ found in part (i)(b).

(i)

The terms $\cos\theta,\cos3\theta,\ldots,\cos(2n-1)\theta$ do not cancel against one another as they stand, so something has to be done to them first. Two routes work, and choosing between them is the only real decision in this part.

Route 1, force a telescope. We look for a multiplier that turns each term into a difference of two things, one of which is the next term's partner. The angles lying at a distance $\theta$ either side of $(2k-1)\theta$ are $2k\theta$ and $(2k-2)\theta$, and those are consecutive even multiples of $\theta$, so they are exactly the objects that will cancel in pairs. That observation is what motivates the following, and writing $2k\theta=(2k-1)\theta+\theta$ and $(2k-2)\theta=(2k-1)\theta-\theta$ is the choice being made: $$\sin(2k\theta)-\sin\big((2k-2)\theta\big)=\sin\big((2k-1)\theta+\theta\big)-\sin\big((2k-1)\theta-\theta\big)=2\cos\big((2k-1)\theta\big)\sin\theta,$$ by the compound angle formula for $\sin(P\pm Q)$, the two $\sin\big((2k-1)\theta\big)\cos\theta$ terms cancelling. Summing this for $k=1,2,\ldots,n$, $$2\sin\theta\sum_{k=1}^{n}\cos\big((2k-1)\theta\big)=\sum_{k=1}^{n}\Big(\sin(2k\theta)-\sin\big((2k-2)\theta\big)\Big).$$ Write the right hand side out rather than asserting the cancellation, because that is where an off by one error would live: $$\big(\sin2\theta-\sin0\big)+\big(\sin4\theta-\sin2\theta\big)+\cdots+\big(\sin2n\theta-\sin(2n-2)\theta\big)=\sin2n\theta-\sin0=\sin2n\theta .$$ Every angle $2\theta,4\theta,\ldots,(2n-2)\theta$ occurs exactly twice, once with each sign, so only the two ends survive. Since $\sin\theta\neq0$ by hypothesis we may divide by $2\sin\theta$, and that hypothesis is exactly what makes the division legal: $$\sum_{k=1}^{n}\cos\big((2k-1)\theta\big)=\frac{\sin2n\theta}{2\sin\theta}.$$

Route 2, a geometric series. Put $z=\cos\theta+\mathrm{i}\sin\theta$. By de Moivre, $z^{2k-1}=\cos\big((2k-1)\theta\big)+\mathrm{i}\sin\big((2k-1)\theta\big)$, so the sum we want is the real part of $\sum_{k=1}^{n}z^{2k-1}$, a geometric series with first term $z$ and common ratio $z^{2}$. Before summing it we must know the ratio is not $1$: $z^{2}=\cos2\theta+\mathrm{i}\sin2\theta$ equals $1$ exactly when $\theta$ is an integer multiple of $\pi$, which is exactly the case $\sin\theta=0$ that the hypothesis excludes. So the two routes exclude the same $\theta$, which is a useful check on both. Then $$\sum_{k=1}^{n}z^{2k-1}=z\cdot\frac{z^{2n}-1}{z^{2}-1}=\frac{z^{2n}-1}{z-z^{-1}}=\frac{z^{2n}-1}{2\mathrm{i}\sin\theta},$$ using $z^{-1}=\cos\theta-\mathrm{i}\sin\theta$. Since $2\sin\theta$ is real and $1/\mathrm{i}=-\mathrm{i}$, taking real parts turns the numerator's imaginary part into the answer: $$\sum_{k=1}^{n}\cos\big((2k-1)\theta\big)=\frac{\operatorname{Im}\big(z^{2n}-1\big)}{2\sin\theta}=\frac{\sin2n\theta}{2\sin\theta}.$$

The deduction. Take $\theta=\dfrac{\pi}{2n+1}$. This lies strictly between $0$ and $\pi$, so $\sin\theta\neq0$ and the identity applies. The point is the arithmetic of the numerator: $$2n\theta=\frac{2n\pi}{2n+1}=\pi-\frac{\pi}{2n+1}=\pi-\theta ,$$ so $\sin2n\theta=\sin(\pi-\theta)=\sin\theta$ and the quotient collapses: $$\sum_{k=1}^{n}\cos\frac{(2k-1)\pi}{2n+1}=\frac{\sin\theta}{2\sin\theta}=\frac12 .$$ Note what this says: the answer does not depend on $n$ at all. Part (iv) will show that it does not depend on the power either, and this is the case of that statement with the power equal to $1$.

(ii)

Why one condition is enough. Suppose $\sin\theta=0$. Then $\theta=p\pi$ for some integer $p$, so $3\theta=3p\pi$ and $\sin3\theta=0$ as well. Taking the contrapositive: if $\sin3\theta\neq0$ then $\sin\theta\neq0$. So the single stated condition licenses both of the applications of part (i) that follow. The converse is false, which is the whole reason the condition has to be stated in terms of $3\theta$: at $\theta=\pi/3$ we have $\sin\theta\neq0$ but $\sin3\theta=0$.

The identity. From $\cos3A=4\cos^{3}A-3\cos A$, which is de Moivre with index $3$ or the standard triple angle formula, $$\cos^{3}A=\frac{3\cos A+\cos3A}{4}\qquad\text{for every real }A .$$ Put $A=(2k-1)\theta$ and sum for $k=1,\ldots,n$. Both sums are finite, so splitting them is free: $$\sum_{k=1}^{n}\cos^{3}\big((2k-1)\theta\big)=\frac34\sum_{k=1}^{n}\cos\big((2k-1)\theta\big)+\frac14\sum_{k=1}^{n}\cos\big(3(2k-1)\theta\big).$$ The first sum is part (i). The second is the step the rest of the question is built on, and it is a choice rather than a consequence: rewrite $$3(2k-1)\theta=(2k-1)(3\theta),$$ so that the angles in the second sum, namely $3\theta,\,9\theta,\,\ldots,\,(2n-1)(3\theta)$, are precisely the first $n$ odd multiples of $3\theta$. Part (i) therefore applies verbatim with $\theta$ replaced throughout by $3\theta$, which is legitimate because $\sin3\theta\neq0$. Hence $$\sum_{k=1}^{n}\cos^{3}\big((2k-1)\theta\big)=\frac34\cdot\frac{\sin2n\theta}{2\sin\theta}+\frac14\cdot\frac{\sin\big(2n\cdot3\theta\big)}{2\sin3\theta}=\frac{3\sin2n\theta}{8\sin\theta}+\frac{\sin6n\theta}{8\sin3\theta}.$$

The excluded values. For $0\lt\theta\lt\pi$ we have $0\lt3\theta\lt3\pi$, and in that range $\sin3\theta=0$ exactly when $3\theta=\pi$ or $3\theta=2\pi$, that is $$\theta=\frac{\pi}{3}\quad\text{or}\quad\theta=\frac{2\pi}{3}.$$ There is nothing else to exclude, since $\sin\theta=0$ has no solution with $0\lt\theta\lt\pi$.

The excluded case, evaluated directly. At $\theta=\pi/3$ and $n=3$ the three angles are $\pi/3$, $\pi$ and $5\pi/3$, with cosines $\tfrac12$, $-1$ and $\tfrac12$. So $$\sum_{k=1}^{3}\cos^{3}\big((2k-1)\tfrac{\pi}{3}\big)=\tfrac18-1+\tfrac18=-\tfrac34 .$$ The formula cannot be evaluated here, because its second term is $0/0$: at $\theta=\pi/3$ both $\sin6n\theta$ and $\sin3\theta$ vanish. What must not be done is to declare that term equal to $1$, as it is for a generic $\theta$, which would give $\frac18$, or to discard it as zero, which would give $0$. The sum itself is a trigonometric polynomial and so is perfectly well behaved at $\theta=\pi/3$, and indeed the limit of the right hand side as $\theta\to\pi/3$ is $0+(-\frac34)=-\frac34$, which agrees with the direct evaluation, as it must.

(iii)

Set $z=\cos A+\mathrm{i}\sin A$, so that $|z|=1$ and $z^{-1}=\cos A-\mathrm{i}\sin A$. By de Moivre, for every integer $r$, $$z^{r}+z^{-r}=\big(\cos rA+\mathrm{i}\sin rA\big)+\big(\cos rA-\mathrm{i}\sin rA\big)=2\cos rA .$$ In particular $z+z^{-1}=2\cos A$. Raising that to the power $2m+1$ by the binomial theorem, which is available because $2m+1$ is a positive integer, $$\big(2\cos A\big)^{2m+1}=\big(z+z^{-1}\big)^{2m+1}=\sum_{j=0}^{2m+1}\binom{2m+1}{j}z^{\,2m+1-j}\big(z^{-1}\big)^{j}=\sum_{j=0}^{2m+1}\binom{2m+1}{j}z^{\,2m+1-2j}.$$ The expansion has $2m+2$ terms and we want $m+1$ cosines, so the move is to pair the terms off. Pair the term with index $j$ against the term with index $2m+1-j$. Their coefficients are equal, since $\binom{2m+1}{j}=\binom{2m+1}{2m+1-j}$, and their exponents are negatives of one another, since $$2m+1-2(2m+1-j)=-(2m+1-2j).$$ As $j$ runs through $0,1,\ldots,m$ its partner $2m+1-j$ runs through $2m+1,2m,\ldots,m+1$, so the $2m+2$ terms fall into exactly $m+1$ pairs, with no term left over and no term used twice. This is where the exponent being odd is doing real work: an even power would have a middle term that is its own partner, and the corresponding identity carries an extra constant. Using $z^{r}+z^{-r}=2\cos rA$ on each pair, $$\big(2\cos A\big)^{2m+1}=\sum_{j=0}^{m}\binom{2m+1}{j}\Big(z^{\,2m+1-2j}+z^{-(2m+1-2j)}\Big)=2\sum_{j=0}^{m}\binom{2m+1}{j}\cos\big((2m+1-2j)A\big).$$ Dividing by $2$, and noting $2^{2m+1}/2=2^{2m}$, $$2^{2m}\cos^{2m+1}A=\sum_{j=0}^{m}\binom{2m+1}{j}\cos\big((2m+1-2j)A\big),$$ as required. As a check, $m=1$ gives $4\cos^{3}A=\cos3A+3\cos A$, which is the identity used in part (ii), and $m=2$ gives $16\cos^{5}A=\cos5A+5\cos3A+10\cos A$.

(iv)

Write $r_{j}=2m+1-2j$. As $j$ runs through $0,1,\ldots,m$, $r_{j}$ runs through $2m+1,\,2m-1,\,\ldots,\,3,\,1$: that is, through every odd integer from $1$ to $2m+1$, each exactly once. So the hypothesis, that $\sin(r\theta)\neq0$ for every odd $r$ with $1\leqslant r\leqslant2m+1$, says precisely that $\sin(r_{j}\theta)\neq0$ for each $j$ in the range, and that is precisely what is needed to apply part (i) at the angle $r_{j}\theta$, once for each $j$. The hypothesis is not decoration: it is the list of $m+1$ conditions the argument is about to consume.

Put $A=(2k-1)\theta$ in part (iii) and sum over $k$. Both sums are finite, so they may be interchanged: $$2^{2m}\sum_{k=1}^{n}\cos^{2m+1}\big((2k-1)\theta\big)=\sum_{k=1}^{n}\sum_{j=0}^{m}\binom{2m+1}{j}\cos\big(r_{j}(2k-1)\theta\big)=\sum_{j=0}^{m}\binom{2m+1}{j}\sum_{k=1}^{n}\cos\big(r_{j}(2k-1)\theta\big).$$ Exactly as in part (ii), $r_{j}(2k-1)\theta=(2k-1)\big(r_{j}\theta\big)$, so the inner sum runs over the first $n$ odd multiples of the angle $r_{j}\theta$, and part (i) gives $$\sum_{k=1}^{n}\cos\big((2k-1)(r_{j}\theta)\big)=\frac{\sin\big(2nr_{j}\theta\big)}{2\sin\big(r_{j}\theta\big)} .$$ Substituting and dividing by $2^{2m}$, $$\sum_{k=1}^{n}\cos^{2m+1}\big((2k-1)\theta\big)=\frac{1}{2^{2m+1}}\sum_{j=0}^{m}\binom{2m+1}{j}\frac{\sin\big(2n(2m+1-2j)\theta\big)}{\sin\big((2m+1-2j)\theta\big)},$$ which is the required identity.

The deduction. Take $\theta=\dfrac{\pi}{2n+1}$ and suppose $m\leqslant n-1$. First check the hypothesis, since this is the only place the restriction on $m$ is used: each $r_{j}$ is odd with $$1\leqslant r_{j}\leqslant2m+1\leqslant2n-1\lt2n+1,$$ so $0\lt r_{j}\theta\lt\pi$ and therefore $\sin(r_{j}\theta)\neq0$. The identity above is thus available. Now evaluate each quotient. For each $j$, $$2nr_{j}\theta=\frac{2nr_{j}\pi}{2n+1}=r_{j}\pi-\frac{r_{j}\pi}{2n+1}=r_{j}\pi-r_{j}\theta ,$$ and since $r_{j}$ is odd, $\sin(r_{j}\pi)=0$ and $\cos(r_{j}\pi)=-1$, so $$\sin\big(r_{j}\pi-r_{j}\theta\big)=\sin(r_{j}\pi)\cos(r_{j}\theta)-\cos(r_{j}\pi)\sin(r_{j}\theta)=\sin(r_{j}\theta).$$ Every quotient is therefore $1$, and $$\sum_{k=1}^{n}\cos^{2m+1}\frac{(2k-1)\pi}{2n+1}=\frac{1}{2^{2m+1}}\sum_{j=0}^{m}\binom{2m+1}{j}.$$ The remaining sum is half of a full binomial expansion: the map $j\mapsto2m+1-j$ is a bijection from $\{0,1,\ldots,m\}$ onto $\{m+1,\ldots,2m+1\}$ and $\binom{2m+1}{j}=\binom{2m+1}{2m+1-j}$, so the two halves of $$\sum_{j=0}^{2m+1}\binom{2m+1}{j}=2^{2m+1}$$ are equal and each is $2^{2m}$. Hence the sum equals $\dfrac{2^{2m}}{2^{2m+1}}=\dfrac12$ for every $m$ with $m\leqslant n-1$, and in particular it does not depend on $m$: the value found in part (i) for the first power is the value for every odd power up to the $(2n-1)$th.

Why $m=n$ is different. When $m=n$ the index $j=0$ gives $r_{0}=2m+1=2n+1$, and then $$\sin(r_{0}\theta)=\sin\left(\frac{(2n+1)\pi}{2n+1}\right)=\sin\pi=0 .$$ The hypothesis of the identity fails, so the term with $j=0$ cannot be evaluated by substitution. It is not that the term contributes nothing: it is a $0/0$, and the temptation to declare it equal to $1$ like all the others is exactly what must be resisted, since that gives $\frac12$ and the answer is not $\frac12$. A reader who prefers to rescue the identity may take the limit as $\theta\to\frac{\pi}{2n+1}$, which is legitimate because both sides are continuous and the identity holds nearby, and that limit gives the $j=0$ quotient the value $-2n$; the direct route below avoids the limit altogether and is the one to write out in an examination. The temptation to be resisted is specific and worth naming: the numerator of that term, $\sin(2nr_{0}\theta)=\sin(2n\pi)$, is also zero, so the offending term looks like $0/0$ and it is easy to declare it equal to $1$ like all the others and carry on. That step is invalid, and here it does not merely fail to be justified, it gives a false answer.

The case $m=n=2$. Here $\theta=\pi/5$ and the two angles are $\pi/5$ and $3\pi/5$. Rather than substitute into a formula that does not apply, go back to part (iii), which holds for every real $A$: with $m=2$, $$16\cos^{5}A=\cos5A+5\cos3A+10\cos A .$$ Sum over the two angles. For the $\cos5A$ term the angles become $\pi$ and $3\pi$, so that contribution is $\cos\pi+\cos3\pi=-1-1=-2$; this is the term the general argument could not handle, and it is nowhere near the value $\tfrac12$ that the other terms take. For the $\cos3A$ term the angles are the first two odd multiples of $3\pi/5$, and part (i) applies since $\sin(3\pi/5)\neq0$, giving $\tfrac12$; the $\cos A$ term gives $\tfrac12$ in the same way. Hence $$\sum_{k=1}^{2}\cos^{5}\frac{(2k-1)\pi}{5}=\frac{1}{16}\left(-2+5\cdot\frac12+10\cdot\frac12\right)=\frac{1}{16}\cdot\frac{11}{2}=\frac{11}{32},$$ and $\tfrac{11}{32}\neq\tfrac12$, as required. As a numerical check, $\cos^{5}(\pi/5)+\cos^{5}(3\pi/5)=0.34375$, which is $11/32$ exactly.

Remark, not required by the question. The same computation for general $n$ with $m=n$ gives $-n$ from the single term $r=2n+1$ and $\tfrac12$ from each of the others, so $$\sum_{k=1}^{n}\cos^{2n+1}\frac{(2k-1)\pi}{2n+1}=\frac{1}{2^{2n}}\left(-n+\frac{2^{2n}-1}{2}\right)=\frac12-\frac{2n+1}{2^{2n+1}} .$$ The value $11/32$ above is the case $n=2$. More is true, and it costs one line. At $\theta=\frac{\pi}{2n+1}$ the inner sum $\sum_{k=1}^{n}\cos\big((2k-1)r\theta\big)$ equals $\frac12$ when $2n+1$ does not divide the odd number $r$, and equals $-n$ when it does, because then every cosine is $\cos$ of an odd multiple of $\pi$. Hence in general $\sum_{k=1}^{n}\cos^{2m+1}\frac{(2k-1)\pi}{2n+1}=\frac12-\frac{(2n+1)T}{2^{2m+1}}$ where $T$ is the sum of those $\binom{2m+1}{j}$ for which $2n+1$ divides $2m+1-2j$; since $T=0$ exactly when $2m+1\lt2n+1$ and $T\geqslant1$ otherwise, the answer is $\frac12$ precisely when $m\leqslant n-1$ and is strictly smaller for every $m\geqslant n$.

(i) Both halves of this part are governed by one quadratic, so it is worth producing it before doing anything else. For a non-zero real $x$, multiplying $x + \frac{1}{x} = t$ through by $x$ gives $$x^2 - tx + 1 \;=\; 0. \qquad (\ast)$$ Multiplying by $x$ is reversible here because $x \ne 0$ is given, so the non-zero real solutions of the original equation are exactly the real roots of $(\ast)$. Note also that $0$ is never a root of $(\ast)$, since putting $x = 0$ into it gives $1 = 0$; so no root has to be discarded afterwards.

Now $(\ast)$ is a quadratic in $x$ with real coefficients, so it has a real root if and only if its discriminant is non-negative, that is if and only if $t^2 - 4 \ge 0$. Since $t^2 - 4 = (t-2)(t+2)$, this product is non-negative exactly when $t \ge 2$ or $t \le -2$. That settles both directions of the 'if and only if' at once, which is why the quadratic was worth writing down first.

(If one prefers to prove the forward direction directly, the two signs of $x$ have to be separated, because the sign of $x$ decides the direction of the inequality: for $x \gt 0$, $\;x + \frac{1}{x} - 2 = \frac{(x-1)^2}{x} \ge 0$, and for $x \lt 0$, $\;x + \frac{1}{x} + 2 = \frac{(x+1)^2}{x} \le 0$.)

For the solution set, use the product of the roots of $(\ast)$, which is the constant term $1$. So if $x_0$ is one root, the other is $\frac{1}{x_0}$, and the complete solution set is $\left\{ x_0, \frac{1}{x_0} \right\}$. When $t = 2$ or $t = -2$ the discriminant is zero and the two roots coincide, at $x_0 = 1$ and $x_0 = -1$ respectively; since $x_0 = \frac{1}{x_0}$ in those two cases, the description above is still correct, the set simply has one element. The fact to carry forward is this: the numbers of the form $x + \frac{1}{x}$ are exactly the reals $t$ with $t \ge 2$ or $t \le -2$, and each of them is produced by a reciprocal pair of values of $x$ and by nothing else.

(ii)(a) Expand powers of $t$ and collect the middle terms. For every non-zero real $x$, $$t^2 \;=\; \left(x + \frac{1}{x}\right)^2 \;=\; x^2 + 2 + \frac{1}{x^2},\qquad\text{so}\qquad x^2 + \frac{1}{x^2} \;=\; t^2 - 2,$$ and $$t^3 \;=\; x^3 + 3x + \frac{3}{x} + \frac{1}{x^3} \;=\; \left(x^3 + \frac{1}{x^3}\right) + 3t, \qquad\text{so}\qquad x^3 + \frac{1}{x^3} \;=\; t^3 - 3t.$$ Nothing beyond $x \ne 0$ was used, so both identities hold for every non-zero real $x$. That last remark is not decoration: part (c) and part (v) both depend on the identities holding for every non-zero real number, including numbers that are themselves powers of $x$.

(ii)(b) By (a), the equation $x^3 + \frac{1}{x^3} = 3\left(x + \frac{1}{x}\right)$ says $t^3 - 3t = 3t$, that is $$t^3 - 6t \;=\; 0, \qquad\text{that is}\qquad t\left(t^2 - 6\right) \;=\; 0,$$ so $t = 0$, $t = \sqrt{6}$ or $t = -\sqrt{6}$.

Here is the step where the question can be lost: solving for $t$ is not solving for $x$, and a value of $t$ is only useful if some non-zero real $x$ actually produces it. Each root must therefore be tested against part (i) and then converted back. $\bullet$ $t = 0$ satisfies neither $t \ge 2$ nor $t \le -2$, so by part (i) no non-zero real $x$ has $x + \frac{1}{x} = 0$. This root is rejected, and it contributes no solutions. $\bullet$ $t = \pm\sqrt{6}$: since $6 \ge 4$ we have $\sqrt{6} \ge 2$, so both values are admissible.

For $t = \sqrt{6}$, equation $(\ast)$ reads $x^2 - \sqrt{6}\,x + 1 = 0$, whose roots are $$x \;=\; \frac{\sqrt{6} \pm \sqrt{6-4}}{2} \;=\; \frac{\sqrt{6} \pm \sqrt{2}}{2},$$ a reciprocal pair as part (i) predicts. For $t=-\sqrt6$, equation $(\ast)$ becomes $x^2+\sqrt6\,x+1=0$, which is what $x^2-\sqrt6\,x+1=0$ becomes under $x \mapsto -x$, so its roots are the negatives of the two just found, namely $x=-\frac{\sqrt6+\sqrt2}{2}$ and $x=-\frac{\sqrt6-\sqrt2}{2}$. So the complete list of real solutions is $$x \;=\; \frac{\sqrt{6}+\sqrt{2}}{2}, \qquad x \;=\; \frac{\sqrt{6}-\sqrt{2}}{2}, \qquad x \;=\; -\frac{\sqrt{6}-\sqrt{2}}{2}, \qquad x \;=\; -\frac{\sqrt{6}+\sqrt{2}}{2}.$$ The list is complete because every step was an equivalence: the original equation holds if and only if $t\left(t^2-6\right) = 0$, and Each admissible value of $t$ contributes the roots of $(\ast)$, and here $t^2-4=2 \gt 0$ for both $t=\sqrt6$ and $t=-\sqrt6$, so each contributes two distinct values of $x$ rather than the single value that part (i) showed occurs when $t=\pm2$; the four values listed are therefore all of them.. As an arithmetic check, $\frac{\sqrt{6}+\sqrt{2}}{2} \approx 1.9319$, its reciprocal is $\approx 0.5176$, and those sum to $\approx 2.4495 = \sqrt{6}$.

(ii)(c) The identity of part (a) was proved in the form: for every non-zero real $u$, $\;u^2 + \frac{1}{u^2} = \left(u + \frac{1}{u}\right)^2 - 2$. The choice made here, rather than expanding $t^4$, is to apply that identity with $u = x^2$. This is legitimate for exactly one reason, and the reason is worth stating: $x^2$ is again a non-zero real number, and the identity was proved for every non-zero real number. Hence $$x^4 + \frac{1}{x^4} \;=\; \left(x^2 + \frac{1}{x^2}\right)^2 - 2 \;=\; \left(t^2-2\right)^2 - 2 \;=\; t^4 - 4t^2 + 2.$$ The move rehearsed here, feeding a power of $x$ back into an identity that holds for every non-zero real number, is the move part (v) is built on.

(iii) Let $S(n)$ be the statement: there is a polynomial $p_n$, of degree $n$ and with leading coefficient $1$, such that $p_n\!\left(x+\frac{1}{x}\right) = x^n + \frac{1}{x^n}$ for every non-zero real $x$.

Base cases. $S(1)$ holds with $p_1(t) = t$, which is the definition of $t$. $S(2)$ holds with $p_2(t) = t^2 - 2$, by part (ii)(a). Both are monic of the stated degree. Two base cases are checked rather than one, and the reason appears in the next paragraph.

The identity the induction runs on. This is the one step of the question that is not signposted, so it is worth saying how it is found. The only lever available for raising the exponent is multiplication by $t = x + \frac{1}{x}$, so multiply and see what appears: $$\left(x^n + \frac{1}{x^n}\right)\left(x + \frac{1}{x}\right) \;=\; x^{n+1} + x^{n-1} + \frac{1}{x^{n-1}} + \frac{1}{x^{n+1}} \;=\; \left(x^{n+1} + \frac{1}{x^{n+1}}\right) + \left(x^{n-1} + \frac{1}{x^{n-1}}\right),$$ valid for every non-zero real $x$ and every integer $n \ge 1$. Rearranged, $$x^{n+1} + \frac{1}{x^{n+1}} \;=\; t\left(x^n + \frac{1}{x^n}\right) - \left(x^{n-1} + \frac{1}{x^{n-1}}\right).$$ The cross terms did not cancel, they became the case $n-1$: the relation reaches back two steps, and that is precisely why two base cases are needed and why a one-step induction cannot be made to work.

Inductive step. Suppose $S(n-1)$ and $S(n)$ both hold, for some integer $n \ge 2$, with polynomials $p_{n-1}$ and $p_n$. Define $$p_{n+1}(t) \;=\; t\,p_n(t) - p_{n-1}(t),$$ which is a polynomial with real coefficients. Let $x$ be any non-zero real number and substitute $t = x + \frac{1}{x}$. Using $S(n)$ and $S(n-1)$ on the two terms and then the displayed identity, $$p_{n+1}\!\left(x+\frac{1}{x}\right) \;=\; \left(x+\frac{1}{x}\right)\left(x^n + \frac{1}{x^n}\right) - \left(x^{n-1}+\frac{1}{x^{n-1}}\right) \;=\; x^{n+1} + \frac{1}{x^{n+1}}.$$ For the degree: by the inductive hypothesis $t\,p_n(t)$ has degree $n+1$ and leading coefficient $1$, while $p_{n-1}$ has degree $n-1$, and $n-1 \lt n+1$, so subtracting it cannot touch the leading term. Hence $p_{n+1}$ has degree $n+1$ and leading coefficient $1$, and $S(n+1)$ holds.

Since $S(1)$ and $S(2)$ hold, and any two consecutive cases give the next, $S(n)$ holds for every positive integer $n$. For the record the first few are $p_1 = t$, $p_2 = t^2-2$, $p_3 = t^3-3t$, $p_4 = t^4-4t^2+2$ and $p_5 = t^5-5t^3+5t$; the third and fourth of these agree with parts (ii)(a) and (ii)(c), which is a useful check that the recurrence has been set up with the right signs.

(iv) Suppose, for a contradiction, that $n$ is a positive integer and that $q$ is a polynomial with $q\!\left(x+\frac{1}{x}\right) = x^n - \frac{1}{x^n}$ for every non-zero real $x$. Note what is being assumed: a single $q$, working at every non-zero real $x$ at once. It is that 'every' which will be turned against the assumption.

Part (i) says that each attainable value of $t$ comes from a reciprocal pair of values of $x$. So the left-hand side cannot distinguish $x$ from $\frac{1}{x}$. The right-hand side plainly can: replacing $x$ by $\frac{1}{x}$ turns $x^n - \frac{1}{x^n}$ into its own negative. One well-chosen pair of values is therefore enough, and the only care needed is to choose $x$ with $x \ne \frac{1}{x}$, that is $x \ne 1$ and $x \ne -1$.

Take $x = 2$ and $x = \frac{1}{2}$. Both give $x + \frac{1}{x} = \frac{5}{2}$, so the assumed property, applied twice, gives $$q\!\left(\tfrac{5}{2}\right) \;=\; 2^n - 2^{-n} \qquad\text{and}\qquad q\!\left(\tfrac{5}{2}\right) \;=\; 2^{-n} - 2^{n}.$$ A polynomial takes only one value at $\frac{5}{2}$, so these two numbers are equal. Adding them, $2\left(2^n - 2^{-n}\right) = 0$, hence $2^n = 2^{-n}$, hence $2^{2n} = 1$. But $n \ge 1$ gives $2^{2n} \ge 4$, so $2^{2n} = 1$ is false.

The only assumption made was that such a $q$ exists, so that assumption is what fails: there is no such polynomial. Two remarks are worth making. First, nothing in the argument used that $q$ is a polynomial, only that it is a function taking one value at each point; so no function of $x + \frac{1}{x}$ whatsoever can equal $x^n - \frac{1}{x^n}$. Second, this is exactly the contrast with part (iii): $x^n + \frac{1}{x^n}$ is unchanged when $x$ is replaced by $\frac{1}{x}$, and it is that symmetry which leaves room for a $p_n$ to exist at all.

(v) Fix positive integers $m$ and $n$, and let $p_m$, $p_n$ and $p_{mn}$ be polynomials with the property of part (iii). Put $$D(u) \;=\; p_m\!\left(p_n(u)\right) - p_{mn}(u),$$ which is a polynomial in $u$, because a composition of polynomials is a polynomial. The claim is that $D(u) = 0$ for every real $u$.

Step 1: the identity where $t$ can be reached. Let $x$ be any non-zero real number and set $t = x + \frac{1}{x}$. The choice on which the whole part turns is to put $$y \;=\; x^n,$$ which is the general form of the substitution rehearsed in part (ii)(c). Then $y$ is a non-zero real number, and by part (iii), $$p_n(t) \;=\; x^n + \frac{1}{x^n} \;=\; y + \frac{1}{y}.$$ So $p_n(t)$ is itself of the special form, with $y$ in the role of $x$. Now apply the defining property of $p_m$ to $y$. This is legitimate because that property holds for every non-zero real number and $y$ is one of them: $$p_m\!\left(p_n(t)\right) \;=\; p_m\!\left(y + \frac{1}{y}\right) \;=\; y^m + \frac{1}{y^m} \;=\; x^{mn} + \frac{1}{x^{mn}} \;=\; p_{mn}(t),$$ the last equality being part (iii) applied with $mn$ in place of $n$. Hence $D(t) = 0$.

Step 2: what has, and has not, been proved. By part (i), the values of $t$ produced this way are exactly the real numbers with $t \ge 2$ or $t \le -2$. So Step 1 proves $D(t) = 0$ on those two half-lines and says nothing at all, directly, about the values of $u$ with $-2 \lt u \lt 2$. Declaring the identity proved at this point would be the plausible invalid step, because the identity was asked for at every real $u$, and no non-zero real $x$ produces a $t$ strictly between $-2$ and $2$.

Step 3: the extension, and this is what the Fact is for. The half-line $t \ge 2$ contains infinitely many distinct real numbers, for instance $2, 3, 4, 5, \dots$, and $D$ vanishes at every one of them. Suppose $D$ were not the zero polynomial. Then, by the Fact, a polynomial vanishing at infinitely many distinct real numbers has all its coefficients equal to $0$, which is to say it is the zero polynomial: a contradiction. Hence $D$ is the zero polynomial, so $D(u) = 0$ and $$p_m\!\left(p_n(u)\right) \;=\; p_{mn}(u)$$ for every real number $u$, as required.

Two closing remarks. The argument used only the defining property of the chosen polynomials, so the conclusion does not depend on which polynomials with that property were picked; and in fact the Fact shows there is only one for each $n$, since the difference of two would vanish on both half-lines. As a check of the result, $p_2\!\left(p_3(u)\right) = \left(u^3-3u\right)^2 - 2 = u^6 - 6u^4 + 9u^2 - 2$, and running the recurrence of part (iii) up to $n = 6$ gives $p_6(u) = u^6 - 6u^4 + 9u^2 - 2$ as well.

Notation and conventions. Take the direction of the blows as the positive direction, and measure every velocity and displacement along the line of motion. Write $v_A$ and $v_B$ for the velocities of $A$ and $B$, and $$u \;=\; v_B - v_A$$ for the velocity of $B$ relative to $A$. Write $$a \;=\; \frac{\mu g (M+m)}{M},$$ which part (i) identifies as the rate at which $u$ falls while the blocks slide on each other. Working with the single quantity $u$ rather than with $v_A$ and $v_B$ separately is a choice, not a consequence, and it is the choice that makes parts (iii) and (iv) short: every blow does the same thing to $u$, and friction does the same thing to $u$, whatever common velocity the blocks happen to have at the time.

(i) Why $A$ does not move during the blow. This is the modelling decision the whole question turns on, so it deserves a careful argument rather than an assertion.

The only horizontal force ever acting on $A$ is the friction from the upper face of $B$. Now $A$ stays on that face, which is horizontal, so $A$ has no vertical acceleration; resolving vertically for $A$ gives a normal contact force of $mg$. Hence the friction on $A$ has magnitude at most $\mu m g$ at every instant, and that bound does not depend on what is being done to $B$. The impulse delivered to $A$ over a time interval of length $\tau$ is the integral of that force over the interval, so its magnitude is at most $\mu m g \tau$. The blow is modelled as instantaneous, so $\tau = 0$ and the impulse on $A$ is zero. By the impulse-momentum principle the momentum of $A$ is unchanged, so $A$ is still at rest immediately after the blow.

It is worth being clear about what this argument does not claim. It does not say that friction is negligible: over the motion that follows, friction is the only thing that happens. It says that a force whose magnitude is bounded cannot deliver a non-zero impulse in zero time. The blow is not bounded in this way, which is precisely why it can change the velocity of $B$.

The velocity of $B$. Apply the impulse-momentum principle to $B$ horizontally. The impulses acting on $B$ are the blow, of impulse $J$; the friction from $A$, which by the argument just given contributes zero over the blow; and the force from the floor, which is vertical because the floor is smooth. Hence $M v_B - 0 = J$, so $$v_B \;=\; \frac{J}{M} \qquad \text{immediately after the blow.}$$

The relative deceleration. Insert before the supposition: "In this part $u$ starts at the value $J/M \gt 0$ immediately after the blow, and $u$ varies continuously thereafter, so $u$ cannot become negative without first taking the value zero, at which point the surfaces stop sliding. Hence for as long as the two blocks have different velocities in this part we have $u \gt 0$, and it is this case that has to be treated. For the record, if $u$ were negative the friction would reverse and the same calculation would give $\dot u = +a$, so the general statement is that $\left|u\right|$ decreases at the constant rate $a$ while the surfaces slide." Friction then takes its limiting value $\mu m g$ and opposes the relative sliding: the face of $B$ is moving forwards underneath $A$, so the friction on $A$ from $B$ acts forwards, and by Newton's third law the friction on $B$ from $A$ acts backwards with the same magnitude. Resolving horizontally and applying Newton's second law to each block separately, $$\text{for } A: \quad m \dot v_A = \mu m g, \qquad\text{so}\qquad \dot v_A = \mu g;$$ $$\text{for } B: \quad M \dot v_B = -\mu m g, \qquad\text{so}\qquad \dot v_B = -\frac{\mu m g}{M},$$ the floor contributing nothing horizontally because it is smooth. Subtracting, $$\dot u \;=\; \dot v_B - \dot v_A \;=\; -\frac{\mu m g}{M} - \mu g \;=\; -\frac{\mu g (M+m)}{M} \;=\; -a .$$ So while the blocks have different velocities, $u$ decreases at the constant rate $a$, as required. Both individual accelerations are constant as well, which is what makes the constant-acceleration relations available in part (ii).

(ii) The common velocity. Immediately after the blow $u = J/M \gt 0$, and by (i) $u$ falls at the constant rate $a$ while it is positive, so $u = \dfrac{J}{M} - at$ and $u$ first reaches zero at $$t \;=\; \frac{J/M}{a} \;=\; \frac{J}{M}\cdot\frac{M}{\mu g (M+m)} \;=\; \frac{J}{\mu g (M+m)}.$$ At that instant $v_A = \mu g t = \dfrac{J}{M+m}$, and likewise $v_B = \dfrac{J}{M} - \dfrac{\mu m g}{M}\,t = \dfrac{J}{M} - \dfrac{mJ}{M(M+m)} = \dfrac{J}{M+m}$, which agrees.

There is a quicker route to the same value, and it is worth recording because it is an independent check on the algebra: after the blow no horizontal external impulse acts on the system consisting of $A$ together with $B$, since the floor is smooth, so the total horizontal momentum keeps the value $J$ it had just after the blow. When the two move together with common velocity $V$ this gives $(M+m)V = J$, so $V = \dfrac{J}{M+m}$.

They then continue to move together, and this needs saying rather than assuming. Replace with: "If the blocks move together with no acceleration, the horizontal force required on $A$ is zero, and zero lies within the range permitted for friction when there is no relative sliding, so the joint state is allowed. That it is forced needs one further step, because the friction law only bounds the force when there is no sliding and so does not by itself say what happens. Suppose sliding restarted, with $u$ becoming positive. Friction would then take its limiting value opposing the sliding, and by part (i) $\dot u = -a \lt 0$, so $u$ would be decreasing at the instant it was supposed to be increasing from zero: impossible. If instead $u$ became negative, friction would reverse and $\dot u = +a \gt 0$, so $u$ would be increasing at the instant it was supposed to be decreasing from zero: also impossible. Hence $u$ stays at zero and the blocks continue to move together." Hence from $t = \dfrac{J}{\mu g (M+m)}$ onwards the blocks move with the common velocity $\dfrac{J}{M+m}$.

The distance slid. The displacement of $B$ relative to $A$ over the sliding phase is the displacement of a motion whose velocity falls at the constant rate $a$ from $J/M$ to $0$. Applying the constant-acceleration relation (final velocity squared equals initial velocity squared plus twice acceleration times displacement) to the relative motion, $$0^2 \;=\; \left(\frac{J}{M}\right)^{2} - 2 a s, \qquad\text{so}\qquad s \;=\; \frac{(J/M)^2}{2a} \;=\; \frac{J^2}{M^2}\cdot\frac{M}{2\mu g (M+m)} \;=\; \frac{J^2}{2\mu g M (M+m)} \;=\; d .$$ Throughout the motion $u \ge 0$: it starts positive and decreases to zero, and then stays there. So $B$ moves forwards relative to $A$ the whole time, which is to say that $A$ slides backwards relative to $B$ the whole time and never forwards. Add after the sentence quoted: "One point of logic deserves a line here, since the case that decides the if and only if is the case in which the model's own assumption fails. The computation of $d$ assumes $A$ stays on the face throughout, so when $d \gt L$ it describes a motion the apparatus could not perform. It still settles the question, because the relative displacement is monotone: the motion is correctly described up to the first instant at which the relative displacement has magnitude $L$, and if $d \gt L$ that instant is reached, with $A$ then at the trailing edge, so $A$ does not stay on $B$. If $d \le L$ the assumption is never violated and the computation stands as it is."

The condition. By the definition given in the question, $A$ stays on $B$ exactly when that greatest magnitude is at most $L$, that is exactly when $d \le L$: $$\frac{J^2}{2\mu g M (M+m)} \;\le\; L \iff J^2 \;\le\; 2\mu g L M (M+m) \iff J \;\le\; \sqrt{2\mu g L M (M+m)} \;=\; J_0 .$$ The last equivalence is legitimate because $J \gt 0$ and $J_0 \gt 0$, so taking square roots of both sides of an inequality between positive quantities is reversible.

The case $J = J_0$. Then the slide is exactly $L$, so $A$ arrives exactly at the trailing edge of the upper face of $B$, and it arrives there at the very instant at which the relative sliding stops: it comes to relative rest on the brink. Any blow of impulse larger than $J_0$, however slightly larger, carries $A$ off the back. So the bound $J_0$ is attained and cannot be improved.

(iii) The step to supply here is the observation that the relative motion caused by a blow does not depend on the velocity the blocks already had, and everything else follows from part (ii).

Suppose a blow of impulse $j$ is delivered at an instant when $A$ and $B$ are moving with a common velocity $V$. By the argument of part (i), applied unchanged, the blow leaves $v_A = V$ and gives $v_B = V + \dfrac{j}{M}$. Hence immediately after that blow $$u \;=\; v_B - v_A \;=\; \frac{j}{M},$$ with no trace of $V$ in it. The relative deceleration $a$ carries no trace of $V$ either: it was derived in (i) from the friction forces, which involve only $\mu$, $m$, $g$ and $M$. So the relative motion after this blow is identical to the relative motion in part (ii) with $J$ replaced by $j$, and the calculation of (ii) applies word for word. The slide caused by this blow is $$\frac{(j/M)^2}{2a} \;=\; \frac{j^2}{2\mu g M (M+m)} .$$ (This is the mathematical content of the assumption that the floor is smooth. With no external horizontal force there is no preferred zero of velocity, so a description of the motion in terms of $u$ alone is complete.)

Apply this with $j = \dfrac{J}{n}$ to each of the $n$ blows in turn. The first blow is the case $V = 0$, and every later blow is delivered at an instant of common velocity by hypothesis, so each of the $n$ blows contributes a slide of $$\frac{(J/n)^2}{2\mu g M (M+m)} \;=\; \frac{1}{n^2}\cdot\frac{J^2}{2\mu g M(M+m)} \;=\; \frac{d}{n^2}.$$ By the last paragraph of part (ii), every one of these slides carries $A$ backwards relative to $B$, so they accumulate rather than partly cancelling, and the total distance slid is $$n \cdot \frac{d}{n^2} \;=\; \frac{d}{n}.$$ Since the relative displacement only ever moves one way, its greatest magnitude is again the total, so $A$ stays on $B$ if and only if $$\frac{d}{n} \;\le\; L \iff \frac{J^2}{2\mu g M (M+m)} \;\le\; nL \iff J^2 \le n J_0^2 \iff J \;\le\; \sqrt{n}\,J_0 ,$$ using $J \gt 0$ and $J_0 \gt 0$ at the last step as before.

Finally, let $J$ be given. Since $J_0 \gt 0$ we may choose an integer $n \ge \dfrac{J^2}{J_0^{2}}$; then $\sqrt{n}\,J_0 \ge J$ and $A$ stays on $B$. So there is no upper limit at all on the total impulse that can be delivered to $B$ without losing $A$, provided it is broken into enough blows and each blow waits for the sliding caused by its predecessor to stop.

Two remarks are worth making, because they say what has and has not changed. The total momentum delivered is $J$ whatever $n$ is, so the final common velocity is $\dfrac{J}{M+m}$ in every case: splitting the blow costs nothing in the outcome. What splitting changes is the sliding, and hence, since the energy dissipated by friction is $\mu m g$ times the distance slid, the energy wasted.

(iv) Now nothing is assumed about the timing, so in particular we may not assume that the sliding has stopped when a blow arrives. The construction that makes the calculation possible, and it is the step the candidate must supply unaided, is to name the relative velocity at each blow.

Notation. For $k = 1, 2, \dots, n$ let $w_k$ be the value of $u$ immediately before the $k$th blow, and set $w_{n+1} = 0$, the value of $u$ once all the motion has settled after the last blow. Let $$c \;=\; \frac{J}{nM}$$ be the jump in $u$ produced by one blow: by the argument of part (iii), a blow of impulse $\dfrac{J}{n}$ delivered to $B$ increases $v_B$ by $\dfrac{J}{nM}$ and leaves $v_A$ unchanged, whatever the blocks are doing at the time, so it increases $u$ by exactly $c$. Note that $w_1 = 0$, because the blocks start at rest and the first blow is delivered at $t_1 = 0$.

Step 1: $u$ is never negative. Initially $u = 0$. Each blow increases $u$ by $c \gt 0$. Between blows, if $u \gt 0$ then $u$ decreases at the constant rate $a$ until it reaches $0$, and once it reaches $0$ it stays at $0$, by the argument in part (ii) that no friction force is required to keep the blocks moving together. So $u$ can never pass below zero, and in particular $$w_k \;\ge\; 0 \qquad\text{for every } k .$$ Consequently $A$ slides backwards relative to $B$ throughout and never forwards, so the total distance slid is the sum of the distances slid over the successive intervals, and the greatest magnitude of the relative displacement at any instant is that same total.

Step 2: the slide over one interval. Consider the interval between the $k$th blow and the $(k+1)$th, for $1 \le k \le n-1$, and for $k = n$ the interval from the last blow onwards. At the start of the interval $u = w_k + c$; at the end $u = w_{k+1}$; and in between $u$ falls at the constant rate $a$ while it is positive, and is thereafter constant at $0$. In every case the relative displacement over the interval is $$\frac{(w_k+c)^2 - w_{k+1}^{2}}{2a},$$ by the same constant-acceleration relation used in part (ii). The two degenerate cases both behave: if $u$ reaches $0$ partway through the interval then $w_{k+1} = 0$ and the remainder of the interval contributes no relative displacement, so the expression still holds; and if two blows are delivered at the same instant then the interval has zero length, $w_{k+1} = w_k + c$, and the expression correctly gives $0$.

Step 3: sum and telescope. The total distance slid is therefore $$S \;=\; \frac{1}{2a}\sum_{k=1}^{n}\Big[(w_k+c)^2 - w_{k+1}^{2}\Big] \;=\; \frac{1}{2a}\left[\sum_{k=1}^{n}\big(w_k^2 + 2c\,w_k + c^2\big) \;-\; \sum_{k=2}^{n+1} w_k^{2}\right],$$ where the second sum has been re-indexed. The two sums of squares cancel except at their ends: what survives is $+\,w_1^2$ from the first and $-\,w_{n+1}^2$ from the second, and both of those are zero. Hence $$S \;=\; \frac{1}{2a}\left[n c^2 \;+\; 2c\sum_{k=1}^{n} w_k\right] \;=\; \frac{n c^2}{2a} \;+\; \frac{c}{a}\sum_{k=1}^{n} w_k .$$ The first term is the value found in part (iii), as it must be: $$\frac{n c^2}{2a} \;=\; \frac{n}{2}\cdot\frac{J^2}{n^2M^2}\cdot\frac{M}{\mu g (M+m)} \;=\; \frac{J^2}{2n\,\mu g M (M+m)} \;=\; \frac{d}{n}.$$ So $$S \;=\; \frac{d}{n} \;+\; \frac{c}{a}\sum_{k=1}^{n} w_k .$$

Step 4: the inequality and its equality case. Every $w_k \ge 0$ by Step 1, and $c \gt 0$ and $a \gt 0$, so the second term is non-negative and $$S \;\ge\; \frac{d}{n},$$ which is the required inequality. Equality holds if and only if $\displaystyle\sum_{k=1}^{n} w_k = 0$; and a sum of non-negative terms is zero if and only if every term is zero, so equality holds if and only if $w_k = 0$ for every $k$. That is, if and only if each blow is delivered at an instant when $u = 0$, which is to say at an instant when $A$ and $B$ are moving with a common velocity. Since $w_1 = 0$ automatically, this is a condition on the second and later blows only, and it is exactly the timing prescribed in part (iii). The two parts therefore agree, which is a useful check on both.

Step 5: the greatest total impulse. By Step 1 the greatest magnitude of the relative displacement is $S$, so $A$ stays on $B$ if and only if $S \le L$. For a given total impulse $J$ delivered in $n$ equal blows, the smallest value of $S$ available over all timings is $\dfrac{d}{n}$, by Step 4. Hence some timing keeps $A$ on $B$ if and only if $\dfrac{d}{n} \le L$, which by part (iii) is the condition $J \le \sqrt{n}\,J_0$. The greatest total impulse that can be delivered to $B$ in $n$ blows of equal impulse without $A$ leaving $B$ is therefore $$\sqrt{n}\,J_0 \;=\; \sqrt{2n\,\mu g L M (M+m)} .$$ The equality case says something the inequality alone does not. When the total impulse is exactly $\sqrt{n}\,J_0$ we need $S = \dfrac{d}{n}$, so by Step 4 the timing is forced: every blow after the first must be delayed until the sliding caused by its predecessor has entirely stopped, and $A$ then finishes exactly at the trailing edge, arriving there as the sliding ends. Delivering that same total impulse even slightly sooner makes $S$ strictly greater than $\dfrac{d}{n}$ and sends $A$ off the back. At the maximum, patience is not merely the best policy: it is the only one.

Choosing a description of the experiment.

A row is a sequence of $a+b$ counters of which $a$ are red, and counters of one colour are indistinguishable, so a row is exactly a word of length $a+b$ in the two letters $\mathrm{R}$ and $\mathrm{B}$ containing $a$ letters $\mathrm{R}$. A row is determined by the set of positions holding the red counters, so there are $\binom{a+b}{a}$ rows, and the question declares them equally likely. Every probability asked for is therefore (number of rows with the property) divided by $\binom{a+b}{a}$, and the whole question is a counting question.

The first genuine decision is which colour to describe a row by. We describe a row by saying where the red counters sit relative to the blue ones. This is a choice, not a consequence, and it is made because it is the red blocks that parts (i) and (ii) ask about: laying the blue counters out first gives a fixed frame, and the red counters are then dropped into it.

Write the $b$ blue counters in a row. They create $b+1$ gaps: one to the left of the first blue counter, one between each of the $b-1$ pairs of consecutive blue counters, and one to the right of the last blue counter. Label them $g_0, g_1, \dots, g_b$ from left to right. Given a row, let $r_i$ be the number of red counters lying in gap $g_i$, so that $r_i \ge 0$ and $r_0 + r_1 + \cdots + r_b = a$.

Lemma 1. Rows correspond one to one with $(b+1)$-tuples $(r_0, r_1, \dots, r_b)$ of non-negative integers with $r_0 + \cdots + r_b = a$.

Why. The map just described sends a row to such a tuple. It has an inverse: given a tuple, write $r_0$ red counters, then a blue counter, then $r_1$ red counters, then a blue counter, and so on, finishing with $r_b$ red counters. This uses each of the $b$ blue counters once and $r_0 + \cdots + r_b = a$ red counters, so it is a row, and the two constructions undo one another. Hence the correspondence is a bijection.

Lemma 2. Under Lemma 1, the red blocks of a row are exactly the non-empty gaps. In particular the number of red blocks is the number of indices $i$ with $r_i \ge 1$.

Why. Two red counters lying in the same gap have only red counters between them, so no blue counter separates them and they lie in the same block. Two red counters lying in different gaps have at least one blue counter between them, so they lie in different blocks. Therefore the red counters of one non-empty gap form a set of consecutive red counters which cannot be enlarged, because whatever stands immediately outside it is a blue counter or nothing at all: that is a block. Distinct non-empty gaps give distinct blocks, and every red counter lies in some gap, so every red block arises this way exactly once.

(i)

No two red counters are adjacent if and only if no gap holds two or more red counters. Both directions matter and both are short. If some gap held two or more red counters, two of them would be next to each other in the row, so two red counters would be adjacent. Conversely, if two red counters are adjacent, then no blue counter lies between them, so they lie in the same gap and that gap holds at least two red counters.

So, by Lemma 1, the rows in which no two red counters are adjacent correspond one to one with the $(b+1)$-tuples $(r_0, \dots, r_b)$ in which every $r_i$ is $0$ or $1$ and the total is $a$. Such a tuple is the same thing as a choice of which $a$ of the $b+1$ gaps hold a red counter, that is, an $a$-element subset of a set of size $b+1$. There are $\binom{b+1}{a}$ of these, so the number of rows is $\binom{b+1}{a}$.

The degenerate case is worth a sentence. If $a \gt b+1$ then there is no such subset, and indeed no such row, since $a$ red counters cannot be spread over $b+1$ gaps one at a time; the stated convention makes $\binom{b+1}{a}=0$, so the formula is correct there too. If $a=1$ the condition is vacuous, and the formula gives $\binom{b+1}{1}=b+1$, which is the total number of rows, as it must be.

For $a=3$ and $b=5$ the number of such rows is $\binom{6}{3}=20$, and the total number of rows is $\binom{8}{3}=56$, so $$\mathrm{P}(\text{no two red counters adjacent}) = \frac{20}{56} = \frac{5}{14}.$$

(ii)

Part (i) counted the rows in which every non-empty gap holds exactly one red counter. The general case has to allow a gap to hold several, and that is a second and genuinely different count: how many ways are there of splitting $a$ into $k$ positive parts in a definite order.

Lemma 3 (the count of compositions). Let $a$ and $k$ be positive integers. The number of $k$-tuples $(c_1, c_2, \dots, c_k)$ of positive integers with $c_1 + c_2 + \cdots + c_k = a$ is $\binom{a-1}{k-1}$.

Why. Write $a$ as a row of $a$ units, and note the $a-1$ spaces between consecutive units. Choose $k-1$ of those spaces and cut there. The cuts divide the units into $k$ consecutive groups, each non-empty because a group can be empty only if two cuts are made in the same space, which a choice of $k-1$ distinct spaces does not allow; reading the group sizes from left to right gives a $k$-tuple of positive integers with sum $a$. Conversely a $k$-tuple determines the cuts: cut after unit number $c_1 + \cdots + c_j$ for $j = 1, \dots, k-1$, and these $k-1$ positions are distinct spaces, strictly between $0$ and $a$, precisely because every $c_j \ge 1$. The two constructions are mutually inverse, so the count is the number of $(k-1)$-element subsets of a set of size $a-1$, namely $\binom{a-1}{k-1}$. When $k \gt a$ there is no such tuple, since $k$ positive integers sum to at least $k$, and the convention gives $\binom{a-1}{k-1}=0$ in agreement.

Now fix $k \ge 1$. By Lemma 2, a row has exactly $k$ red blocks if and only if exactly $k$ of the $b+1$ gaps are non-empty. Such a row is determined by two pieces of data, and determines them:

1. the set $S$ of non-empty gaps, which is a $k$-element subset of the $b+1$ gaps; 2. the numbers of red counters in those gaps, read from left to right, which is a $k$-tuple of positive integers with sum $a$.

Conversely, any such pair $(S, (c_1, \dots, c_k))$ gives back one row: put $c_j$ red counters into the $j$th smallest gap in $S$ and none into the others, which is a tuple as in Lemma 1, hence a row, and it has exactly $k$ non-empty gaps, hence exactly $k$ red blocks. The two constructions are mutually inverse, so this is a bijection, and the two choices are independent of one another: any subset may be paired with any tuple. Hence the number of rows with exactly $k$ red blocks is $$\binom{b+1}{k} \times \binom{a-1}{k-1} = \binom{a-1}{k-1}\binom{b+1}{k},$$ as required. Note that the formula correctly returns $0$ when $k \gt b+1$ (too few gaps) and when $k \gt a$ (too few red counters).

Dividing by the number of rows, $$\mathrm{P}(\text{exactly } k \text{ red blocks}) = \frac{\binom{a-1}{k-1}\binom{b+1}{k}}{\binom{a+b}{a}}.$$

Consistency with part (i). A row has exactly $a$ red blocks if and only if the $a$ red counters lie in $a$ different gaps, that is, if and only if every red block consists of a single counter, that is, if and only if no two red counters are adjacent. Putting $k=a$ in the formula gives $\binom{a-1}{a-1}\binom{b+1}{a} = \binom{b+1}{a}$, which is exactly the count of part (i). This is a check on the general formula, not a new result.

As a numerical check, take $a=3$ and $b=2$, where there are $\binom{5}{3}=10$ rows. The formula gives $\binom{2}{0}\binom{3}{1}=3$ rows with one red block, $\binom{2}{1}\binom{3}{2}=6$ with two, and $\binom{2}{2}\binom{3}{3}=1$ with three, totalling $10$. Listing the ten rows confirms this: $\mathrm{RRRBB}$, $\mathrm{BRRRB}$ and $\mathrm{BBRRR}$ have one red block, $\mathrm{RBRBR}$ has three, and the remaining six have two.

(iii)

This part is about blocks of both colours, so the gap description of parts (i) and (ii) is no longer the natural frame. What replaces it is the following structural fact, which is the step the question does not signpost.

Lemma 4 (blocks alternate). In any row, consecutive blocks have different colours.

Why. Suppose blocks number $j$ and $j+1$ had the same colour. They are next to each other in the row, so the counter immediately to the right of block $j$ is the leftmost counter of block $j+1$, and it has the same colour as block $j$. That contradicts the requirement in the definition that a block cannot be enlarged.

It follows that the colour of block $j$ is the colour of block $1$ when $j$ is odd, and the other colour when $j$ is even; this is an immediate induction on $j$ using Lemma 4.

Since $a \ge 1$ and $b \ge 1$, both colours occur, so every row has at least two blocks. Suppose a row has exactly $2m$ blocks. By the previous paragraph, blocks $1, 3, \dots, 2m-1$ all have the colour of block $1$, and blocks $2, 4, \dots, 2m$ all have the other colour. There are $m$ blocks of each kind, so the row has exactly $m$ red blocks and exactly $m$ blue blocks.

Now split according to the colour of the first block. Every row has a first block and that block has exactly one colour, so the two classes below are disjoint and together contain every row with $2m$ blocks. This split is a choice, and it is the right one because, once the sizes of the blocks of each colour are known, the colour of the first block is the only thing still undetermined.

Class 1: the first block is red. Then reading from the left the row is $$\underbrace{\mathrm{R}\cdots\mathrm{R}}_{c_1}\ \underbrace{\mathrm{B}\cdots\mathrm{B}}_{d_1}\ \underbrace{\mathrm{R}\cdots\mathrm{R}}_{c_2}\ \underbrace{\mathrm{B}\cdots\mathrm{B}}_{d_2}\ \cdots\ \underbrace{\mathrm{R}\cdots\mathrm{R}}_{c_m}\ \underbrace{\mathrm{B}\cdots\mathrm{B}}_{d_m},$$ where every $c_j$ and every $d_j$ is a positive integer (a block is non-empty), $c_1 + \cdots + c_m = a$ and $d_1 + \cdots + d_m = b$. The row determines the two tuples, since the blocks of a row are determined by the row; and the two tuples determine the row, since the display above reconstructs it. Choosing $(c_1, \dots, c_m)$ and choosing $(d_1, \dots, d_m)$ are independent choices, so by Lemma 3, applied once to $a$ and once to $b$, this class contains $$\binom{a-1}{m-1}\binom{b-1}{m-1}$$ rows. Replace with: "This is where Lemma 3 is consumed: the composition count established in part (ii) is used twice here, once for $a$ and once for $b$. Note that it is the lemma and not the conclusion of part (ii) that is reused, since the gap frame of parts (i) and (ii) plays no role at all in this part."

Class 2: the first block is blue. The same argument with the colours interchanged gives $\binom{b-1}{m-1}\binom{a-1}{m-1}$ rows, which is the same number.

Adding the two disjoint classes, the number of rows with exactly $2m$ blocks altogether is $$2\binom{a-1}{m-1}\binom{b-1}{m-1}.$$

Check with $a=3$, $b=2$. For $m=1$ the formula gives $2\binom{2}{0}\binom{1}{0}=2$, and indeed only $\mathrm{RRRBB}$ and $\mathrm{BBRRR}$ have two blocks. For $m=2$ it gives $2\binom{2}{1}\binom{1}{1}=4$, and indeed $\mathrm{RRBRB}$, $\mathrm{RBRRB}$, $\mathrm{BRRBR}$ and $\mathrm{BRBRR}$ have four blocks. For $m=3$ it gives $2\binom{2}{2}\binom{1}{2}=0$, correctly, since six blocks would need three blue blocks and there are only two blue counters.

(iv)(a)

Let $R$ be the number of blocks in a row; as noted above $R \ge 2$. By the consequence of Lemma 4, block $R$ has the colour of block $1$ when $R$ is odd, and the other colour when $R$ is even. The first counter of the row belongs to block $1$ and so has the colour of block $1$; the last counter belongs to block $R$ and so has the colour of block $R$. Therefore

the first and last counters have different colours $\iff$ blocks $1$ and $R$ have different colours $\iff$ $R$ is even.

Both implications are contained in this chain, because each link is an equivalence rather than a one-way implication: the first link holds because the first and last counters carry exactly the colours of the first and last blocks, and the second because the colour of block $R$ is determined by the parity of $R$ alone.

(iv)(b)

Let $E$ be the set of rows containing an even number of blocks. We count $E$ in two ways. The identity is then forced, which is the point of the part: the two counts are of the same set, so they are equal.

First count, through part (iii). For each positive integer $m$ let $E_m$ be the set of rows with exactly $2m$ blocks. A row has exactly one number of blocks, so the sets $E_m$ are pairwise disjoint. Their union is $E$: a row in $E$ has an even number of blocks, and that number is $2m$ for exactly one positive integer $m$, positive because $R \ge 2$. So the case split is both disjoint and exhaustive, and $$|E| = \sum_{m \ge 1} |E_m| = \sum_{m \ge 1} 2\binom{a-1}{m-1}\binom{b-1}{m-1}.$$ Every term with $m \gt a$ vanishes, since then $m-1 \gt a-1$ and $\binom{a-1}{m-1}=0$; so the sum may be written as the finite sum $$|E| = 2\sum_{m=1}^{a}\binom{a-1}{m-1}\binom{b-1}{m-1}.$$

Second count, through part (a). By part (a), $E$ is exactly the set of rows whose first and last counters have different colours. Split that condition according to which way round the two colours occur: either the first counter is red and the last is blue, or the first is blue and the last is red. These two cases are disjoint, since the first counter has one colour, and together they are the condition. In the first case the two end positions are fixed, and the remaining $a+b-2$ positions carry the remaining $a-1$ red counters and $b-1$ blue counters; such a row is determined by which $a-1$ of those $a+b-2$ positions are red, so there are $\binom{a+b-2}{a-1}$ of them. The second case gives the same count, again $\binom{a+b-2}{a-1}$, because there too the middle $a+b-2$ positions carry $a-1$ red counters. Hence $$|E| = 2\binom{a+b-2}{a-1}.$$

The identity. Equating the two counts of $|E|$ and dividing by $2$, $$\sum_{m=1}^{a}\binom{a-1}{m-1}\binom{b-1}{m-1} = \binom{a+b-2}{a-1}$$ for all positive integers $a$ and $b$, as required.

The probability. Dividing $|E|$ by the number of rows, $$\mathrm{P}(E) = \frac{2\binom{a+b-2}{a-1}}{\binom{a+b}{a}}.$$ Now $$\frac{\binom{a+b-2}{a-1}}{\binom{a+b}{a}} = \frac{(a+b-2)!}{(a-1)!\,(b-1)!}\cdot\frac{a!\,b!}{(a+b)!} = \frac{a!}{(a-1)!}\cdot\frac{b!}{(b-1)!}\cdot\frac{(a+b-2)!}{(a+b)!} = \frac{ab}{(a+b)(a+b-1)},$$ so $$\mathrm{P}(E) = \frac{2ab}{(a+b)(a+b-1)},$$ which is what was to be shown.

A tempting step that is not valid. One might try to reach this probability by saying that the first counter is red with probability $\frac{a}{a+b}$ and the last is blue with probability $\frac{b}{a+b}$, and multiplying. That treats the two end counters as independent, and they are not: knowing the first counter is red leaves only $a-1$ red counters among the other $a+b-1$ counters, so the conditional probability that the last is blue is $\frac{b}{a+b-1}$, not $\frac{b}{a+b}$. The correct version of this route gives $2 \cdot \frac{a}{a+b} \cdot \frac{b}{a+b-1}$, which agrees with the count above; the incorrect one gives $\frac{2ab}{(a+b)^2}$, which is wrong for every $a$ and $b$.

Checks at small values.

$a=b=1$: the two rows are $\mathrm{RB}$ and $\mathrm{BR}$, each with two blocks, so $\mathrm{P}(E)=1$, and the formula gives $\frac{2 \cdot 1 \cdot 1}{2 \cdot 1}=1$. The identity reads $\binom{0}{0}\binom{0}{0}=1$ on the left and $\binom{0}{0}=1$ on the right.

$a=2$, $b=1$: the three rows $\mathrm{RRB}$, $\mathrm{RBR}$, $\mathrm{BRR}$ have $2$, $3$ and $2$ blocks, so $\mathrm{P}(E)=\frac{2}{3}$, and the formula gives $\frac{2\cdot 2\cdot 1}{3 \cdot 2}=\frac{2}{3}$. The identity reads $\binom{1}{0}\binom{0}{0} + \binom{1}{1}\binom{0}{1} = 1 + 0 = 1$ on the left and $\binom{1}{1}=1$ on the right.

$a=3$, $b=2$: Replace with: "listing the ten rows in dictionary order with $\mathrm{R}$ before $\mathrm{B}$, namely $\mathrm{RRRBB}$, $\mathrm{RRBRB}$, $\mathrm{RRBBR}$, $\mathrm{RBRRB}$, $\mathrm{RBRBR}$, $\mathrm{RBBRR}$, $\mathrm{BRRRB}$, $\mathrm{BRRBR}$, $\mathrm{BRBRR}$, $\mathrm{BBRRR}$, their numbers of blocks are $2, 4, 3, 4, 5, 3, 3, 4, 4, 2$ respectively"., so six of them lie in $E$ and $\mathrm{P}(E)=\frac{3}{5}$; the formula gives $\frac{2 \cdot 3 \cdot 2}{5 \cdot 4}=\frac{3}{5}$. The identity reads $\binom{2}{0}\binom{1}{0}+\binom{2}{1}\binom{1}{1}+\binom{2}{2}\binom{1}{2} = 1+2+0 = 3$ on the left and $\binom{3}{2}=3$ on the right.

The degenerate case, and why the question excludes it. If $b$ were $0$ there would be a single row, with one block, so no row would have an even number of blocks; and the formula of part (iii) would involve $\binom{-1}{m-1}$, which is not defined by the convention in the stem. This is why $a$ and $b$ are required to be positive integers throughout. Part (i) alone survives $b=0$: it then reads $\binom{1}{a}$, which is $1$ when $a=1$ and $0$ when $a \ge 2$, both correct.

Notation, and two small facts isolated first.

Write $H_m$ for the rung occupied at the end of round $m$, so $H_0=0$ and, for $m \geqslant 1$, $H_m=H_{m-1}+1$ if round $m$ is an upward move and $H_m=0$ if round $m$ is a reset. Every round is one or the other, never both and never neither, so this is a complete description of the process.

(L1) The counter cannot skip a rung. If $H_m=r$ with $r \geqslant 1$, then round $m$ cannot have been a reset, since a reset gives $H_m=0$; so $H_m=H_{m-1}+1$ and therefore $H_{m-1}=r-1$. Applying this repeatedly, $H_{m-j}=r-j$ for $j=0,1,\ldots,r$. Hence every one of the rungs $0,1,\ldots,r$ is occupied at the end of one of the rounds $m-r,\,m-r+1,\,\ldots,\,m$. In particular, if the counter is ever on a rung numbered $n$ or higher, then rung $n$ itself has been occupied at the end of some round at or before that one.

(L2) $T_{n-1} \leqslant T_n-1$ for $n \geqslant 1$. By definition $H_{T_n}=n \geqslant 1$, so (L1) gives $H_{T_n-1}=n-1$. Thus rung $n-1$ is occupied at the end of round $T_n-1$, and since $T_{n-1}$ is by definition the least round at whose end rung $n-1$ is occupied, $T_{n-1} \leqslant T_n-1$.

(i)

The waiting time for a first success. The event $N=k$ says that the first $k-1$ trials fail and the $k$th succeeds. The trials are independent, so the probabilities multiply: $$P(N=k)=(1-\theta)^{k-1}\theta \qquad (k=1,2,3,\ldots).$$

To evaluate $E(N)=\sum_{k \geqslant 1}k\theta(1-\theta)^{k-1}$ we need $\sum_{k \geqslant 1}kx^{k-1}$ with $x=1-\theta$, so that $0 \lt x \lt 1$. Here is a choice of method: form the partial sum, multiply it by $x$ and subtract. This works because the terms are a geometric progression multiplied by a linear factor. (Differentiating the geometric series term by term gives the same answer, but term-by-term differentiation of an infinite series is itself a step needing justification, so the finite calculation below is the safer route, and it delivers a finite-sum formula that is needed again in part (iv).) Put $$S_N(x)=\sum_{k=1}^{N}kx^{k-1}.$$ Then $$S_N(x)-xS_N(x)=\sum_{k=1}^{N}kx^{k-1}-\sum_{k=1}^{N}kx^{k}=\sum_{j=0}^{N-1}(j+1)x^{j}-\sum_{k=1}^{N}kx^{k}=\sum_{j=0}^{N-1}x^{j}-Nx^{N},$$ where the middle step reindexes the first sum by $j=k-1$, and the last step cancels the terms $jx^{j}$ for $j=1,\ldots,N-1$, leaving the $j=0$ term of the first sum, the constant terms, and the unmatched $Nx^{N}$. Summing the geometric progression, $$(1-x)S_N(x)=\frac{1-x^{N}}{1-x}-Nx^{N}, \qquad\text{so}\qquad S_N(x)=\frac{1-(N+1)x^{N}+Nx^{N+1}}{(1-x)^{2}}. \qquad (*)$$

Now let $N \to \infty$. Since $0 \lt x \lt 1$ we may write $x=1/(1+h)$ with $h \gt 0$, and the binomial theorem gives $(1+h)^{N} \geqslant \tfrac{1}{2}N(N-1)h^{2}$ for $N \geqslant 2$, every term of the expansion being positive. Hence $$0 \lt Nx^{N}=\frac{N}{(1+h)^{N}} \leqslant \frac{2N}{N(N-1)h^{2}}=\frac{2}{(N-1)h^{2}} \longrightarrow 0 .$$ So $Nx^{N} \to 0$, and a fortiori $x^{N} \to 0$. Therefore $S_N(x)$ converges as $N \to \infty$, and $$\sum_{k=1}^{\infty}kx^{k-1}=\frac{1}{(1-x)^{2}} \qquad (0 \lt x \lt 1).$$ Consequently $$E(N)=\theta\sum_{k=1}^{\infty}k(1-\theta)^{k-1}=\frac{\theta}{\bigl(1-(1-\theta)\bigr)^{2}}=\frac{\theta}{\theta^{2}}=\frac{1}{\theta}.$$ As a check that nothing has been lost, $\sum_{k \geqslant 1}P(N=k)=\theta\cdot\dfrac{1}{1-(1-\theta)}=1$, so $N$ is finite with probability $1$.

The batching argument. Fix $n \geqslant 1$ and let $A_j$ be the event that all $n$ rounds of the $j$th batch are upward moves. Different batches involve disjoint sets of rounds, and the rounds are independent, so $A_1,A_2,A_3,\ldots$ are independent events, each of probability $p^{\,n}$.

Suppose $A_j$ occurs, and let $r=H_{(j-1)n}$ be the rung occupied at the start of that batch, with $H_0=0$ when $j=1$. There are two cases, and they are exhaustive.

If $r \geqslant n$, then by (L1) rung $n$ has already been occupied at the end of some round at or before round $(j-1)n$.

If $r \lt n$, then the $n$ rounds of the batch are all upward moves, so $H_{(j-1)n+i}=r+i$ for $i=1,2,\ldots,n$. Taking $i=n-r$, which satisfies $1 \leqslant n-r \leqslant n$ because $0 \leqslant r \lt n$, gives $H_{(j-1)n+(n-r)}=n$.

Either way rung $n$ is occupied at the end of some round no later than round $jn$, which is the required claim. The first case is the one it is easy to forget: the counter may already have climbed past rung $n$ before the batch begins, and a proof that only tracks the batch itself has a hole in it.

Let $B$ be the least $j$ for which $A_j$ occurs. Because the events $A_j$ are independent, each of probability $p^{\,n}$, the index $B$ is exactly the waiting time for a first success studied above, with $\theta=p^{\,n}$; and $0 \lt p^{\,n} \lt 1$ because $0 \lt p \lt 1$. Hence $$P(B \gt M)=P(\text{none of } A_1,\ldots,A_M \text{ occurs})=(1-p^{\,n})^{M} \longrightarrow 0 \quad (M \to \infty),$$ the middle equality using independence. So $P(B \lt \infty)=1$, and by the previous paragraph $T_n \leqslant nB$ whenever $B$ is finite. Therefore $T_n$ exists with probability $1$. Moreover the inequality $T_n \leqslant nB$ holds with probability $1$, so $$a_n=E(T_n) \leqslant nE(B)=\frac{n}{p^{\,n}}=np^{-n} \lt \infty .$$

This last sentence is a genuine strengthening of the one before it, not a restatement: a random variable can be finite with probability $1$ and still have infinite expectation, so a bound on the expectation has to be obtained separately. It is the finiteness of $a_n$, and not merely the existence of $T_n$, that part (ii) will need.

One special case is worth recording now. When $n=1$, $T_1$ is precisely the number of rounds up to and including the first upward move, which is the waiting time for a first success with $\theta=p$. So in fact $a_1=1/p$ exactly, not merely $a_1 \leqslant 1/p$, and part (ii) uses this as a check.

(ii)

Rung $n-1$ comes first. This is (L2). Since $H_{T_n}=n \geqslant 1$, round $T_n$ was an upward move, so $H_{T_n-1}=n-1$; and $T_{n-1}$ is the least round at whose end rung $n-1$ is occupied, so $T_{n-1} \leqslant T_n-1$. In particular round $T_{n-1}+1$ exists and is no later than round $T_n$.

Choosing what to condition on. We condition on round $T_{n-1}+1$, the round immediately after the counter first reaches rung $n-1$. This is a choice, and it is the choice the question turns on. Conditioning on round $1$ instead leads nowhere useful: after one upward move the counter is on rung $1$, and the expected further time to reach rung $n$ from rung $1$ is not $a_{n-1}$, because a reset from rung $1$ sends the counter to rung $0$ rather than to a rung one step below its target. For example, with $p=\tfrac12$ and $n=2$, the expected time to get from rung $1$ to rung $2$ is $1+\tfrac12 a_2=1+3=4$, whereas $a_1=2$. Conditioning at $T_{n-1}$ avoids the difficulty, because from rung $n-1$ the counter is exactly one upward move short of the target, and a reset returns it to rung $0$, which is where it started.

Why the supplied fact applies. The event $T_{n-1}=s$ says that rung $n-1$ is occupied at the end of round $s$ and at the end of no earlier round. Whether that holds is decided by the outcomes of rounds $1,\ldots,s$ alone. So $T_{n-1}$ is a round number of exactly the kind described in the fact supplied with the question, and the outcomes of rounds $T_{n-1}+1,\,T_{n-1}+2,\,\ldots$ are independent of everything that came before and form a fresh copy of the whole process.

The case split. Exactly one of the following happens at round $T_{n-1}+1$. The two cases are mutually exclusive and exhaustive because a round is by definition either an upward move or a reset, never both and never neither.

Case U, of probability $p$. The round is an upward move. The counter goes from rung $n-1$ to rung $n$, so $T_n=T_{n-1}+1$.

Case R, of probability $1-p$. The round is a reset. At the end of it the counter is on rung $0$, exactly as at the very start. Insert before the sentence quoted: "Note first that rung $n$ has not yet been occupied. By L2 we have $T_n \geqslant T_{n-1}+1$, so it was not occupied before round $T_{n-1}+1$; and in this case round $T_{n-1}+1$ is a reset, so $H_{T_{n-1}+1}=0 \neq n$, and therefore $T_n \gt T_{n-1}+1$. At the end of round $T_{n-1}+1$ the counter is thus on rung $0$ with rung $n$ still unvisited, which is exactly its state at the end of round $0$."

The probabilities attached to the two cases are the unconditional $p$ and $1-p$, and this too is the supplied fact at work: round $T_{n-1}+1$ is independent of the rounds that determined $T_{n-1}$, so knowing when the counter first reached rung $n-1$ tells us nothing about what happens next.

Taking expectations over the two cases, $$a_n=p\bigl(a_{n-1}+1\bigr)+(1-p)\bigl(a_{n-1}+1+a_n\bigr)=a_{n-1}+1+(1-p)a_n \qquad (n \geqslant 1),$$ the last step using $p+(1-p)=1$. Both cases contribute $a_{n-1}+1$, being the expected time to reach rung $n-1$ plus the one round we are conditioning on; only Case R contributes the extra $a_n$.

The step that must be justified, and the trap in it. We now want to subtract $(1-p)a_n$ from both sides. That is legitimate only because $a_n$ is a finite real number, which is exactly what part (i) established. Had $a_n$ been infinite, the displayed equation would have read $\infty=\infty$ and would have said nothing at all, while the cancellation would still have produced a plausible-looking formula. This is the one place in the question where a step that looks like routine algebra needs an external input. With finiteness in hand, $$pa_n=a_{n-1}+1, \qquad\text{that is}\qquad a_n=\frac{1+a_{n-1}}{p} \quad (n \geqslant 1), \qquad a_0=0 .$$

Solving the recurrence. Claim: $a_n=\sum_{k=1}^{n}p^{-k}$ for every $n \geqslant 0$, an empty sum being $0$. Base case: $a_0=0$, which is the empty sum. Inductive step: if $a_{n-1}=\sum_{k=1}^{n-1}p^{-k}$ for some $n \geqslant 1$, then $$a_n=\frac{1+a_{n-1}}{p}=\frac{1}{p}+\sum_{k=1}^{n-1}\frac{1}{p^{\,k+1}}=\frac{1}{p}+\sum_{k=2}^{n}\frac{1}{p^{\,k}}=\sum_{k=1}^{n}\frac{1}{p^{\,k}},$$ which is the claim for $n$. So it holds for every $n \geqslant 0$ by induction. Summing this geometric progression, whose first term is $p^{-1}$ and whose common ratio is $p^{-1} \neq 1$ because $p \neq 1$, $$a_n=\frac{p^{-1}\left(p^{-n}-1\right)}{p^{-1}-1}=\frac{p^{-n}-1}{1-p}=\frac{1-p^{\,n}}{p^{\,n}(1-p)} ,$$ the last step multiplying numerator and denominator by $p^{\,n}$.

Checks. At $n=0$ the formula gives $0$, as it must. At $n=1$ it gives $\dfrac{1-p}{p(1-p)}=\dfrac{1}{p}$, which agrees with part (i), where $T_1$ was identified as the waiting time for the first upward move. At $n=2$ it gives $p^{-1}+p^{-2}$, and directly $a_2=(1+a_1)/p=(1+1/p)/p$, the same thing. For $p=\tfrac12$ these read $a_1=2$ and $a_2=6$.

The limit as $p \to 1^{-}$. The formula as written is of the form $0/0$ at $p=1$, so it must be rewritten before the limit is taken; this is the small unsignposted move in this part. Using $1-p^{\,n}=(1-p)\left(1+p+\cdots+p^{\,n-1}\right)$, $$a_n=\frac{1+p+p^{2}+\cdots+p^{\,n-1}}{p^{\,n}},$$ which has no vanishing factor left in it. Letting $p \to 1^{-}$ with $n$ fixed gives $$\lim_{p \to 1^{-}}a_n=\frac{n}{1}=n .$$ That is what one expects: when $p$ is close to $1$ resets are very rare, so the counter climbs one rung per round and needs about $n$ rounds to reach rung $n$. At the other end, $a_n \to \infty$ as $p \to 0^{+}$ for every $n \geqslant 1$, which is also as expected.

The case $p=\tfrac12$. Here $a_n=\sum_{k=1}^{n}2^{k}=2^{\,n+1}-2$. We need $2^{\,n+1}-2 \gt 10^{6}$, that is $2^{\,n+1} \gt 1000002$. Since $2^{19}=524288$ and $2^{20}=1048576$, the least admissible value of $n+1$ is $20$, so the least value of $n$ is $$n=19 ,$$ with $a_{19}=2^{20}-2=1048574 \gt 10^{6}$, while $a_{18}=2^{19}-2=524286 \lt 10^{6}$. It is worth pausing on the size of this. Nineteen rungs, and the counter needs over a million rounds on average, because each extra rung multiplies the expected time by $1/p$: the cost of one more rung is multiplicative, not additive.

(iii)

The construction this part needs. Read the process backwards from round $m$ rather than forwards from round $1$. Forwards, $H_m$ appears to depend on the whole history; backwards, it depends only on the last few rounds. Precisely, let $R$ be the length of the unbroken run of upward moves that ends with round $m$: that is, $R$ is the largest $r$ with $0 \leqslant r \leqslant m$ such that rounds $m-r+1,\,m-r+2,\,\ldots,\,m$ are all upward moves, with $R=0$ when round $m$ is a reset.

Claim: $H_m=R$. Suppose first that $R=r$ with $1 \leqslant r \lt m$. Then rounds $m-r+1,\ldots,m$ are all upward moves and, by the maximality of $r$, round $m-r$ is a reset. A reset puts the counter on rung $0$, so $H_{m-r}=0$, and the $r$ upward moves that follow give $H_m=0+r=r$. If $R=m$ then all $m$ rounds are upward moves, and since $H_0=0$ we get $H_m=m=R$. If $R=0$ then round $m$ is a reset, so $H_m=0=R$. In every case $H_m=R$, and the three cases are exhaustive.

The distribution. Let $0 \leqslant k \leqslant m-1$. By the claim, $H_m=k$ holds exactly when rounds $m-k+1,\ldots,m$ are all upward moves and round $m-k$ is a reset. That is a condition on $k+1$ distinct rounds, namely rounds $m-k,\,m-k+1,\,\ldots,\,m$, all of which lie in $\{1,\ldots,m\}$ because $k \leqslant m-1$. The rounds are independent, so the probabilities multiply: $$P(H_m=k)=(1-p)p^{\,k} \qquad (0 \leqslant k \leqslant m-1).$$ The remaining case is $k=m$, which by the claim holds exactly when all $m$ rounds are upward moves, so $$P(H_m=m)=p^{\,m}.$$ The case $k=m$ genuinely is different, and that is the trap here: there is no round $0$ to be a reset, so the factor $1-p$ is absent.

Verification. Summing the geometric progression, $$\sum_{k=0}^{m-1}(1-p)p^{\,k}+p^{\,m}=(1-p)\cdot\frac{1-p^{\,m}}{1-p}+p^{\,m}=\left(1-p^{\,m}\right)+p^{\,m}=1 ,$$ as required. Note that had the formula $(1-p)p^{\,k}$ been used for $k=m$ as well, the total would have come to $1-p^{\,m+1}$, which is not $1$; the verification is what catches that error.

Small cases. For $m=1$: $P(H_1=0)=1-p$ and $P(H_1=1)=p$, which is right, since one round either lifts the counter to rung $1$ or resets it. Replace with: "For $m=2$ the four outcomes $\mathrm{RR}$, $\mathrm{RU}$, $\mathrm{UR}$, $\mathrm{UU}$ have probabilities $(1-p)^{2}$, $(1-p)p$, $p(1-p)$, $p^{2}$ and give rungs $0, 1, 0, 2$. Two of them give rung $0$, so $P(H_2=0)=(1-p)^{2}+p(1-p)=1-p$, while $P(H_2=1)=(1-p)p$ and $P(H_2=2)=p^{2}$, in agreement with the general formula, and the three sum to $1$." For $m=0$ the process has not started, $H_0=0$ with probability $1$, consistent with reading the formulas at $m=0$ as the single case $k=m=0$ with probability $p^{0}=1$.

(iv)

The expectation. Using the distribution from part (iii), and separating the exceptional term $k=m$, $$E(H_m)=\sum_{k=0}^{m-1}k(1-p)p^{\,k}+mp^{\,m}=(1-p)p\sum_{k=1}^{m-1}kp^{\,k-1}+mp^{\,m},$$ where the $k=0$ term has been dropped because it is zero and a factor $p$ has been taken out to expose the shape of $(*)$. For $m \geqslant 2$, apply $(*)$ from part (i) with $x=p$ and $N=m-1$: $$\sum_{k=1}^{m-1}kp^{\,k-1}=\frac{1-mp^{\,m-1}+(m-1)p^{\,m}}{(1-p)^{2}} .$$ Hence $$E(H_m)=\frac{p\left(1-mp^{\,m-1}+(m-1)p^{\,m}\right)}{1-p}+mp^{\,m}=\frac{p-mp^{\,m}+(m-1)p^{\,m+1}+mp^{\,m}(1-p)}{1-p}.$$ In the numerator, $-mp^{\,m}+mp^{\,m}=0$ and $(m-1)p^{\,m+1}-mp^{\,m+1}=-p^{\,m+1}$, so $$E(H_m)=\frac{p-p^{\,m+1}}{1-p}=\frac{p\left(1-p^{\,m}\right)}{1-p} .$$ The cases $m=0$ and $m=1$ are immediate and agree with this formula: $E(H_0)=0$ and $E(H_1)=p$.

Checks. At $m=2$ the formula gives $p(1+p)=p+p^{2}$, and directly $0 \cdot (1-p)+1 \cdot (1-p)p+2p^{2}=p-p^{2}+2p^{2}=p+p^{2}$. At $m=3$ the formula gives $p+p^{2}+p^{3}$, and directly $(1-p)p+2(1-p)p^{2}+3p^{3}=p-p^{2}+2p^{2}-2p^{3}+3p^{3}=p+p^{2}+p^{3}$.

There is a shorter route worth knowing, offered here as a cross-check rather than as the intended method, because the identity it uses is not something a candidate should quote without proof. If $X$ takes values in $\{0,1,2,\ldots\}$ then $E(X)=\sum_{k \geqslant 1}P(X \geqslant k)$; with $P(H_m \geqslant k)=p^{\,k}$ for $1 \leqslant k \leqslant m$ and $0$ for $k \gt m$, this gives $E(H_m)=\sum_{k=1}^{m}p^{\,k}=\dfrac{p\left(1-p^{\,m}\right)}{1-p}$, the same answer.

Monotonicity and the limit. Since $0 \lt p \lt 1$, the sequence $p^{\,m}$ is strictly decreasing in $m$, so $1-p^{\,m}$ is strictly increasing, and multiplying by the positive constant $p/(1-p)$ preserves that: $E(H_m)$ increases strictly with $m$. Writing $$E(H_m)=\frac{p}{1-p}-\frac{p^{\,m+1}}{1-p}$$ shows two things at once. First, $p^{\,m+1} \gt 0$ for every $m$, so $E(H_m) \lt \dfrac{p}{1-p}$ for every $m$: the bound is never attained. Second, $p^{\,m+1} \to 0$ as $m \to \infty$, so $$E(H_m) \longrightarrow \frac{p}{1-p} \qquad (m \to \infty).$$ For $p=\tfrac12$ this limit is $1$, so the expected rung is less than $1$ at every single round, however long the process runs.

The tail probability. Let $1 \leqslant n \leqslant m$. Summing the distribution from part (iii), $$P(H_m \geqslant n)=\sum_{k=n}^{m-1}(1-p)p^{\,k}+p^{\,m}=(1-p)\cdot\frac{p^{\,n}-p^{\,m}}{1-p}+p^{\,m}=p^{\,n}-p^{\,m}+p^{\,m}=p^{\,n}.$$ The backwards description of part (iii) gives this in one line and explains why the answer is so clean: $H_m \geqslant n$ holds exactly when the last $n$ rounds, rounds $m-n+1,\ldots,m$, are all upward moves, and that has probability $p^{\,n}$ whatever $m$ is.

Now bring in part (ii). From $a_n=\dfrac{1-p^{\,n}}{p^{\,n}(1-p)}$, $$(1-p)a_n=\frac{1-p^{\,n}}{p^{\,n}}=p^{-n}-1, \qquad\text{so}\qquad 1+(1-p)a_n=p^{-n},$$ and therefore $$P(H_m \geqslant n)=p^{\,n}=\frac{1}{1+(1-p)a_n} \qquad (1 \leqslant n \leqslant m),$$ which in particular does not involve $m$ at all. As a numerical check, $p=\tfrac12$ and $n=2$ give $P(H_m \geqslant 2)=\tfrac14$ for every $m \geqslant 2$, and $1+(1-p)a_2=1+\tfrac12 \times 6=4$, whose reciprocal is $\tfrac14$.

What the identity says. It is an exact reciprocal relation between two quantities that were computed by completely different arguments: $a_n$ came from a forwards recurrence, and $P(H_m \geqslant n)$ from a backwards look at the last few rounds. It says that the harder rung $n$ is to reach, measured by the expected number of rounds $a_n$, the less often the counter is found at or above it, and that the trade is exact rather than approximate. For large $n$ the $1$ is negligible beside $(1-p)a_n$, so doubling the expected waiting time roughly halves the chance of finding the counter at rung $n$ or above at a given round. A rung is rare in proportion to how long it takes to reach.

Reconciling this with part (i). Part (i) shows that for every $n$, however large, the counter occupies rung $n$ at the end of some round with probability $1$, and part (ii) makes that quantitative with a finite expected waiting time $a_n$. Yet the expected rung at a specified round is always less than $p/(1-p)$; for $p=\tfrac12$ it is always less than $1$. There is no contradiction, and the reason is the order of the quantifiers.

The counter reaches rung $n$ is a statement about the whole infinite sequence of rounds: it asserts that there exists a round at which the rung is $n$. Over infinitely many rounds even a very unlikely event happens eventually, and part (i) makes precisely that argument with the batches. Replace with: "The counter is at rung $n$ at the end of round $m$ is a statement about one specified round. Its probability is $0$ for $m \lt n$ and $p^{n}$ at $m = n$, and it settles at the fixed value $(1-p)p^{n}$ for every $m \gt n$: it never improves as $m$ grows, however long the process runs."

The picture behind the algebra is this. The counter spends almost all of its time close to the bottom of the ladder and makes rare, brief excursions upwards, each of which is destroyed by the first reset. The excursions are what make every rung reachable; their rarity, and the fact that a single reset undoes all of the progress at once, is what keeps $E(H_m)$ bounded. An average over rounds and an event over all rounds are simply different things, and this question is built so that they can be compared exactly.