STEP Mock Paper 1: Long-form Questions

\textbf{(i)} Let $x>0$ and $y>0$. Then $xy(x+y)>0$, so the stated inequality is equivalent to the inequality obtained by multiplying through by $xy(x+y)$: $$y(x+y)+4x(x+y)\ \ge\ 9xy,$$ that is $$xy+y^2+4x^2+4xy\ \ge\ 9xy,$$ that is $$4x^2-4xy+y^2\ \ge\ 0,$$ that is $(2x-y)^2\ge 0$, which is true for all real $x,y$. Since every step is reversible (we multiplied and divided by the positive quantity $xy(x+y)$), the original inequality holds.

Equality holds exactly when $(2x-y)^2=0$, i.e. exactly when $y=2x$. So equality holds precisely for the pairs $(x,2x)$ with $x>0$.

\medskip \textbf{(ii)} Let $x>0$, $y>0$ and let $p,q$ be real. Multiplying by $xy(x+y)>0$, the inequality $$\frac{p^2}{x}+\frac{q^2}{y}\ \ge\ \frac{(p+q)^2}{x+y}$$ is equivalent to $$p^2y(x+y)+q^2x(x+y)\ \ge\ (p+q)^2xy,$$ that is $$p^2xy+p^2y^2+q^2x^2+q^2xy\ \ge\ p^2xy+2pq\,xy+q^2xy,$$ that is $$p^2y^2-2pq\,xy+q^2x^2\ \ge\ 0,$$ that is $(py-qx)^2\ge 0$, which is true. Again all steps are reversible, so the inequality holds, and equality holds if and only if $(py-qx)^2=0$, i.e. if and only if $py=qx$. Since $x,y>0$ this may be written as $\dfrac{p}{x}=\dfrac{q}{y}$.

(Part (i) is the case $p=1$, $q=2$: then $py=qx$ reads $y=2x$, as found above.)

\medskip \textbf{(iii)} Write $P_n=p_1+\cdots+p_n$ and $X_n=x_1+\cdots+x_n$, so $X_n>0$. Let $S(n)$ be the statement: for all real $p_1,\dots,p_n$ and all positive $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}$.

\emph{Base case.} For $n=1$ both sides equal $p_1^2/x_1$, so the inequality holds with equality, and the equality condition is vacuously satisfied. Hence $S(1)$ is true. (The case $n=2$ is exactly part (ii).)

\emph{Inductive step.} Suppose $S(n)$ is true for some $n\ge 1$, and let $p_1,\dots,p_{n+1}$ be real and $x_1,\dots,x_{n+1}$ positive. By the inductive hypothesis applied to the first $n$ terms, and then by part (ii) applied with $p=P_n$, $q=p_{n+1}$, $x=X_n>0$, $y=x_{n+1}>0$, $$\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}}\ \ge\ \frac{P_n^2}{X_n}+\frac{p_{n+1}^2}{x_{n+1}}\ \ge\ \frac{(P_n+p_{n+1})^2}{X_n+x_{n+1}}\ =\ \frac{P_{n+1}^2}{X_{n+1}}.$$ This proves the inequality in $S(n+1)$.

For the equality condition, note that equality in the displayed chain holds if and only if equality holds at both of the two inequality signs.

If $\dfrac{p_1}{x_1}=\cdots=\dfrac{p_{n+1}}{x_{n+1}}=k$, then $p_i=kx_i$ for each $i$, so $P_n=kX_n$; the inductive hypothesis gives equality at the first sign, and $P_n\,x_{n+1}=kX_nx_{n+1}=p_{n+1}X_n$ gives equality at the second by (ii). Hence equality holds throughout.

Conversely, suppose equality holds. Equality at the first sign forces, by the inductive hypothesis, $\dfrac{p_1}{x_1}=\cdots=\dfrac{p_n}{x_n}=k$ say, and then $P_n=kX_n$, so $\dfrac{P_n}{X_n}=k$. Equality at the second sign forces, by (ii), $P_n\,x_{n+1}=p_{n+1}X_n$, i.e. $\dfrac{p_{n+1}}{x_{n+1}}=\dfrac{P_n}{X_n}=k$. Hence all $n+1$ ratios are equal.

