Open Book Publishers logo Open Access logo
  • button
  • button
  • button
GO TO...
Contents
Copyright
book cover
BUY THE BOOK

Problem 7:  Chain of equations () 1997 Paper II

Suppose that

3 = 2 x1 = x1 + 2 x2 = x2 + 2 x3 = x3 + 2 x4 = .

Guess an expression, in terms of n, for xn. Then, by induction or otherwise, prove the correctness of your guess.

Comments

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 x1, x2, x3, etc and look for a pattern. You should not need to go beyond x4.

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 = xn + 2 xn+1,i.e.xn+1 = 2 3 xn.

We find x1 = 2 3, x2 = 6 7, x3 = 14 15 and x4 = 30 31. The denominators give the game away. We guess

xn = 2n+1 2 2n+1 1.

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

xk = 2k+1 2 2k+1 1.

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,

xk+1 = 2 3 xk = 2 3 2k+12 2k+11 = 2(2k+1 1) 3(2k+1 1) (2k+1 2) = 2k+2 2 2k+2 1,

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 first line of the solution, when we had to decide how to separate out the equations. We could have tried instead

x2 + 2 x3 = x3 + 2 x4

leading to

(x2 x3) = 2(x3 x4) x3x4 ,

and so on, but it would not be at all clear what to do next.