Problem 7:  Chain of equations ($✓$) 1997 Paper II

Suppose that

$3=\frac{2}{{x}_{1}}={x}_{1}+\frac{2}{{x}_{2}}={x}_{2}+\frac{2}{{x}_{3}}={x}_{3}+\frac{2}{{x}_{4}}=\cdots \phantom{\rule{0.3em}{0ex}}.$

Guess an expression, in terms of $n$, for ${x}_{n}\phantom{\rule{0.3em}{0ex}}$. Then, by induction or otherwise, prove the correctness of your guess.

Wording this sort of question is a real headache for the examiners. Suppose you guess wrong; how can you then prove your guess by induction (unless you get that wrong too)? How else can the question be phrased? In the end, we decided to assume that you are all so clever that your guesses will all be correct.

To guess the formula, you need to work out ${x}_{1}$, ${x}_{2}$, ${x}_{3}\phantom{\rule{0.3em}{0ex}}$, etc and look for a pattern. You should not need to go beyond ${x}_{4}\phantom{\rule{0.3em}{0ex}}$.

Proof by induction is not in the core A-level syllabus. We decided to include it in the syllabus for STEP I and II because the idea behind it is not difficult and it is very important both as a method of proof and also as an introduction to more sophisticated mathematical thought.

Solution to problem 7

First let’s put the equations into a more manageable form. Each equality can be written in the form

$3={x}_{n}+\frac{2}{{x}_{n+1}},\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}\text{i.e.}\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{1em}{0ex}}{x}_{n+1}=\frac{2}{3-{x}_{n}}\phantom{\rule{2.77695pt}{0ex}}.$

We ﬁnd ${x}_{1}=\frac{2}{3}$, ${x}_{2}=\frac{6}{7}$, ${x}_{3}=\frac{14}{15}$ and ${x}_{4}=\frac{30}{31}$. The denominators give the game away. We guess

${x}_{n}=\frac{{2}^{n+1}-2}{{2}^{n+1}-1}\phantom{\rule{2.77695pt}{0ex}}.$

For the induction, we need a starting point: our guess certainly holds for $n=1$ (and 2, 3, and 4!).

For the inductive step, we suppose our guess also holds for $n=k$, where $k$ is any integer, so that

${x}_{k}=\frac{{2}^{k+1}-2}{{2}^{k+1}-1}\phantom{\rule{2.77695pt}{0ex}}.$

If we can show that it then also holds for $n=k+1$, we are done.

We have, from the equation given in the question,

${x}_{k+1}=\frac{2}{3-{x}_{k}}=\frac{2}{3-\frac{{2}^{k+1}-2}{{2}^{k+1}-1}}=\frac{2\left({2}^{k+1}-1\right)}{3\left({2}^{k+1}-1\right)-\left({2}^{k+1}-2\right)}=\frac{{2}^{k+2}-2}{{2}^{k+2}-1}\phantom{\rule{2.77695pt}{0ex}},$

as required.

Post-mortem

There’s not much to say about this. By STEP standards, it is fairly easy and short. Nevertheless, you are left to your own devices from the beginning, so you should be pleased if you got it out.

Perhaps the key step came in the very ﬁrst line of the solution, when we had to decide how to separate out the equations. We could have tried instead

${x}_{2}+\frac{2}{{x}_{3}}={x}_{3}+\frac{2}{{x}_{4}}$

$\left({x}_{2}-{x}_{3}\right)=\frac{2\left({x}_{3}-{x}_{4}\right)}{{x}_{3}{x}_{4}}\phantom{\rule{0.3em}{0ex}},$