Therefore $S(n)\Rightarrow S(n+1)$, and since $S(1)$ holds, $S(n)$ holds for all integers $n\ge 1$ by induction.

\medskip \textbf{(iv)(a)} With $a,b,c>0$ and $a+b+c=1$, apply (iii) with $n=3$, $(p_1,p_2,p_3)=(1,2,3)$ and $(x_1,x_2,x_3)=(a,b,c)$: $$\frac{1}{a}+\frac{4}{b}+\frac{9}{c}=\frac{1^2}{a}+\frac{2^2}{b}+\frac{3^2}{c}\ \ge\ \frac{(1+2+3)^2}{a+b+c}=\frac{36}{1}=36.$$ Equality holds if and only if $\dfrac{1}{a}=\dfrac{2}{b}=\dfrac{3}{c}$, i.e. $b=2a$ and $c=3a$. Then $a+b+c=6a=1$, so $a=\tfrac16$, $b=\tfrac13$, $c=\tfrac12$. These values are positive and sum to $1$, and they give $$6+12+18=36,$$ so the bound is attained.

Hence the least value is $\boxed{36}$, attained exactly when $a=\tfrac16$, $b=\tfrac13$, $c=\tfrac12$.

\medskip \textbf{(iv)(b)} First, for all real $a,b,c$, $$(a+b+c)^2-3(ab+bc+ca)=a^2+b^2+c^2-ab-bc-ca=\tfrac12\big[(a-b)^2+(b-c)^2+(c-a)^2\big]\ \ge\ 0,$$ so $(a+b+c)^2\ge 3(ab+bc+ca)$, with equality if and only if $a=b=c$.

Now let $a,b,c>0$ and write $$\frac{a}{b+c}=\frac{a^2}{a(b+c)},\qquad \frac{b}{c+a}=\frac{b^2}{b(c+a)},\qquad \frac{c}{a+b}=\frac{c^2}{c(a+b)},$$ where the three denominators are positive. Applying (iii) with $n=3$, $(p_1,p_2,p_3)=(a,b,c)$ and $(x_1,x_2,x_3)=\big(a(b+c),\,b(c+a),\,c(a+b)\big)$, and noting that $$a(b+c)+b(c+a)+c(a+b)=2(ab+bc+ca),$$ we obtain $$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\ \ge\ \frac{(a+b+c)^2}{2(ab+bc+ca)}\ \ge\ \frac{3(ab+bc+ca)}{2(ab+bc+ca)}=\frac{3}{2},$$ the last inequality using the result of the first paragraph together with $ab+bc+ca>0$.

Equality requires equality in both steps. Equality in the second step requires $a=b=c$; and if $a=b=c$ then each of the three original terms equals $\tfrac12$, so the sum is exactly $\tfrac32$. Hence $$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\ \ge\ \frac{3}{2},$$ with equality if and only if $a=b=c$.

## (i) [4 marks]

$I(m,0) = \displaystyle\int_0^1 x^m\,dx = \frac{1}{m+1}$.

For $n \ge 1$, integrate by parts with $u = (1-x)^n$ and $\dfrac{dv}{dx} = x^m$, so $v = \dfrac{x^{m+1}}{m+1}$: $$I(m,n) = \left[\frac{x^{m+1}}{m+1}(1-x)^n\right]_0^1 + \frac{n}{m+1}\int_0^1 x^{m+1}(1-x)^{n-1}\,dx .$$ At $x=0$ the bracket is $0$ because $m+1 \ge 1$; at $x=1$ it is $0$ because $n \ge 1$. Hence $$I(m,n) = \frac{n}{m+1} I(m+1, n-1), \qquad\text{that is}\qquad (m+1)I(m,n) = n\,I(m+1,n-1). \qquad (\ast)$$

## (ii) [5 marks]

Let $P(n)$ be the statement: $$P(n): \quad \text{for \emph{every} non-negative integer } m, \quad I(m,n) = \frac{m!\,n!}{(m+n+1)!}.$$

**Base case.** $P(0)$: for every $m$, $I(m,0) = \dfrac{1}{m+1} = \dfrac{m!\,0!}{(m+1)!}$, by part (i). So $P(0)$ holds.

**Inductive step.** Let $n \ge 1$ and assume $P(n-1)$. Let $m$ be an arbitrary non-negative integer. Applying $(\ast)$ and then the hypothesis $P(n-1)$ at first argument $m+1$, $$I(m,n) = \frac{n}{m+1}\,I(m+1,n-1) = \frac{n}{m+1}\cdot\frac{(m+1)!\,(n-1)!}{\big((m+1)+(n-1)+1\big)!} = \frac{n}{m+1}\cdot\frac{(m+1)!\,(n-1)!}{(m+n+1)!}.$$ Since $\dfrac{(m+1)!}{m+1} = m!$ and $n\,(n-1)! = n!$, this is $\dfrac{m!\,n!}{(m+n+1)!}$. As $m$ was arbitrary, $P(n)$ holds.

By induction $P(n)$ holds for all $n \ge 0$, which is the required result.

**Why the statement must be quantified over all $m$.** The reduction $(\ast)$ does not express $I(m,n)$ in terms of $I(m, n-1)$: it lowers the second index but *raises the first*, producing $I(m+1,n-1)$. So if the induction statement were $Q(n): I(m_0,n) = \frac{m_0!\,n!}{(m_0+n+1)!}$ for one fixed $m_0$, then in the step from $Q(n-1)$ to $Q(n)$ the hypothesis would supply information only about $I(m_0, n-1)$, whereas $(\ast)$ requires the value of $I(m_0+1, n-1)$, about which $Q(n-1)$ says nothing. The step therefore cannot be closed. Inducting on $n$ with the statement asserted simultaneously for every $m$ makes the hypothesis strong enough to cover the shifted first argument. (Equivalently: each application of $(\ast)$ walks along a diagonal $m+n = \text{constant}$, so the whole diagonal must be carried by the hypothesis at once.)

*Remark for markers.* A candidate may instead derive the fixed-$m$ reduction $(m+n+1)I(m,n) = n\,I(m,n-1)$, for instance by combining $(\ast)$ with $I(m,n) = I(m,n-1) - I(m+1,n-1)$ (which follows from $(1-x)^n = (1-x)^{n-1} - x(1-x)^{n-1}$), and then induct at fixed $m$. This is fully valid and should receive full credit for the proof; the explanation asked for concerns inductions built on $(\ast)$ itself.

## (iii) [3 marks]

By the binomial theorem, $(1-x)^n = \displaystyle\sum_{k=0}^{n}\binom{n}{k}(-x)^k$, a *finite* sum, so it may be integrated term by term: $$I(m,n) = \int_0^1 x^m\sum_{k=0}^n \binom{n}{k}(-1)^k x^k \,dx = \sum_{k=0}^n (-1)^k\binom{n}{k}\int_0^1 x^{m+k}\,dx = \sum_{k=0}^n \frac{(-1)^k}{m+k+1}\binom{n}{k}.$$ Comparing with part (ii), $$\sum_{k=0}^{n} \frac{(-1)^k}{m+k+1}\binom{n}{k} = \frac{m!\,n!}{(m+n+1)!}.$$ (Check: $m=1$, $n=2$ gives $\tfrac12 - \tfrac23 + \tfrac14 = \tfrac{1}{12} = \tfrac{1!\,2!}{4!}$.)

## (iv) [8 marks]

**First result.** Write $A_N = \displaystyle\sum_{k=1}^{N}\frac{(-1)^{k-1}}{k}\binom{N}{k}$.

*Method 1 (turn the sum into an integral, reversing the move of part (iii)).* For $k \ge 1$, $\dfrac1k = \displaystyle\int_0^1 x^{k-1}\,dx$. Hence, the sum being finite, $$A_N = \sum_{k=1}^{N}(-1)^{k-1}\binom{N}{k}\int_0^1 x^{k-1}\,dx = \int_0^1 \frac{1}{x}\sum_{k=1}^{N}(-1)^{k-1}\binom{N}{k}x^{k}\,dx .$$ Now $\displaystyle\sum_{k=1}^{N}\binom{N}{k}(-x)^k = (1-x)^N - 1$, so $\displaystyle\sum_{k=1}^{N}(-1)^{k-1}\binom{N}{k}x^k = 1 - (1-x)^N$ and $$A_N = \int_0^1 \frac{1-(1-x)^N}{x}\,dx .$$ The numerator is a polynomial with zero constant term, so the integrand is itself a polynomial and this is an ordinary integral. Substituting $u = 1-x$ (so $du = -dx$ and the limits reverse), $$A_N = \int_0^1 \frac{1-u^N}{1-u}\,du = \int_0^1 \left(1 + u + u^2 + \cdots + u^{N-1}\right)du = \sum_{j=1}^{N}\frac{1}{j}.$$

*Method 2 (Pascal's rule and induction).* For $N \ge 2$, using $\binom{N}{k} = \binom{N-1}{k} + \binom{N-1}{k-1}$, $$A_N = \sum_{k=1}^{N}\frac{(-1)^{k-1}}{k}\binom{N-1}{k} + \sum_{k=1}^{N}\frac{(-1)^{k-1}}{k}\binom{N-1}{k-1}.$$ In the first sum the $k=N$ term is zero, so it equals $A_{N-1}$. In the second, $\dfrac{1}{k}\binom{N-1}{k-1} = \dfrac{(N-1)!}{k!\,(N-k)!} = \dfrac{1}{N}\binom{N}{k}$, so it equals $$\frac1N\sum_{k=1}^{N}(-1)^{k-1}\binom{N}{k} = \frac1N\left(1 - \sum_{k=0}^{N}(-1)^{k}\binom{N}{k}\right) = \frac1N\left(1 - 0\right) = \frac1N .$$ Hence $A_N = A_{N-1} + \frac1N$ with $A_1 = 1$, and $A_N = \sum_{j=1}^N \frac1j$ follows by induction.

**Second result.** Write $S_n = \displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{(k+1)^2}\binom{n}{k}$. The step that is not signposted is the absorption identity $$\frac{1}{k+1}\binom{n}{k} = \frac{n!}{(k+1)!\,(n-k)!} = \frac{1}{n+1}\cdot\frac{(n+1)!}{(k+1)!\,\big((n+1)-(k+1)\big)!} = \frac{1}{n+1}\binom{n+1}{k+1}.$$ Using it on one of the two factors $\dfrac{1}{k+1}$, $$S_n = \sum_{k=0}^{n}\frac{(-1)^k}{k+1}\cdot\frac{1}{n+1}\binom{n+1}{k+1} = \frac{1}{n+1}\sum_{j=1}^{n+1}\frac{(-1)^{j-1}}{j}\binom{n+1}{j},$$ after the shift $j = k+1$ (note $(-1)^k = (-1)^{j-1}$). By the first result with $N = n+1$, $$\boxed{\;S_n = \frac{1}{n+1}\left(1 + \frac12 + \cdots + \frac{1}{n+1}\right).\;}$$

*Alternative route to $S_n$ (no absorption identity).* For $0 \le t \le 1$, $$\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}t^{k+1} = \int_0^t (1-x)^n\,dx = \frac{1-(1-t)^{n+1}}{n+1},$$ so dividing by $t$ and integrating from $0$ to $1$ (the integrand is a polynomial throughout) gives $$S_n = \frac{1}{n+1}\int_0^1\frac{1-(1-t)^{n+1}}{t}\,dt = \frac{1}{n+1}\sum_{j=1}^{n+1}\frac1j,$$ by the integral already evaluated in the first result.

**Checks.** $n=0$: $S_0 = 1$ and the formula gives $1$. $n=1$: $1 - \tfrac14 = \tfrac34$ and the formula gives $\tfrac12(1+\tfrac12) = \tfrac34$. $n=2$: $1 - \tfrac{2}{4} + \tfrac19 = \tfrac{11}{18}$ and the formula gives $\tfrac13(1+\tfrac12+\tfrac13) = \tfrac{11}{18}$. All three identities were also verified numerically for many values of $m$, $n$ and $N$.

## Mark allocation

(i) 4: parts correctly set up 2, boundary term dealt with 1, $I(m,0)$ 1. (ii) 5: correctly quantified statement 1, base case 1, inductive step 2, explanation of the quantifier 1. (iii) 3: binomial expansion 1, term by term integration 1, comparison 1. (iv) 8: integral (or Pascal) representation 2, evaluation to the harmonic sum 2, absorption identity or the equivalent device 2, index shift and final closed form 2.

\textbf{(i)}

$u_2=2^2-2+1=3$, $u_3=3^2-3+1=7$, $u_4=7^2-7+1=43$.

From the recurrence, $$u_{n+1}-1=u_n^{\,2}-u_n=u_n(u_n-1),$$ and $$u_{n+1}-u_n=u_n^{\,2}-2u_n+1=(u_n-1)^2 .$$

Since $(u_n-1)^2\geqslant 0$, we have $u_{n+1}\geqslant u_n$ for every $n$. Formally, if $u_n\geqslant 2$ then $u_{n+1}=u_n+(u_n-1)^2\geqslant u_n\geqslant 2$; as $u_1=2\geqslant 2$, induction gives $u_n\geqslant 2$ for all $n\geqslant 1$.

In particular $u_n-1\geqslant 1>0$ and $u_{n+1}-1\geqslant 1>0$, so the following manipulation is valid: $$\frac{1}{u_n-1}-\frac{1}{u_{n+1}-1}=\frac{1}{u_n-1}-\frac{1}{u_n(u_n-1)}=\frac{u_n-1}{u_n(u_n-1)}=\frac{1}{u_n}.$$

\medskip \textbf{(ii)}

Let $P(n)$ be the statement $u_{n+1}-1=u_1u_2\cdots u_n$.

\emph{Base case.} $u_2-1=3-1=2=u_1$, so $P(1)$ is true.

\emph{Inductive step.} Suppose $P(m)$ holds for some $m\geqslant 1$, i.e. $u_{m+1}-1=u_1u_2\cdots u_m$. Using $u_{m+2}-1=u_{m+1}(u_{m+1}-1)$ from part (i), $$u_{m+2}-1=u_{m+1}\bigl(u_1u_2\cdots u_m\bigr)=u_1u_2\cdots u_mu_{m+1},$$ which is $P(m+1)$.

Hence by induction $u_{n+1}-1=u_1u_2\cdots u_n$ for all $n\geqslant 1$.

Since each factor satisfies $u_k\geqslant 2$, the product of the $n$ factors satisfies $$u_{n+1}-1=u_1u_2\cdots u_n\geqslant \underbrace{2\times 2\times\cdots\times 2}_{n}=2^{\,n}.$$

\medskip \textbf{(iii)}

Summing the identity of part (i) for $k=1,2,\ldots,n$, the sum telescopes: $$S_n=\sum_{k=1}^{n}\left(\frac{1}{u_k-1}-\frac{1}{u_{k+1}-1}\right)=\frac{1}{u_1-1}-\frac{1}{u_{n+1}-1}=1-\frac{1}{u_{n+1}-1},$$ since $u_1-1=1$.

For $n=4$: $u_5=43^2-43+1=1807$, so $u_5-1=1806$ and $$S_4=1-\frac{1}{1806}=\frac{1805}{1806}.$$ (Direct check: $\tfrac12+\tfrac13+\tfrac17+\tfrac1{43}=\tfrac{41}{42}+\tfrac{1}{43}=\tfrac{1763+42}{1806}=\tfrac{1805}{1806}$.)

By part (ii), $u_{n+1}-1\geqslant 2^{\,n}$, so $$0<1-S_n=\frac{1}{u_{n+1}-1}\leqslant \frac{1}{2^{\,n}}.$$ As $2^{-n}\to 0$ when $n\to\infty$, we get $1-S_n\to 0$, i.e. $S_n\to 1$. (Alternatively: $S_n$ is increasing and bounded above by $1$.) The limit is $1$.

Finally, $1-S_n<10^{-6}$ is equivalent to $u_{n+1}-1>10^{6}$. Now $$u_2-1=2,\quad u_3-1=6,\quad u_4-1=42,\quad u_5-1=1806,\quad u_6-1=u_5(u_5-1)=1807\times 1806=3\,263\,442 .$$ Since the sequence $u_{n+1}-1$ is increasing, the first value exceeding $10^{6}$ is $u_6-1=3\,263\,442$, corresponding to $n=5$; and indeed $1-S_5=\tfrac{1}{3263442}\approx 3.06\times 10^{-7}<10^{-6}$, whereas $1-S_4=\tfrac{1}{1806}\approx 5.5\times 10^{-4}>10^{-6}$.

Hence the least such $n$ is $\boxed{n=5}$ (informally: $n=5$).

\medskip \textbf{(iv)}

Exactly as in part (i), the recurrence gives, for all $n\geqslant 1$, $$w_{n+1}-1=w_n(w_n-1),\qquad w_{n+1}-w_n=(w_n-1)^2\geqslant 0 .$$ Since $w_1=a\geqslant 2$, the same induction as before gives $w_n\geqslant a\geqslant 2$ for all $n$, so $w_n-1\geqslant 1>0$ and $$\frac{1}{w_n}=\frac{1}{w_n-1}-\frac{1}{w_{n+1}-1}.$$ Summing for $k=1,\ldots,n$ telescopes to $$\sum_{k=1}^{n}\frac{1}{w_k}=\frac{1}{w_1-1}-\frac{1}{w_{n+1}-1}=\frac{1}{a-1}-\frac{1}{w_{n+1}-1}.$$

For the size of $w_{n+1}-1$: since $w_n\geqslant 2$, $$w_{n+1}-1=w_n(w_n-1)\geqslant 2(w_n-1),$$ so by induction $w_{n+1}-1\geqslant 2^{\,n}(w_1-1)=2^{\,n}(a-1)\geqslant 2^{\,n}$. Hence $$0<\frac{1}{w_{n+1}-1}\leqslant \frac{1}{2^{\,n}}\longrightarrow 0,$$ and therefore $$\sum_{k=1}^{\infty}\frac{1}{w_k}=\lim_{n\to\infty}\left(\frac{1}{a-1}-\frac{1}{w_{n+1}-1}\right)=\frac{1}{a-1}.$$

Taking $a=3$ gives $w_1=3$, $w_2=9-3+1=7$, $w_3=49-7+1=43$, $w_4=43^2-43+1=1807$, which is exactly the sequence of denominators in the given series. Hence $$\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1807}+\cdots=\frac{1}{3-1}=\frac{1}{2}.$$ (Consistency check with part (iii): this series is $S_\infty-\tfrac12=1-\tfrac12=\tfrac12$, since $u_2,u_3,u_4,\ldots=3,7,43,\ldots$.)

**Part (i) [3 marks]**

Suppose $r > s \ge 0$ and $3^r - 3^s = 2^c$ for some integer $c \ge 0$. Factorising the left hand side, $$3^s\left(3^{\,r-s} - 1\right) = 2^c .$$ Thus $3^s$ is a positive divisor of $2^c$, so by the Fact $3^s$ is a power of $2$, say $3^s = 2^j$. If $j \ge 1$ then $3^s$ is even, which is false since every power of $3$ is odd. Hence $j = 0$, so $3^s = 1$ and therefore $s = 0$.

(Equivalently: if $s \ge 1$ then $3$ divides $2^c$, which is impossible.)

Marks: factorising out $3^s$ (1); applying the Fact to $3^s \mid 2^c$ (1); concluding $s = 0$ (1).

**Part (ii) [8 marks]**

Let $m, n \ge 1$ with $3^m - 2^n = 1$, that is $2^n = 3^m - 1$. Split according to the parity of $m$.

*Case A: $m$ odd.* Using the standard factorisation, $$3^m - 1 = (3 - 1)\left(3^{m-1} + 3^{m-2} + \cdots + 3 + 1\right) = 2S,$$ where $S = 3^{m-1} + \cdots + 3 + 1$ is a sum of exactly $m$ terms, each of which is odd. Since $m$ is odd, $S$ is odd. Now $S$ divides $2^n$, so by the Fact $S$ is a power of $2$; being odd, $S = 1$. If $m \ge 3$ then $S \ge 1 + 3 + 9 = 13 > 1$, so $m = 1$. Then $2^n = 3 - 1 = 2$, giving $n = 1$. This yields $(m, n) = (1, 1)$.

*Case B: $m$ even.* Write $m = 2k$ with $k \ge 1$. Then $$2^n = 3^{2k} - 1 = \left(3^k - 1\right)\left(3^k + 1\right).$$ Both brackets are positive divisors of $2^n$, so by the Fact both are powers of $2$: say $3^k - 1 = 2^u$ and $3^k + 1 = 2^v$, where $0 \le u < v$ and $u + v = n$. Subtracting, $$2^v - 2^u = 2 .$$ If $u = 0$ then $2^v = 3$, which is impossible. So $u \ge 1$ and $2^u\left(2^{\,v-u} - 1\right) = 2$. The bracket is a positive odd divisor of $2$, hence equals $1$, so $v = u + 1$; then $2^u = 2$, giving $u = 1$ and $v = 2$. Therefore $3^k - 1 = 2$, so $k = 1$, $m = 2$, and $n = u + v = 3$. This yields $(m, n) = (2, 3)$.

Both pairs work: $3 - 2 = 1$ and $9 - 8 = 1$. Hence the complete list is $(m, n) = (1, 1)$ and $(2, 3)$.

*Alternative start (congruences).* If $n \ge 3$ then $3^m = 2^n + 1 \equiv 1 \pmod 8$. Since $3^2 = 9 \equiv 1 \pmod 8$, we have $3^m \equiv 1 \pmod 8$ for $m$ even and $3^m \equiv 3 \pmod 8$ for $m$ odd, so $m$ must be even and Case B finishes the problem; the cases $n = 1$ (giving $3^m = 3$, $m = 1$) and $n = 2$ (giving $3^m = 5$, impossible) are checked directly. Note that working modulo $8$ cannot by itself settle this equation, since it leaves every even $m$ open: the factorisation and the Fact are what actually finish it.

Marks: correct parity split or equivalent reduction (2); disposing of the odd case, including the oddness of $S$ and the use of the Fact (2); the difference of two squares in the even case (1); applying the Fact to both brackets (1); solving $2^v - 2^u = 2$ correctly, including the rejection of $u = 0$ (1); complete final list with verification (1).

**Part (iii) [9 marks]**

Suppose $m, n \ge 1$ and $2^n + 3^m = t^2$ with $t$ a positive integer.

Since $2^n$ is even and $3^m$ is odd, $t^2$ is odd, so $t$ is odd.

*Step 1: $n$ is even.* Work modulo $3$. If $3 \mid t$ then $3 \mid t^2 - 3^m = 2^n$, which is false, so $3 \nmid t$ and hence $t^2 \equiv 1 \pmod 3$. Also $2 \equiv -1 \pmod 3$, so $2^n \equiv (-1)^n \pmod 3$. Reducing $2^n + 3^m = t^2$ modulo $3$ gives $(-1)^n \equiv 1 \pmod 3$, which forces $n$ to be even. Write $n = 2a$ with $a \ge 1$.

*Step 2: $m$ is even.* Since $n = 2a \ge 2$, we have $2^n \equiv 0 \pmod 4$. As $t$ is odd, $t^2 \equiv 1 \pmod 4$. Hence $3^m \equiv 1 \pmod 4$, and since $3 \equiv -1 \pmod 4$ we get $(-1)^m \equiv 1 \pmod 4$, so $m$ is even. Write $m = 2b$ with $b \ge 1$.

*Step 3: factorise.* Now $$3^{2b} = t^2 - 2^{2a} = \left(t - 2^a\right)\left(t + 2^a\right).$$ Since $t^2 = 2^{2a} + 3^{2b} > 2^{2a}$ and $t > 0$, we have $t > 2^a$, so both brackets are positive divisors of $3^{2b}$. By the Fact both are powers of $3$: say $t - 2^a = 3^i$ and $t + 2^a = 3^j$ with $i < j$ and $i + j = 2b$. Subtracting, $$3^j - 3^i = 2^{a+1},$$ so a difference of two powers of $3$ is a power of $2$. By part (i), $i = 0$, and hence $j = 2b$, giving $$3^{2b} - 2^{\,a+1} = 1 .$$

*Step 4: apply part (ii).* By part (ii), the only positive integer solutions of $3^M - 2^N = 1$ are $(M, N) = (1, 1)$ and $(2, 3)$. Here $M = 2b$ is even, so $2b = 2$ and $a + 1 = 3$, giving $b = 1$ and $a = 2$.

Therefore $m = 2b = 2$ and $n = 2a = 4$, with $t = 3^i + 2^a = 1 + 4 = 5$. Checking: $2^4 + 3^2 = 16 + 9 = 25 = 5^2$.

Hence the only pair is $(m, n) = (2, 4)$, and the square is $25$.

*Alternative route (equally acceptable).* First rule out $n = 1$: then $t^2 = 3^m + 2 \equiv 2 \pmod 3$, but squares are $0$ or $1$ modulo $3$. So $n \ge 2$ and Step 2 applies, giving $m = 2b$. Factorise the other way: $$2^n = t^2 - 3^{2b} = \left(t - 3^b\right)\left(t + 3^b\right),$$ so by the Fact $t - 3^b = 2^u$ and $t + 3^b = 2^v$ with $u < v$ and $u + v = n$. Subtracting, $2^u\left(2^{\,v-u} - 1\right) = 2 \cdot 3^b$; the bracket is odd, so $2^u = 2$, that is $u = 1$, and $2^{\,v-1} - 1 = 3^b$. This is the equation $2^w - 3^b = 1$ with $w = v - 1$, which part (ii) does not cover, so it must be solved on the spot: if $w \ge 3$ then $3^b = 2^w - 1 \equiv 7 \pmod 8$, impossible because $3^b \equiv 1$ or $3 \pmod 8$; and $w = 1$ gives $3^b = 1$, rejected as $b \ge 1$; so $w = 2$ and $b = 1$. Then $v = 3$, $n = u + v = 4$, $m = 2$ and $t = 3 + 2 = 5$, the same answer. Candidates who take this route must supply the extra argument for $2^w - 3^b = 1$; those who take the first route must supply Step 1 instead. Full marks either way.

Marks: obtaining $t$ odd and $n$ even by a valid congruence argument (2); obtaining $m$ even (2); the difference of two squares and the use of the Fact to make both factors powers of $3$ (2); reduction to $3^{2b} - 2^{a+1} = 1$ via part (i), or the equivalent extra work in the alternative route (2); correct unique answer with the value of the square stated and verified (1).