A A A
OPB logo

The Essence of Mathematics Through Elementary Problems
More info and resources at: https://www.openbookpublishers.com/product/979

VI. Infinity: recursion, induction, infinite descent

Mathematical induction – i.e. proof by recurrence – is... imposed on us, because it is... the affirmation of a property of the mind itself.

Henri Poincaré (1854–1912)

Allez en avant, et la foi vous viendra. (Press on ahead, and understanding will follow.)

Jean le Rond d’Alembert (1717–1783)

Mathematics has been called “the science of infinity”. However, infinity is a slippery notion, and many of the techniques which are characteristic of modern mathematics were developed precisely to tame this slipperiness. This chapter introduces some of the relevant ideas and techniques.

There are aspects of the story of infinity in mathematics which we shall not address. For example, astronomers who study the night sky and the movements of the planets and stars soon note its immensity, and its apparently ‘fractal’ nature – where increasing the detail or magnification reveals more or less the same level of complexity on different scales. And it is hard then to avoid the question of whether the stellar universe is finite or infinite.

In the mental universe of mathematics, once counting, and the process of halving, become routinely iterative processes, questions about infinity and infinitesimals are almost inevitable. However, mathematics recognises the conceptual gulf between the finite and the infinite (or infinitesimal), and rejects the lazy use of “infinity” as a metaphor for what is simply “very large”. Large finite numbers are still numbers; and long finite sums are conceptually quite different from sums that “go on for ever”. Indeed, in the third century BC, Archimedes (c. 287–212 BC) wrote a small booklet called The Sand Reckoner, dedicated to King Gelon, in which he introduced the arithmetic of powers (even though the ancient Greeks had no convenient notation for writing such numbers), in order to demonstrate that – contrary to what some people had claimed – the number of grains of sand in the known universe must be finite (he derived an upper bound of approximately 8×1063 The influence wielded by ideas of infinity on mathematics has been profound, even if we now view some of these ideas as flights of fancy –

  • from Zeno of Elea (c. 495 BC – c. 430 BC), who presented his paradoxes to highlight the dangers inherent in reasoning sloppily with infinity,
  • through Giordano Bruno (1548–1600), who declared that there were infinitely many inhabited universes, and who was burned at the stake when he refused to retract this and other “heresies”,
  • to Georg Cantor (1845–1918) whose groundbreaking work in developing a true “mathematics of infinity” was inextricably linked to his religious beliefs.

In contrast, we focus here on the delights of the mathematics, and in particular on how an initial doorway into “ideas of infinity” can be forged from careful reasoning with finite entities. Readers who would like to explore what we pass over in silence could do worse than to start with the essay on “infinity” in the MacTutor History of Mathematics archive:

http://www-history.mcs.st-and.ac.uk/HistTopics/Infinity.html.

The simplest infinite processes begin with recursion – a process where we repeat exactly the same operation over and over again (in principle, continuing for ever). For example, we may start with 0, and repeat the operation “add 1”, to generate the sequence:

0, 1, 2, 3, 4, 5, 6, 7,….

Or we may start with 20 = 1 and repeat the operation “multiply by 2”, to generate:

1, 2, 4, 8, 16, 32, 64, 128,….

Or we may start with 1.000000 ⋯, and repeat the steps involved in “dividing by 7” to generate the infinite decimal for 1 7 :

1 7 = 0.1428571428571428571 .

We can then vary this idea of “recursion” by allowing each operation to be “essentially” (rather than exactly) the same, as when we define triangular numbers by “adding n” at the nth stage to generate the sequence:

0, 1, 3, 6, 10, 15, 21, 28,….

In other words, the sequence of triangular numbers is defined by a recurrence relation:

T0=0; and

when n1, Tn=Tn-1+n.

We can vary this idea further by allowing more complicated recurrence relations – such as that which defines the Fibonacci numbers:

F0=0, F1=1; and
when n1 Fn+1=Fn+Fn-1.

All of these “images of infinity” hark back to the familiar counting numbers.

  • We know how the counting numbers begin (with 0, or with 1); and
  • we know that we can “add 1” over and over again to get ever larger counting numbers.

The intuition that this process is, in principle, never–ending (so is never actually completed), yet somehow manages to count all positive integers, is what Poincaré called a “property of the mind itself”: that is, the idea that we can define an infinite sequence, or process, or chain of deductions (involving digits, or numbers, or objects, or statements, or truths) by

  • specifying how it begins, and by then
  • specifying in a uniform way “how to construct the next term ”, or “how to perform the next step”.

This idea is what lies behind “proof by mathematical induction”, where we prove that some assertion P(n) holds for all n1 – so demonstrating infinitely many separate statements at a single blow. The validity of this method of proof depends on a fundamental property of the positive integers, or of the counting sequence

“1, 2, 3, 4, 5, …”,

namely:

The Principle of Mathematical Induction: If a subset S of the positive integers

  • contains the integer “1”,
    and has the property that
  • whenever an integer k is in the set S, then the next integer k+1 is always in S too,

then S contains all positive integers.

6.1. Proof by mathematical induction I

When students first meet “proof by induction”, it is often explained in a way that leaves them feeling distinctly uneasy, because it appears to break the fundamental taboo:

never assume what you are trying to prove.

This tends to leave the beginner in the position described by d'Alembert's quote at the start of the chapter: they may “press on” in the hope that “understanding will follow”, but a doubt often remains. So we encourage readers who have already met proof by induction to take a step back, and to try to understand afresh how it really works. This may require you to study the solutions (Section 6.10), and to be prepared to learn to write out proofs more carefully than, and rather differently from, what you are used to.

When we wish to prove a general result which involves a parameter n, where n can be any positive integer, we are really trying to prove infinitely many results all at once. If we tried to prove such a collection of results in turn, “one at a time”, not only would we never finish, we would scarcely get started (since completing the first million, or billion, cases leaves just as much undone as at the start). So our only hope is:

  • to think of the sequence of assertions in a uniform way, as consisting of infinitely many different, but similar–looking, statements P(n), one for each n separately (with each statement depending on a particular n); and
  • to recognise that the overall result to be proved is not just a single statement P(n), but the compound statement that “P(n) is true, for all n1 ”.

Once the result to be proved has been formulated in this way, we can

  • use bare hands to check that the very first statement is true (usually P(1)); and
  • try to find some way of demonstrating that,

– as soon as we know that “P(k) is true, for some (particular, but unspecified) k1”,

– we can prove in a uniform way that the next result P(k+1) is then automatically true.

Having implemented the first of the two induction steps, we know that P(1) is true.

The second bullet point above then comes into play and assures us that (since we know that P(1) is true), P(2) must be true.

And once we know that P(2) is true, the second bullet point assures us that P(3) is also true.

And once we know that P(3) is true, the second bullet point assures us that P(4) is also true.

And so on for ever.

We can then conclude that the whole sequence of infinitely many statements are all true – namely that:

every statement P(n) is true”,

or that

P(n) is true, for all n1.”

In other words, if we define S to be the set of positive integers n for which the statement P(n) is true, then S contains the element “1”, and whenever k is in S, so is k+1; hence, by the Principle of Mathematical Induction we know that S contains all positive integers.

At this stage we should acknowledge an important didactical (rather than mathematical) ploy in our recommended layout here. It is important to underline the distinction between

(i) the individual statements P(n) which are the separate ingredients in the overall statement to be proved, namely:

“P(n) is true, for all n1”,

where infinitely many individual statements have been compressed into a single compound statement, and

(ii) the induction step, where we

– assume some particular P(k) is known to be true, and

– show that the next statement P(k+1) is then automatically true.

To underline this distinction we consistently use a different “dummy variable” (namely “k”) in the latter case. This distinction is a psychological ploy rather than a logical necessity. However, we recommend that readers should imitate this distinction (at least initially).

6.2. ‘Mathematical induction’ and ‘scientific induction’

The idea of a “list that goes on for ever” arose in the sequence of powers of 4 back in Problem 16, where we asked

Do the two sequences arising from successive powers of 4:

  • the leading digits:
4, 2, 6, 2, 1, 4, 2, 6, 2, 1, 4,…,

and

  • the units digits:
4, 6, 4, 6, 4, 6, 4, 6,…,

really “repeat for ever” as they seem to?

This example illustrates the most basic misconception that sometimes arises concerning mathematical induction – namely to confuse it with the kind of pattern spotting that is often called ‘scientific induction’.

In science (as in everyday life), we routinely infer that something that is observed to occur repeatedly, apparently without exception (such as the sun rising every morning; or the Pole star seeming to be fixed in the night sky) may be taken as a “fact”. This kind of “scientific induction” makes perfect sense when trying to understand the world around us – even though the inference is not warranted in a strictly logical sense.

Proof by mathematical induction is quite different. Admittedly, it often requires intelligent guesswork at a preliminary stage to make a guess that allows us to formulate precisely what it is that we should be trying to prove. But this initial guess is separate from the proof, which remains a strictly deductive construction. For example,

the fact that “1”, “1+3”, “1+3+5”, “1+3+5+7”, etc. all appear to be successive squares gives us an idea that perhaps the identity

P(n): 1+3+5++(2n-1)=n2
is true, for all n1.

This guess is needed before we can start the proof by mathematical induction. But the process of guessing is not part of the proof. And until we construct the “proof by induction” (Problem 231), we cannot be sure that our guess is correct.

The danger of confusing ‘mathematical induction’ and ‘scientific induction’ may be highlighted to some extent if we consider the proof in Problem 76 above that “we can always construct ever larger prime numbers”, and contrast it with an observation (see Problem 228 below) that is often used in its place – even by authors who should know better.

In Problem 76 we gave a strict construction by mathematical induction:

  • we first showed how to begin (with p1=2 say);
  • then we showed how, given any finite list of distinct prime numbers p1,p2,p3,,pk, it is always possible to construct a new prime pk+1 (as the smallest prime number dividing Nk=p1×p2×p3××pk+1).

This construction was very carefully worded, so as to be logically correct.

In contrast, one often finds lessons, books and websites that present the essential idea in the above proof, but “simplify” it into a form that encourages anti–mathematical “pattern–spotting” which is all–too–easily misconstrued. For example, some books present the sequence

(2;)2+1=3;2×3+1=7;2×3×5+1=31;2×3×5×7+1=211;

as a way of generating more and more primes.

Problem 228

(a) Are 3, 7, 31, 211 all prime?

(b) 2×3×5×7×11+1 prime?

(c) Is 2×3×5×7×11×13+1 prime? A

We have already met two excellent historical examples of the dangers of plausible pattern–spotting in connection with Problem 118. There you proved that:

“if 2n-1 is prime, then n must be prime.”

You then showed that 22-1, 23-1, 25-1, 27-1 are all prime, but that 211-1=2047=23×89 is not. This underlines the need to avoid jumping to (possibly false) conclusions, and never to confuse a statement with its converse.

In the same problem you showed that:

“if ab+1 is to be prime and a1, then a must be even, and b must be a power of 2.”

You then looked at the simplest family of such candidate primes namely the sequence of Fermat numbers fn:

f0=21+1=3,f1=22+1=5,f2=24+1=17,f3=28+1=257,f4=216+1.

It turned out that, although fo, f0,f1,f2,f3,f4 are all prime, and although Fermat (1601–1665) claimed (in a letter to Marin Mersenne (1588–1648)) that all Fermat numbers fn are prime, we have yet to discover a sixth Fermat prime!

There are times when a mathematician may appear to guess a general result on the basis of what looks like very modest evidence (such as noticing that it appears to be true in a few small cases). Such “informed guesses” are almost always rooted in other experience, or in some unnoticed feature of the particular situation, or in some striking analogy: that is, an apparent pattern strikes a chord for reasons that go way beyond the mere numbers. However those with less experience need to realise that apparent patterns or trends are often no more than numerical accidents.

Pell’s equation (John Pell (1611–1685)) provides some dramatic examples.

  • If we evaluate the expression “n2+1” for n=1,2, 3,, we may notice that the outputs 2,5, 10, 17, 26, never give a perfect square. And this is to be expected, since the next square after n2 is
(n+1)2=n2+2n+1, ,

and this is always greater than n2+1.

  • However, if we evaluate “991n2+1” for n=1, 2, 3,…, we may observe that the outputs never seem to include a perfect square. But this time there is no obvious reason why this should be so – so we may anticipate that this is simply an accident of “small” numbers. And we should hesitate to change our view, even though this accident goes on happening for a very, very, very long time: the smallest value of n for which 991n2+1 gives rise to a perfect square is apparently
n=12055735790331359447442538767.

6.3. Proof by mathematical induction II

Even where there is no confusion between mathematical induction and ‘scientific induction', students often fail to appreciate the essence of “proof by induction”. Before illustrating this, we repeat the basic structure of such a proof.

A mathematical result, or formula, often involves a parameter n, where n can be any positive integer. In such cases, what is presented as a single result, or formula, is a short way of writing an infinite family of results. The proof that such a result is correct therefore requires us to prove infinitely many results at once. We repeat that our only hope of achieving such a mind–boggling feat is

  • to formulate the stated result for each value of n separately: that is, as a statement P(n) which depends on n;
  • then to use bare hands to check the “beginning” – namely that the simplest case (usually P(1)) is true;
  • finally to find some way of demonstrating that,

– as soon as we know that P(k) is true, for some (unknown) k1,

– we can prove that the next result P(k+1) is then automatically true.

We can then conclude that

every statement P(n) is true”,

or that

P(n) is true, for all n1”.

Problem 229 Prove the statement:

“52n+2 – 24n – 25 is divisible by 576, for all n1”.

When trying to construct proofs in private, one is free to write anything that helps as ‘rough work'. But the intended thrust of Problem 229 is two–fold:

  • to introduce the habit of distinguishing clearly between

    (i) the statement P(n) for a particular n, and

    (ii) the statement to be proved – namely “P(n) is true, for all n1”; and

  • to draw attention to the “induction step” (i.e. the third bullet point above), where

    (i) we assume that some unspecified P(k) is known to be true, and

    (ii) seek to prove that the next statement P(k+1) must then be true.

The central lesson in completing the “induction step” is to recognize that:

to prove that P(k+1) is true, one has to start by looking at what P(k+1) says.

In Problem 229 P(k+1) says that

52(k+1)+2-24(k+1)-25 is divisible by 576”.

Hence one has to start the induction step with the relevant expression

52(k+1)+2-24(k+1)-25,

and look for some way to rearrange this into a form where one can use P(k) (which we assume is already known to be true, and so are free to use).

It is in general a false strategy to work the other way round – by “starting with P(k), and then fiddling with it to try to get P(k+1)”. (This strategy can be made to work in the simplest cases; but it does not work in general, and so is a bad habit to get into.) So the induction step should always start with the hypothesis of P(k+1).

The next problem invites you to prove the formula for the sum of the angles in any polygon. The result is well–known; yet we are fairly sure that the reader will never have seen a correct proof. So the intention here is for you to recognise the basic character of the result, to identify the flaws in what you may until now have accepted as a proof, and to try to find some way of producing a general proof.

Problem 230 Prove by induction the statement:

“for each n3, the angles of any n–gon in the plane have sum equal to (n-2)π radians.”

The formulation certainly involves a parameter n3; so you clearly need to begin by formulating the statement P(n). For the proof to have a chance of working, finding the right formulation involves a modest twist! So if you get stuck, it may be worth checking the first couple of lines of the solution.

No matter how P(n) is formulated, you should certainly know how to prove the statement P(3) (essentially the formula for the sum of the angles in a triangle). But it is far from obvious how to prove the “induction step”:

“if we know that P(k) is true for some particular k1, then P(k+1) must also be true”.

When tackling the induction step, we certainly cannot start with P(k)! The statement P(k+1) says something about polygons with k+1 sides: and there is no way to obtain a typical (k+1)–gon by fiddling with some statement about polygons with k sides. (If you start with a k–gon, you can of course draw a triangle on one side to get a (k+1)–gon; but this is a very special construction, and there is no easy way of knowing whether all (k+1)–gons can be obtained in this way from some k–gon.) The whole thrust of mathematical induction is that we must always start the induction step by thinking about the hypothesis of P(k+1) – that is in this case, by considering an arbitrary (k+1)–gon and then finding some guaranteed way of “reducing” it in order to make use of P(k).

The next two problems invite you to prove some classical algebraic identities. Most of these may be familiar. The challenge here is to think carefully about the way you lay out your induction proof, to learn from the examples above, and (later) to learn from the detailed solutions provided.

Problem 231 Prove by induction the statement:

1+3+5++(2n1)=n2 holds, for all n1

The summation in Problem 231 was known to the ancient Greeks. The mystical Pythagorean tradition (which flourished in the centuries after Pythagoras) explored the character of integers through the ‘spatial figures’ which they formed. For example, if we arrange each successive integer as a new line of dots in the plane, then the sum “1+2+3++n” can be seen to represent a triangular number. Similarly, if we arrange each odd number 2k1 in the sum “1+2+3++n” as a “k-by-k reverse L-shape”, or gnomon (a word which we still use to refer to the L-shaped piece that casts the shadow on a sundial), then the accumulated L-shapes build up an n by n square of dots - the “1” being the dot in the top left hand corner, the “3” being the reverse L-shape of 3 dots which make this initial “1” into a 2 by 2 square, the “5” being the reverse L-shape of 5 dots which makes this 2 by 2 square into a 3 by 3 square, and so on. Hence the sum “1+3+5+...+(2n1)” can be seen to represent a square number.

There is much to be said for such geometrical illustrations; but there is no escape from the fact that they hide behind an ellipsis (the three dots which we inserted in the sum between “5” and “2n1”, which were then summarised when arranging the reverse L-shapes by ending with the words “and so on”). Proof by mathematical induction, and its application in Problem 231, constitute a formal way of avoiding both the appeal to pictures, and the hidden ellipsis.

Problem 232 The sequence

2,5,13,35,

is defined by its first two terms u0=2,u1=5, and by the recurrence relation:

un+2=5un+16un.

(a) Guess a closed formula for the nth term un.

(b) Prove by induction that your guess in (a) is correct for all n0.

Problem 233 The sequence of Fibonacci numbers

0,1,1,2,3,5,8,13,

is defined by its first two terms F0=0,F1=1, and by the recurrence relation:

Fn+2=Fn+1+Fn when n0.

Prove by induction that, for all n0,

Fn=αnβn5,whereα=1+52andβ=152

Problem 234 Prove by induction that

52n+1·2n+2+3n+2·22n+1

is divisible by 19, for all n0.

Problem 235 Use mathematical induction to prove that each of these identities holds, for all n1:

(a) 1+2+3++n=n(n+1)2

(b) 11·2+12·3+13·4++1n(n+1)=11n+1

(c) 1+q+q2+q3++qn1=11qqn1q

(d) 0·0!+1·1!+2·2!++(n1)·(n1)!=n!1

(e) (cosθ+isinθ)n=cosnθ+isinnθ.

Problem 236 Prove by induction the statement:

(1+2+3++n)2=13+23+33++n3, for all n1”.

We now know that, for all n1:

1+1+1++1(nterms)=n.

And if we sum these “outputs” (that is, the first n natural numbers), we get the nth triangular number:

1+2+3++n=n(n+1)2=Tn.

The next problem invites you to find the sum of these “outputs”: that is, to find the sum of the first n triangular numbers.

Problem 237

(a) Experiment and guess a formula for the sum of the first n triangular numbers:

T1+T2+T3++Tn=1+3+6++n(n+1)2.

(b) Prove by induction that your guessed formula is correct for all n1.

A We now know closed formulae for

1+2+3++n

and for

1·2+2·3+3·4++(n1)n”.

The next problem hints firstly that these identities are part of something more general, and secondly that these results allow us to find identities for the sum of the first n squares:

12+22+32++n2

for the first n cubes:

13+23+33++n3

and so on.

Problem 238

(a) Note that

1·2+2·3+3·4++n(n+1)=1·(1+1)+2·(2+1)+3·(3+1)++n·(n+1).

Use this and the result of Problem 237 to derive a formula for the sum:

12+22+32++n2.

(b) Guess and prove a formula for the sum

1·2·3+2·3·4+3·4·5++(n2)(n1)n.

Use this to derive a closed formula for the sum:

13+23+33++n3.

It may take a bit of effort to digest the statement in the next problem. It extends the idea behind the “method of undetermined coefficients” that is discussed in Note 2 to the solution of Problem 237(a).

Problem 239

(a) Given n+1 distinct real numbers

a0,a1,a2,...,an

find all possible polynomials of degree n which satisfy

fa0=fa1=fa2==fan1=0,fan=b

for some specified number b.

(b) For each n1, prove the following statement:

Given two labelled sets of n+1 real numbers

a0,a1,a2,...,an,

and

b0,b1,b2,,bn,

where the ai are all distinct (but the b need not be), there exists a polynomial fn of degree n, such that

fna0=b0,fna1=b1,fna2=b2,,fnan=bn.

We end this subsection with a mixed bag of three rather different induction problems. In the first problem the induction step involves a simple construction of a kind we will meet later.

Problem 240 A country has only 3 cent and 4 cent coins.

(a) Experiment to decide what seems to be the largest amount, N cents, that cannot be paid directly (without receiving change).

(b) Prove by induction that “n cents can be paid directly for each n>N”.

Problem 241

(a) Solve the equation z+1z=1. Calculate z2, and check that z2+1z2 is also an integer.

(b) Solve the equation z+1z=2. Calculate z2+1z2, and check that z2+1z2 is also an integer.

(c) Solve the equation z+1z=3. Calculate z2+1z2, and check that z2+1z2 is also an integer.

(d) Solve the equation z+1z=k, where k is an integer. Calculate z2, and check that z2+1z2 is also an integer.

(e) Prove that if a number z has the property that z+ 1 z is an integer, then zn+1zn is also an integer for each n1.

Problem 242 Let p be any prime number. Use induction to prove:

npn is divisible by p for all n1”.

6.4. Infinite geometric series

Elementary mathematics is predominantly about equations and identities. But it is often impossible to capture important mathematical relations in the form of exact equations. This is one reason why inequalities become more central as we progress; another reason is because inequalities allow us to make precise statements about certain infinite processes.

One of the simplest infinite process arises in the formula for the “sum” of an infinite geometric series:

1+r+r2+r3++rn+ (for ever).

Despite the use of the familiar-looking “+” signs, this can be no ordinary addition. Ordinary addition is defined for two summands; and by repeating the process, we can add three summands (thanks in part to the associative law of addition). We can then add four, or any finite number of summands. But this does not allow us to “add” infinitely many terms as in the above sum. To get round this we combine ordinary addition (of finitely many terms) and simple inequalities to find a new way of giving a meaning to the above “endless sum”. In Problem 116 you used the factorisation

rn+11=(r1)1+r+r2+r3++rn

to derive the closed formula:

1+r+r2+r3++rn=1rn+11r.

This formula for the sum of a finite geometric series can be rewritten in the form

1+r+r2+r3++rn=11rrn+11r.

At first sight, this may not look like a clever move! However, it separates the part that is independent of n from the part on the RHS that depends on n; and it allows us to see how the second part behaves as n gets large:

when |r|<1, successive powers of r get smaller and smaller and converge rapidly towards 0,

so the above form of the identity may be interpreted as having the form:

1+r+r2+r3++rn=11r — (an “error term”).

Moreover if |r|<1, then the “error term” converges towards 0 as n. In particular, if 1>r>0, the error term is always positive, so we have proved, for all n1:

1+r+r2+r3++rn<11r

and

the difference between the two sides tends rapidly to 0 as n.

We then make the natural (but bold) step to interpret this, when |r|<1, as offering a new definition which explains precisely what is meant by the endless sum

1+r+r2+r3+ (for ever),

declaring that, when |r|<1,

1+r+r2+r3+ (for ever) = 11r.

More generally, if we multiply every term by a, we see that

a+ar+ar2+ar3+ (for ever) = a1r.

Problem 243 Interpret the recurring decimal 0.037037037 ··· (for ever) as an infinite geometric series, and hence find its value as a fraction.

Problem 244 Interpret the following endless processes as infinite geometric series.

(a) A square cake is cut into four quarters, with two perpendicular cuts through the centre, parallel to the sides. Three people receive one quarter each - leaving a smaller square piece of cake. This smaller piece is then cut in the same way into four quarters, and each person receives one (even smaller) piece - leaving an even smaller residual square piece, which is then cut in the same way. And so on for ever. What fraction of the original cake does each person receive as a result of this endless process?

(b) I give you a whole cake. Half a minute later, you give me half the cake back. One quarter of a minute later, I return one quarter of the cake to you. One eighth of a minute later you return one eighth of the cake to me. And so on. Adding the successive time intervals, we see that

12+14+18+ (for ever) = 1,

so the whole process is completed in exactly 1 minute. How much of the cake do I have at the end, and how much do you have?

Problem 245 When John von Neumann (1903-1957) was seriously ill in hospital, a visitor tried (rather insensitively) to distract him with the following elementary mathematics problem.

Have you heard the one about the two trains and the fly? Two trains are on a collision course on the same track, each travelling at 30 km/h. A super-fly starts on Train A when the trains are 120 km apart, and flies at a constant speed of 50 km/h - from Train A to Train B, then back to Train A, and so on. Eventually the two trains collide and the fly is squashed. How far did the fly travel before this sad outcome?

6.5. Some classical inequalities

The fact that our formula for the sum of a geometric series gives us an exact sum is very unusual - and hence very precious. For almost all other infinite series - no matter how natural, or beautiful, they may seem - you can be fairly sure that there is no obvious exact formula for the value of the sum. Hence in those cases where we happen to know the exact value, you may infer that it took the best efforts of some of the finest mathematical minds to discover what we know.

One way in which we can make a little progress in estimating the value of an infinite series is to obtain an inequality by comparing the given sum with a geometric series.

Problem 246

(a)(i) Explain why

132<122,

so

122+132<222=12.

(ii) Explain why 152,162,172 are all <142, so

142+152+162+172<442=14.

(b) Use part (a) to prove that

1 1 2 + 1 2 2 + 1 3 2 ++ 1 n 2 <2 , for all n1.

(c) Conclude that the endless sum

112+122+132++1n2+ (for ever)

has a definite value, and that this value lies somewhere between 1712 and 2.

The next problem presents a rather different way of deriving a similar equality. Once the relevant inequality has been guessed, or given (see Problem 247(a) and (b)), the proof by mathematical induction is often relatively straightforward. And after a little thought about Problem 246, it should be clear that much of the inaccuracy in the general inequality arises from the rather poor approximations made for the first few terms (when n = 1, when n = 2, when n = 3, etc.); hence by keeping the first few terms as they are, and only approximating for n2, or n3, or n4, we can often prove a sharper result.

Problem 247

(a) Prove by induction that

112+122+132++1n221n, for all n1.

(b) Prove by induction that

112+122+132++1n2<1.681n for all n4.

The infinite sum

112+122+132++1n2+ (for ever)

is a historical classic, and has many instructive stories to tell. Recall that, in Problems 54, 62, 63, 236, 237, 238 you found closed formulae for the sums

1+2+3++n

12+22+32++n2

13+23+33++n3

and for the sums

1×2+2×3+3×4++(n1)n

1×2×3+2×3×4+3×4×5++(n2)(n1)n.

Each of these expressions has a “natural” feel to it, and invites us to believe that there must be an equally natural compact answer representing the sum. In Problem 235 you took this idea one step further by finding a beautiful closed expression for the sum

11·2+12·3+13·4++1n(n+1)=11n+1

When we began to consider infinite series, we found the elegant closed formula

1+r+r2+r3++rn=11rrn+11r.

We then observed that the final term on the RHS could be viewed as an “error term”, indicating the amount by which the LHS differs from 11r, and noticed that, for any given value of r between −1 and +1, this error term “tends towards 0 as the power n increases”. We interpreted this as indicating that one could assign a value to the endless sum

1+r+r2+r3+ (for ever) = 11r.

In the same way, in the elegant closed formula

11·2+12·3+13·4++1n(n+1)=11n+1

the final term on the RHS indicates the amount by which the finite sum on the LHS differs from 1; and since this “error term” tends towards 0 as n increases, we may assign a value to the endless sum

11·2+12·3+13·4+ (for ever) = 1.

It is therefore natural to ask whether other infinite series, such as

112+122+132++1n2+ (for ever)

may also be assigned some natural finite value. And since the series is purely numerical (without any variable parameters, such as the “r” in the geometric series formula), this answer should be a strictly numerical answer. And it should be exact - though all we have managed to prove so far (in Problems 246 and 247) is that this numerical answer lies somewhere between 1712 and 1.68.

This question arose naturally in the middle of the seventeenth century, when mathematicians were beginning to explore all sorts of infinite series (or “sums that go on for ever”). With a little more work in the spirit of Problems 246 and 247 one could find a much more accurate approximate value. But what is wanted is an exact expression, not an unenlightening decimal approximation. This aspiration has a serious mathematical basis, and is not just some purist preference for elegance. The actual decimal value is very close to

1.649934.

But this conveys no structural information. One is left with no hint as to why the sum has this value. In contrast, the eventual form of the exact expression suggests connections whose significance remains of interest to this day.

The greatest minds of the seventeenth and early eighteenth century tried to find an exact value for the infinite sum - and failed. The problem became known as the Basel problem (after Jakob Bernoulli (1654-1705) who popularised the problem in 1689 - one of several members of the Bernoulli family who were all associated with the University in Basel). The problem was finally solved in 1735 - in truly breathtaking style - by the young Leonhard Euler (1707-1783) (who was at the time also in Basel). The answer

π26

illustrates the final sentence of the preceding paragraph in unexpected ways, which we are still trying to understand.

In the next problem you are invited to apply similar ideas to an even more important series. Part (a) provides a relatively crude first analysis. Part (b) attacks the same question; but it does so using algebra and induction (rather than the formula for the sum of a geometric series) in a way that is then further refined in part (c).

Problem 248

(a)(i) Choose a suitable r and prove that

11!+12!++1n!<1+r+r2++rn1<2.

(ii) Conclude that

10!+11!+12!++1n!<3 for every n0,

and hence that the endless sum

10!+11!+12!++1n!+ (forever)

can be assigned a value “e” satisfying 2<e3.

(b) (i) Prove by induction that

10!+11!+12!++1n!31n.n!, for all n1.

(ii) Use part (i) to conclude that the endless sum

10!+11!+12!++1n!+ (forever)

can be assigned a definite value “e”, and that this value lies somewhere between 2.5 and 3.

(c) (It may help to read the Note at the start of the solution to part (c) before attempting parts (c), (d).)

(i) Prove by induction that

10!+11!+12!++1n!2.751n.n! for all n2.

(ii) Use part (i) to conclude that the endless sum

10!+11!+12!++1n!+ (for ever)

can be assigned a definite value “e”, and that this value lies somewhere between 2.6 and 2.75.

(d) (i) Prove by induction that

10!+11!+12!++1n!2.722(forever)1n.n!,foralln3.

(ii) Use part (i) to conclude that the endless sum

10!+11!+12!++1n!+ (for ever)

can be assigned a definite value “e”, and that this value lies somewhere between 2.708 and 2.7222... (forever).

We end this section with one more inequality in the spirit of this section, and two rather different inequalities whose significance will become clear later.

Problem 249 Prove by induction that

11+12+13++1nn, forall n1.

Problem 250 Let a, b be real numbers such that ab, and a+b>0. Prove by induction that

2n1an+bn(a+b)n, for all n1.

Problem 251 Let x be any real number 1. Prove by induction that

(1+x)n1+nx, for all n1

6.6. The harmonic series

The great foundation of mathematics is the principle of contradiction, or of identity, that is to say that a statement cannot be true and false at the same time, and that thus A is A, and cannot be not A. And this single principle is enough to prove the whole of arithmetic and the whole of geometry, that is to say all mathematical principles.

Gottfried W. Leibniz (1646-1716)

We have seen how some infinite series, or sums that go on for ever, can be assigned a finite value for their sum:

1+r+r2+r3+(for ever)=11r 112+123+134++1n(n+1)+(for ever)=1 112+122+132++1n2+(for ever)=π26 10!+11!+12!++1n!+(for ever)=e.

We say that these series converge (meaning that they can be assigned a finite value).

This section is concerned with another very natural series, the so-called harmonic series

11+12+13++1n+(for ever).

It is not entirely clear why this is called the harmonic series. The natural overtones that arise in connection with plucking a stretched string (as with a guitar or a harp) have wavelengths that are 12 the basic wavelength, or 13 of the basic wavelength, and so on. It is also true that, just as each term of an arithmetic series is the arithmetic mean of its two neighbours, and each term of a geometric series is the geometric mean of its two neighbours, so each term of the harmonic series after the first is equal to the harmonic mean (see Problems 85., 89.) of its two neighbours:

1k=2(1k1)1+(1k+1)1.

Unlike the first two series above, there is no obvious closed formula for the finite sum

sn=11+12+13++1n.

Certainly the sequence of successive sums

s1=1,s2=32,s3=116,s4=2512,s5=13760,

does not suggest any general pattern.

Problem 252 Suppose we denote by S the “value” of the endless sum

11+12+13++1n+(for ever)

(i) Write out the endless sum corresponding to “12S”.

(ii) Remove the terms of this endless sum from the endless sum S, to obtain another endless sum corresponding to “S12S=12S.

(iii) Compare the first term of the series in (i) (namely 12) with the first term in the series in (ii) (namely 1); compare the second term in the series in (i) with the second term in the series in (ii); and so on. What do you notice?

The Leibniz quotation above emphasizes that the reliability of mathematics stems from a single principle – namely the refusal to tolerate a contradiction. We have already made explicit use of this principle from time to time (see, for example, the solution to Problem 125.). The message is simple: whenever we hit a contradiction, we know that we have “gone wrong” – either by making an error in calculation or logic, or by beginning with a false assumption. In Problem 252. the observations you were expected to make are paradoxical: you obtained two different series, which both correspond to “12S”, but every term in one series is larger than the corresponding term in the other! What one can conclude may not be entirely clear. But it is certainly clear that something is wrong: we have somehow created a contradiction. The three steps ((i), (ii), (iii)) appear to be relatively sensible. But the final observation “12S<12S” (since 12<1, 14<13, etc.) makes no sense. And the only obvious assumption we have made is to assume that the endless sum

11+12+13++1n+(for ever)

can be assigned a value “S”, which can then be manipulated as though it were a number.

The conclusion would seem to be that, whether or not the endless sum has a meaning, it cannot be assigned a value in this way. We say that the series diverges. Each finite sum

11+12+13++1n

has a value, and these values “grow more and more slowly” as n increases:

  • the first term immediately makes the sum = 1
  • it takes 4 terms to obtain a sum > 2;
  • it takes 11 terms to obtain a sum > 3; and
  • it takes 12367 terms before the series reaches a sum > 10.

However, this slow growth is not enough to guarantee that the corresponding endless sum corresponds to a finite numerical value.

The danger signals should already have been apparent in Problem 249., where you proved that

11+12+13++1nn

The nth term 1n tends to 0 as n increases; so the finite sums grow ever more slowly as n increases. However, the LHS can be made larger than any integer K simply by taking K2 terms. Hence there is no way to assign a finite value to the endless sum

11+12+13++1n+(for ever).

Problem 253.

(a)(i) Explain why

12+13<1.

(ii) Explain why

14+15+16+17<1.

(iii) Extend parts (i) and (ii) to prove that

11+12+13++12n1<n, for all n2.

(iv) Finally use the fact that, when n3,

12n<1213

to modify the proof in (iii) slightly, and hence show that

11+12+13++12n<n, for all n3.

(b)(i) Explain why

13+14>12.

(ii) Explain why

15+16+17+18>12.

(iii) Extend parts (i) and (ii) to prove that

11+12+13++12n>1+n2, for all n2.

(c) Combine parts (a) and (b) to show that, for all n2, we have the two inequalities

1+n2<11+12+13++12n<n.

Conclude that the endless sum

11+12+13++1n+ (for ever)

cannot be assigned a finite value.

The result in Problem 253.(c) has an unexpected consequence.

Problem 254 Imagine that you have an unlimited supply of identical rectangular strips of length 2. (Identical empty plastic CD cases can serve as a useful illustration, provided one focuses on their rectangular side profile, rather than the almost square frontal cross-section.) The goal is to construct a ‘stack’ in such a way as to stick out as far as possible beyond a table edge. One strip balances exactly at its midpoint, so can protrude a total distance of 1 without tipping over.

(a) Arrange a stack of n strips of length 2, one on top of the other, with the bottom strip protruding distance 1n beyond the edge of the table, the second strip from the bottom protruding 1n1 beyond the leading edge of the bottom strip, the third strip from the bottom protruding 1n2 beyond the leading edge of the strip below it, and so on until the (n1)th strip from the bottom protrudes distance 12 beyond the leading edge of the strip below it, and the top strip protrudes distance 1 beyond the leading edge of the strip below it (see Figure 10). Prove that a stack of n identical strips arranged in this way will just avoid tipping over the table edge.

(b) Conclude that we can choose n so that an arrangement of n strips can (in theory) protrude as far beyond the edge of the table as we wish – without tipping.

The next problem illustrates, in the context of the harmonic series, what is in fact a completely general phenomenon: an endless sum of steadily decreasing positive terms may converge or diverge; but provided the terms themselves converge to 0, then the the corresponding “alternating sum” – where the same terms are combined but with alternately positive and negative signs – always converges.

Figure 10: Overhanging strips, n = 10.

Problem 255

(a) Let

sn=1112+1314+15±1n

(where the final operation is “+” if n is odd and “-” if n is even).

(i) Prove that

s2n2<s2n<s2m+1<s2m1, for all m,n1 .

(ii) Conclude that the endless alternating sum

1112+1314+15 (for ever)

can be assigned a value s that lies somewhere between s6=3760 and s5=4760.

(b) Let

a1,a2,a3,

be an endless, decreasing sequence of positive terms (that is, an+1<an for all n1). Suppose that the sequence of terms an converges to 0 as n.

(i) Let

sn=a1a2+a3a4+a5±an

(where the final operation is “+” if n is odd and “−” if n is even). Prove that

s2n2<s2n<s2m+1<s2m1, for all m,n1.

(ii) Conclude that the endless alternating sum

a1a2+a3a4+a5 (for ever)

can be assigned a value s that lies somewhere between s2=a1a2 and s3=a1a2+a3.

Just as with the series

112+122+132++1n2+(for ever) 10!+11!+12!++1n!+(for ever),

we can show relatively easily that

1112+1314+15(for ever)

can be assigned a value s. It is far less clear whether this value has a familiar name! (It is in fact equal to the natural logarithm of 2: “loge2”.) A similarly intriguing series is the alternating series of odd terms from the harmonic series:

1113+1517+19(for ever)

You should be able to show that this endless series can be assigned a value somewhere between s2=23 and s3=1315; but you are most unlikely to guess that its value is equal to π4. This was first discovered in 1674 by Leibniz (1646-1716). One way to obtain the result is using the integral of (1+x2)1 from 0 to 1: on the one hand the integral is equal to arctanx evaluated when x=1 (that is, π4); on the other hand, we can expand the integrand as a power series 1x2+x4x6+, integrate term by term, and prove that the resulting series converges when x=1. (It does indeed converge, though it does so very, very slowly.)

The fact that the alternating harmonic series has the value loge2 seems to have been first shown by Euler (1707-1783), using the power series expansion for log(1+x).

6.7. Induction in geometry, combinatorics and number theory

We turn next to a mixed collection of problems designed to highlight a range of applications.

Problem 256 Let f1=2, fk+1=fk(fk+1). Prove by induction that fk has at least k distinct prime factors.

Problem 257

(a) Prove by induction that n points on a straight line divide the line into n+1 parts.

(b)(i) By experimenting with small values of n, guess a formula Rn for the maximum number of regions which can be created in the plane by an array of n straight lines.

(ii) Prove by induction that n straight lines in the plane divide the plane into at most Rn regions.

(c)(i) By experimenting with small values of n, guess a formula Sn for the maximum number of regions which can be created in 3-dimensions by an array of n planes.

(ii) Prove by induction that n planes in 3-dimensions divide space into at most Sn regions.

Problem 258 Given a square, prove that, for each n6, the initial square can be cut into n squares (of possibly different sizes).

Problem 259 A tree is a connected graph, or network, consisting of vertices and edges, but with no cycles (or circuits). Prove that a tree with n vertices has exactly n1 edges.

The next problem concerns spherical polyhedra. A spherical polyhedron is a polyhedral surface in 3-dimensions, which can be inflated to form a sphere (where we assume that the faces and edges can stretch as required). For example, a cube is a spherical polyhedron; but the surface of a picture frame is not. A spherical polyhedron has

  • faces (flat 2-dimensional polygons, which can be stretched to take the form of a disc),
  • edges (1-dimensional line segments, where exactly two faces meet), and
  • vertices (0-dimensional points, where several faces and edges meet, in such a way that they form a single cycle around the vertex).

Each face must clearly have at least 3 edges; and there must be at least three edges and three faces meeting at each vertex.

If a spherical polyhedron has V vertices, E edges, and F faces, then the numbers V, E, F satisfy Euler's formula

VE+F=2.

For example, a cube has V=8 vertices, E=12 edges, and F=6 faces, and 812+6=2.

Problem 260

(a) (i) Describe a spherical polyhedron with exactly 6 edges.

(ii) Describe a spherical polyhedron with exactly 8 edges.

(b) Prove that no spherical polyhedron can have exactly 7 edges.

(c) Prove that for every n8, there exists a spherical polyhedron with n edges.

Problem 261 A map is a (finite) collection of regions in the plane, each with a boundary, or border, that is `polygonal' in the sense that it consists of a single sequence of distinct vertices and – possibly curved – edges, that separates the plane into two parts, one of which is the polygonal region itself. A map can be properly coloured if each region can be assigned a colour so that each pair of neighbouring regions (sharing an edge) always receive different colours. Prove that the regions of such a map can be properly coloured with just two colours if and only if an even number of edges meet at each vertex.

Problem 262 (Gray codes) There are 2n sequences of length n consisting of 0s and 1s. Prove that, for each n2, these sequences can be arranged in a cyclic list such that any two neighbouring sequences (including the last and the first) differ in exactly one coordinate position.

Problem 263 (Calkin-Wilf tree) The binary tree in the plane has a distinguished vertex as `root', and is constructed inductively. The root is joined to two new vertices; and each new vertex is then joined to two further new vertices – with the construction process continuing for ever (Figure 11). Label the vertices of the binary tree with positive fractions as follows:

  • the root is given the label 11
  • whenever we know the label ij of a ‘parent’ vertex, we label its `left descendant' as ii+j, and its `right descendant' i+jj.

(a) Prove that every positive rational rs occurs once and only once as a label, and that it occurs in its lowest terms.

(b) Prove that the labels are left-right symmetric in the sense that labels in corresponding left and right positions are reciprocals of each other.

Problem 264 A collection of n intervals on the x-axis is such that every pair of intervals have a point in common. Prove that all n intervals must then have at least one point in common.

6.8. Two problems

Problem 265 Several identical tanks of water sit on a horizontal base. Each pair of tanks is connected with a pipe at ground level controlled by a valve, or tap. When a valve is opened, the water level in the two connected tanks becomes equal (to the average, or mean, of the initial levels). Suppose we start with tank T which contains the least amount of water. The aim is to open and close valves in a sequence that will lead to the final water level in tank T being as high as possible. In what order should we make these connections?

Figure 11: A (rooted) binary tree.

Problem 266 I have two flasks. One is ‘empty’, but still contains a residue of a dangerous chemical; the other contains a fixed amount of solvent that can be used to wash away the remaining traces of the dangerous chemical. What is the best way to use the fixed quantity of solvent? Should I use it all at once to wash out the first flask? Or should I first wash out the flask using just half of the solvent, and then repeat with the other half? Or is there a better way of using the available solvent to remove as much as possible of the dangerous chemical?

6.8. Infinite descent

In this final section we touch upon an important variation on mathematical induction. This variation is well-illustrated by the next (probably familiar) problem.

Problem 267 Write out for yourself the following standard proof that 2 is irrational.

(i) Suppose to the contrary that 2 is rational. Then 2=mn for some positive integers m, n. Prove first that m must be even.

(ii) Write m=2m, where m is also an integer. Show that n must also be even.

(iii) How does this lead to a contradiction?

Problem 267. has the classic form of a proof which reaches a contradiction by infinite descent.

  1. We start with a claim which we wish to prove is true. Often when we do not know how to begin, it makes sense to ask what would happen if the claim were false. This then guarantees that there must be some counterexample, which satisfies the given hypothesis, but which fails to satisfy the asserted conclusion.
  2. Infinite descent becomes an option whenever each such counterexample gives rise to some positive integer parameter n (such as the denominator in Problem 267.(i)).
  3. Infinite descent becomes a reality, if one can prove that the existence of the initial counterexample leads to a construction that produces a counterexample with a smaller value n of the parameter n, since repeating this step then gives rise to an endlessly decreasing sequence n>n>n''>>0 of positive integers, which is impossible (since such a chain can have length at most n).
  4. Hence the initial assumption that the claim was false must itself be false – so the claim must be true (as required).

Proof by “infinite descent” is an invaluable tool. But it is important to realise that the method is essentially a variation on proof by mathematical induction. As a first step in this direction it is worth reinterpreting Problem 267. as an induction proof.

Problem 268 Let P(n) be the statement:

2 cannot be written as a fraction with positive denominator n”.

(i) Explain why P(1) is true.

(ii) Suppose that P(k) is true for some k1. Use the proof in Problem 267. to show that P(k+1) must then be true as well.

(iii) Conclude that P(n) is true for all n1, whence 2 must be irrational.

Problem 268. shows that, in the particular case of Problem 267. one can translate the standard proof that “2 is irrational” into a proof by induction. But much more is true. The contradiction arising in step 3. above is an application of an important principle, namely

The Least Element Principle: Every non-empty set S of positive integers has a smallest element.

The Least Element Principle is equivalent to The Principle of Mathematical Induction which we stated at the beginning of the chapter:

The Principle of Mathematical Induction: If a subset S of the positive integers

  • contains the integer “1”, and has the property that
  • whenever an integer k is in the set S, then the next integer k+1 is always in S too,
then S contains all positive integers.

Problem 269

(a) Assume the Least Element Principle. Suppose a subset T of the positive integers contains the integer “1”, and that whenever k is in the set T, then k+1 is also in the set T. Let S be the set of all positive integers which are not in the set T. Conclude that S must be empty, and hence that T contains all positive integers.

(b) Assume the Principle of Mathematical Induction. Let T be a non-empty set of positive integers, and suppose that T does not have a smallest element. Let S be the set of all positive integers which do not belong to the set T. Prove that “1” must belong to S, and that whenever the positive integer k belongs to S, then so does k+1. Derive the contradiction that T must be empty, contrary to assumption. Conclude that T must in fact have a smallest element.

To round off this final chapter you are invited to devise a rather different proof of the irrationality of 2.

Problem 270 This sequence of constructions presumes that we know – for example, by Pythagoras' Theorem – that, in any square OPQR, the ratio

“diagonal: side” = OQ: OP=2:1.

Let OPQR be a square. Let the circle with centre Q and passing through P meet OQ¯ at P. Construct the perpendicular to OQ¯ at P, and let this meet OR¯ at Q.

(i) Explain why OP¯=PQ¯. Construct the point R to complete the square OPQR.

(ii) Join QQ¯. Explain why PQ¯=RQ¯.

(iii) Suppose OQ¯:OP¯=m:n. Conclude that OQ¯:OP¯=2nm:mn.

(iv) Prove that n<m<2n, and hence that 0<mn<n, 0<2nm.

(v) Explain how, if m, n can be chosen to be positive integers, the above sequence of steps sets up an “infinite descent” – which is impossible.

6.10. Chapter 6: Comments and solutions

Note: It is important to separate the underlying idea of “induction” from the formal way we have chosen to present proofs. As ever in mathematics, the ideas are what matter most. But the process of struggling with (and slowly coming to understand why we need) the formal structure behind the written proofs is part of the way the ideas are tamed and organised.

Readers should not be intimidated by the physical extent of the solutions to this chapter. As explained in the main text it is important for all readers to review the way they approach induction proofs: so we have erred in favour of completeness – knowing that as each reader becomes more confident, s/he will increasingly compress, or abbreviate, some of the steps.

228.

(a) Yes.

(b) Yes.

2×3×5×7×11+1=2311, and 2311=48.07 , so we only need to check prime factors up to 47 .

(c) No.

2×3×5×7×11×13+1=30031,

and 30031=173.29 so we might have to check all 40 possible prime factors up to 173. However, we only have to start at 17 [Why?], and checking with a calculator is very quick. In fact 30031 factorises rather prettily as 59×509.

229. Note: The statement in the problem includes the quantifierfor all n1”.

What is to be proved is the compound statement

P(n) is true for all n1”.

In contrast, each individual statement P(n) refers to a single value of n.

It is essential to be clear when you are dealing with the compound statement, and when you are referring to some particular statement P(1), or P(n), or P(k).

Let P(n) be the statement:

52n+224n25 is divisible by 576”.

P(1) is the statement:

5424×125 is divisible by 576”.

That is:

62549=576 is divisible by 576”,

which is evidently true.

  • Now suppose that we know P(k) is true for some k1. We must show that P(k+1) is then also true.

To prove that P(k+1) is true, we have to consider the statement P(k+1). It is no use starting with P(k). However, since we know that P(k)) is true, we are free to use it at any stage if it turns out to be useful.

To prove that P(k+1) is true, we have to show that

52(k+1)+224(k+1)25 is divisible by 576”.

So we must start with 52(k+1)+224(k+1)25 and try to “simplify” it (knowing that “simplify” in this case means “rewrite it in a way that involves 52k+224k25”).

5 2 ( k + 1 ) + 2 - 24 ( k + 1 ) - 25 = [ 5 2 k + 4 ] - 24 k - 24 - 25 = [ 5 2 ( 5 2 k + 2 - 24 k - 25 ) + 5 2 ( 24 k ) + 5 2 25 ] - 24 k - ( 24 + 25 ) = 5 2 ( 5 2 k + 2 - 24 k - 25 ) + [ ( 5 2 - 1 ) × ( 24 k ) ] + [ 5 2 × 25 - 24 - 25 ] = 5 2 ( 5 2 k + 2 - 24 k - 25 ) + 2 4 2 k + [ 5 2 × 25 - 24 - 25 ] = 5 2 ( 5 2 k + 2 - 24 k - 25 ) + 2 4 2 k + [ 5 4 - 24 - 25 ] .

The first term on the RHS is a multiple of (52k+224k25), so is divisible by 576 (since we know that P(k) is true); the second term on the RHS is a multiple of 242 = 576; and the third term on the RHS is the expression arising in P(1), which we saw is equal to 576.

the whole RHS is divisible by 576

the LHS is divisible by 576, so P(k+1) is true.

Hence

  • P(1) is true; and
  • whenever P(k) is true for some k1, we have proved that P(k+1) must be true.

P(n) is true for all n1.

230. Let P(n) be the statement:

“the angles of any p-gon, for any value of p with 3pn, have sum exactly (p2)π radians”.

  1. P(3) is the statement:

    “the angles of any triangle have sum π radians”.

    This is a known fact: given triangle ΔABC, draw the line XAY through A parallel to BC, with X on the same side of AC as B and Y on the same side of AB as C. Then XAB=CBA and YAC=BCA (alternate angles), so

    B+A+C=XAB+A+YAC=XAY=π.
  2. Now we suppose that P(k) is known to be true for some k3. We must show that P(k+1) is then necessarily true.

To prove that P(k+1) is true, we have to consider the statement P(k+1): that is,

“the angles of a p-gon, for any value of p with 3pk+1, have sum exactly (p2)π radians”.

This can be reworded by splitting it into two parts:

“the angles of any p-gon for 3pk have sum exactly (p2)π radians;”

and

“the angles of any (k + 1)-gon have sum exactly ((k+1)2)π radians”.

The first part of this revised version is precisely the statement P(k), which we suppose is known to be true. So the crux of the matter is to prove the second part – namely that the angles of any (k + 1)-gon have sum (k1)π.

Let A0A1A2Ak be any (k + 1)-gon.

[Note: The usual move at this point is to say “draw the chord AkA1 to cut the polygon into the triangle AkA1A0 (with angle sum π (by P(3)), and the k-gon A1A2Ak (with angle sum (k2)π (by P(k)), whence we can add to see that A0A1A2Ak has angle sum ((k+1)2)π. However, this only works

  • if the triangle AkA1A0 “sticks out” rather than in, and
  • if no other vertices or edges of the (k+ 1)-gon encroach into the part that is cut off – which can only be guaranteed if the polygon is “convex”.

So what is usually presented as a “proof” does not work in general.

If we want to prove the general result – for polygons of all shapes – we have to get round this unwarranted assumption. Experiment may persuade you that “there is always some vertex that sticks out and which can be safely “cut off”; but it is not at all clear how to prove this fact (we know of no simple proof). So we have to find another way.]

Consider the vertex A1, and its two neighbours A0 and A2.

Imagine each half-line, which starts at A1, and which sets off into the interior of the polygon. Because the polygon is finite, each such half-line defines a line segment A1X¯, where X is the next point of the polygon which the half line hits (that is, X is one of the vertices Am, or a point on one of the sides AmAm+1¯).

Consider the locus of all such points X as the half line swings from A1A0¯ (produced) to A1A2¯ (produced). There are two possibilities: either

(a) these points X all belong to a single side of the polygon; or

(b) they don't.

(a) In the first case none of the vertices or sides of the polygon A0A1A2Ak intrude into the interior of the triangle A0A1A2, so the chord A0A2¯ separates the (k + 1)-gon A0A1A2Ak into a triangle A0A1A2 and a k-gon A0A2A3Ak. The angle sum of A0A1A2Ak is then equal to the sum of (i) the angle sum of the triangle A0A1A2 and (ii) the angle sum of A0A2A3Ak – which are equal to π and (k2)π respectively (by P(k)). So the angle sum of the (k + 1)-gon A0A2A3Ak is equal to ((k+1)2)π as required.

(b) In the second case, as the half-line A1X rotates from A1A0 to A1A2, the point X must at some instant switch from lying on one side of the polygon to lying on another side; at the very instant where X switches sides, X=Am must be a vertex of the polygon.

Because of the way the point X was chosen, the chord A1X¯=A1Am¯ does not meet any other point of the (k + 1)-gon A0A1A2Ak, and so splits the (k + 1)-gon into an m-gon A1A2A3Am (with angle sum (m2)π by P(k)) and a (k - m + 3)-gon AmAm+1Am+2AkA0A1 (with angle sum (km+1)π by P(k)). So the (k + 1)-gon A0A1A2Ak has angle sum ((k+1)2)π as required.

Hence P(k+1) is true.

P(n) is true for all n3.

231. Let P(n) be the statement

1+3+5++(2n1)=n2.

  • LHS of P(1)=1; RHS of P(1)=12. Since these two are equal, P(1) is true.
  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    1+3+5++(2k1)=k2.

    We wish to prove that P(k+1) must then be true.

    Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1):

    LHS of P ( k + 1 ) = 1 + 3 + 5 + + ( 2 ( k + 1 ) - 1 ) = ( 1 + 3 + 5 + + ( 2 k - 1 ) ) + ( 2 k + 1 ) .

    If we now use P(k), which we are supposing to be true, then the first bracket is equal to k2, so this sum is equal to:

    = k 2 + ( 2 k + 1 ) = ( k + 1 ) 2 = RHS of P ( k + 1 ) .

    Hence P(k+1) holds.

Combining these two bullet points then shows that “P(n) holds, for all n1”.

232.

(a) The only way to learn is by trying and failing; then trying again and failing slightly better! So don't give up too quickly. It is natural to try to relate each term to the one before. You may then notice that each term is slightly less than 3 times the previous term.

(b) Note: The recurrence relation for un involves the two previous terms. So when we assume that P(k) is known to be true and try to prove P(k+1), the recurrence relation for uk+1 will involve uk and uk1, so P(n) needs to be formulated to ensure that we can use closed expressions for both these terms. For the same reason, the induction proof has to start by showing that both P(0) and P(1) are true.

Let P(n) be the statement:

um=2m+3m for all m, 0mn”.

  • LHS of P(0)=u0=2; RHS of P(0)=20+30=1+1. Since these two are equal, P(0) is true.

    P(1) combines P(0), and the equality of u1=5 and 21+31; since these two are equal, P(1) is true.

  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    um=2m+3m for all m, 0mk.”

    We wish to prove that P(k+1) must then be true.

    Now P(k+1) requires us to prove that

    um=2m+3m for all m, 0mk+1.”

    Most of this is guaranteed by P(k), which we assume to be true. It remains for us to check that the equality holds for uk+1. We know that

    uk+1=5uk6uk1.

    And we may use P(k)), which we are supposing to be true, to conclude that:

    u k + 1 = 5 ( 2 k + 3 k ) - 6 ( 2 k - 1 + 3 k - 1 ) = ( 10 - 6 ) 2 k - 1 + ( 15 - 6 ) 3 k - 1 = 2 k + 1 + 3 k + 1 .

    Hence P(k+1) holds.

Combining these two bullet points then shows that “P(n) holds, for all n0”.

233. Let P(n) be the statement:

Fm=αmβm5 for all m, 0mn”,

where α=1+52 and β=152.

  • LHS of P(0)=F0=0; RHS of P(0)=115=0. Since these two are equal, P(0) is true.

    LHS of P(1)=F1=1; RHS of P(1)=αβ5=1. Since these two are equal, P(1) is true.

  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    Fm=αmβm5 for all m, 0mk.”

    We wish to prove that P(k+1) must then be true.

    Now P(k+1) requires us to prove that

    Fm=αmβm5 for all m, 0mk+1.”

    Most of this is guaranteed by P(k), which we assume to be true. It remains to check this for Fk+1. We know that

    Fk+1=Fk+Fk1.

    And we may use P(k), which we are supposing to be true to conclude that:

    F k + 1 = α k - β k 5 + α k - 1 - β k - 1 5 = α k + α k - 1 5 - β k + β k - 1 5 = α k + 1 - β k + 1 5

    (since α and β are roots of the equation x2x1=0) Hence P(k+1) holds.

Combining these two bullet points then shows that “P(n) holds, for all n1”.

Note: You may understand the above solution and yet wonder how such a formula could be discovered. The answer is fairly simple. There is a general theory about linear recurrence relations which guarantees that the set of all solutions of a second order recurrence (that is, a recurrence in which each term depends on the two previous terms) is “two dimensional” (that is, it is just like the familiar 2D plane, where every vector (p, q) is a combination of the two “base vectors” (1, 0) and (0, 1):

(p,q)=p(1,0)+q(0,1)).

Once we know this, it remains:

  • to find two special solutions (like the vectors (1, 0) and (0, 1) in the plane), which we do here by looking for sequences of the form “1,x,x2,x3,” that satisfy the recurrence, which implies that 1+x=x2, so x=α, or x=β;
  • then to choose a linear combination Fm=pαm+qβm of these two power solutions to give the correct first two terms: 0=F0=p+q, 1=F1=pα+qβ, so p=15, q=15.

234. Let P(n) be the statement:

52n+1·2n+2+3n+2·22n+1 is divisible by 19”.

  • P(0) is the statement: “5×4+9×2 is divisible by 19”, which is true.
  • Now suppose that we know that P(k) is true for some k0. We must show that P(k+1) is then also true.
  • To prove that P(k+1) is true, we have to show that

    52k+3·2k+3+3k+3·22k+3 is divisible by 19”.

    5 2 k + 3 2 k + 3 + 3 k + 3 2 2 k + 3 = 5 2 2 ( 5 2 k + 1 2 k + 2 + 3 k + 2 2 2 k + 1 ) - 5 2 2 3 k + 2 2 2 k + 1 + 3 k + 3 2 2 k + 3 = 5 2 2 ( 5 2 k + 1 2 k + 2 + 3 k + 2 2 2 k + 1 ) - ( 5 2 - 3 2 ) 3 k + 2 2 2 k + 2 .

    The bracket in the first term on the RHS is divisible by 19 (by P(k)), and the bracket in the second term is equal to 19. Hence both terms on the RHS are divisible by 19, so the RHS is divisible by 19. Therefore the LHS is also divisible by 19, so P(k+1) is true.

P(n) is true for all n0.

235.

Note: The proofs of identities such as those in Problem 235., which are given in many introductory texts, ignore the lessons of the previous two problems. In particular,

• they often fail to distinguish between

– the single statement P(n) for a particular n, and

– the “quantified” result to be proved (“for all n1”),

and

• they proceed in the `wrong' direction (e.g. starting with the identity P(n) and “adding the same to both sides”).

This latter strategy is psychologically and didactically misleading – even though it can be justified logically when proving very simple identities. In these very simple cases, each statement P(n) to be proved is unusual in that it refers to exactly one configuration, or equation, for each n. And since there is exactly one configuration for each n, the configuration or identity for k+1 can often be obtained by fiddling with the configuration for k. In contrast, in Problem 230., for each value of n, there is a bewildering variety of possible polygons with n vertices, ranging from regular polygons to the most convoluted, re-entrant shapes: the statement P(n) makes an assertion about all such configurations, and there is no way of knowing whether we can obtain all such configurations for k+1 in a uniform way by fiddling with some configuration for k.

Readers should try to write each proof in the intended spirit, and to learn from the solutions – since this style has been chosen to highlight what mathematical induction is really about, and it is this approach that is needed in serious applications.

(a) Let P(n) be the statement:

1+2+3++n=n(n+1)2”.

  • LHS of P(1)=1; RHS of P(1)=1·(1+1)2=1. Since these two are equal, P(1) is true.
  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    1+2+3++k=k(k+1)2 ”.

    We wish to prove that P(k+1) must then be true.

    Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1)):

    LHS of P ( k + 1 ) = 1 + 2 + 3 + + k + ( k + 1 ) = ( 1 + 2 + 3 + + k ) + ( k + 1 ) .

    If we now use P(k), which we are supposing to be true, then the first bracket is equal to k(k+1)2, so the complete sum is equal to:

    = k ( k + 1 ) 2 + ( k + 1 ) = ( k + 1 ) ( k + 2 ) 2 = RHS of P ( k + 1 ) .

    Hence P(k+1) holds.

    If we combine these two bullet points, then we have proved that “P(n) holds for all n1”.

(b) Let P(n) be the statement:

11·2+12·3+13·4++1n·(n+1)=11n+1”.

  • LHS of P(1)=11·2=12; RHS of P(1)=112=12. Since these two are equal, P(1) is true.
  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    11·2+12·3+13·4++1k·(k+1)=11k+1”.

    We wish to prove that P(k+1) must then be true.

    Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1):

    LHS of P ( k + 1 ) = 1 1 2 + 1 2 3 + 1 3 4 + + 1 ( k + 1 ) ( k + 2 ) = [ 1 1 2 + 1 2 3 + 1 3 4 + 1 k ( k + 1 ) ] + 1 ( k + 1 ) ( k + 2 ) .

    If we now use P(k), which we assume is true, then the first bracket is equal to 11k+1, so the complete sum is equal to:

    = [ 1 - 1 k + 1 ] + 1 ( k + 1 ) ( k + 2 ) = 1 - [ 1 k + 1 - 1 ( k + 1 ) ( k + 2 ) ] = 1 - 1 k + 2 = RHS of P ( k + 1 ) .

    Hence P(k+1) holds.

    If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

(c) Note: If q=1, then the LHS is equal to n, but the RHS makes no sense. So we assume q1.

Let P(n) be the statement:

1+q+q2+q3++qn1=11qqn1q ”.

  • LHS of P(1)=1; RHS of P(1)=11qq1q=1. Since these two are equal, P(1) is true.
  • Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

    1+q+q2+q3++qk1=11qqk1q”.

    We wish to prove that P(k+1) must then be true.

Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1):

LHS of P ( k + 1 ) = 1 + q + q 2 + q 3 + + q k = ( 1 + q + q 2 + q 3 + + q k - 1 ) + q k .

If we now use P(k), which we assume is true, then the first bracket is equal to

11qqk1q

so the complete sum is equal to:

= 1 1 - q - [ q k 1 - q - q k ] = 1 1 - q - q k + 1 1 - q = RHS of P ( k + 1 ) .

Hence P(k+1) holds.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

(d) Note: The statement to be proved starts with a term involving “0!”. The definition

n!=1×2×3××n

does not immediately tell us how to interpret “0!”. The correct interpretation emerges from the fact that several different thoughts all point in the same direction.

(i) When n>0, then to get from n! to (n+1)! we multiply by (n + 1). If we extend this to n=0, then “to get from 0! to 1!, we have to multiply by 1” – which suggests that 0!=1.

(ii) When n>0, n! counts the number of permutations of n symbols, or the number of different linear orders of n objects (i.e. how many different ways they can be arranged in a line). If we extend this to n=0, we see that there is just one way to arrange 0 objects (namely, sit tight and do nothing).

(iii) The definition of n! as a product suggests that 0! involves a “product with no terms” at all. Now when we “add no terms together” it makes sense to interpret the result as “= 0” (perhaps because if this “sum of no terms” were added to some other sum, it would make no difference). In the same spirit, the product of no terms should be taken to be “= 1” (since if this empty product were included at the end of some other product, it would make no difference to the result).

Let P(n) be the statement:

0·0!+1·1!+2·2!++(n1)·(n1)!=n!1”.

• LHS of P(1)=0·0!=0; RHS of P(1)=1!1=0. Since these two are equal, P(1) is true.

• Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

0·0!+1·1!+2·2!++(k1)·(k1)!=k!1”.

We wish to prove that P(k+1) must then be true.

Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1)):

LHS of P ( k + 1 ) = 0 0 ! + 1 1 ! + 2 2 ! + + k k ! = [ 0 0 ! + 1 1 ! + 2 2 ! + + ( k - 1 ) ( k - 1 ) ! ] + k . k ! .

If we now use P(k), which we assume is true, then the first bracket is equal to k!1, so the complete sum is equal to:

= ( k ! - 1 ) + k k ! = ( k + 1 ) k ! - 1 = ( k + 1 ) ! - 1 = RHS of P ( k + 1 ) .

Hence P(k+1) holds.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

(e) Let P(n) be the statement:

(cosθ+isinθ)n=cosnθ+isinnθ

• LHS of P(1)=(cosθ+isinθ)1; RHS of P(1)=cosθ+isinθ. Since these two are equal, P(1) is true.

• Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

(cosθ+isinθ) k =coskθ+isinkθ ”.

We wish to prove that P(k+1) must then be true.

Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1):

LHS of P ( k + 1 ) = ( cos θ + i sin θ ) k + 1 = ( cos θ + i sin θ ) k ( cos θ + i sin θ ) .

If we now use P(k), which we assume is true, then the first bracket is equal to (coskθ+isinkθ), so the complete expression is equal to:

= ( cos k θ + i sin k θ ) ( cos θ + i sin θ ) = [ cos k θ cos θ - sin k θ sin θ ] + i [ cos k θ sin θ + sin k θ cos θ ] = cos ( k + 1 ) θ + i sin ( k + 1 ) θ = RHS of P ( k + 1 ) .

Hence P(k+1) holds.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

236. Let P(n) be the statement:

(1+2+3++n) 2 = 1 3 + 2 3 + 3 3 ++ n 3 ”.

• LHS of P(1)=12; RHS of P(1)=13. Since these two are equal, P(1) is true.

• Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

(1+2+3++k) 2 = 1 3 + 2 3 + 3 3 ++ k 3 ”.

We wish to prove that P(k+1) must then be true.

Now P(k+1) is an equation, so we start with one side of P(k+1) and try to simplify it in an appropriate way to get the other side of P(k+1). In this instance, the RHS of P(k+1) is the most promising starting point (because we know a formula for the kth triangular number, and so can see how to simplify it):

RHS of P ( k + 1 ) = 1 3 + 2 3 + 3 3 + + k 3 + ( k + 1 ) 3 = [ 1 3 + 2 3 + 3 3 + + k 3 ] + ( k + 1 ) 3 .

If we now use P(k), which we assume is true, then the first bracket is equal to

(1+2+3++k) 2 ,

so the complete RHS is:

= ( 1 + 2 + 3 + + k ) 2 + ( k + 1 ) 3 = [ k ( k + 1 ) 2 ] 2 + ( k + 1 ) 3 = 1 4 ( k + 1 ) 2 [ k 2 + 4 k + 4 ] = [ ( k + 1 ) ( k + 2 ) 2 ] 2 = ( 1 + 2 + 3 + + ( k + 1 ) ) 2 = LHS of P ( k + 1 ) .

Hence P(k+1) holds.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

Note: A slightly different way of organizing the proof can sometimes be useful. Denote the two sides of the equation in the statement P(n) by f(n) and g(n) respectively. Then

f(1)=12=13=g(1); and

• simple algebra allows one to check that, for each k1,

f(k+1)f(k)= (k+1) 3 =g(k+1)g(k).

It then follows (by induction) that f(n)=g(n) for all n1.

237.

(a) T1=1, T1+T2=1+3=4, T1+T2+T3=1+3+6=10. These may not be very suggestive. But

T1+T2+T3+T4=20=5×4, T1+T2+T3+T4+T5=35=5×7,

and

T1+T2+T3+T4+T5+T6=56=7×8

may eventually lead one to guess that

T1+T2+T3++Tn=n(n+1)(n+2)6.

Note 1: This will certainly be easier to guess if you remember what you found in Problem 17. and Problem 63.

Note 2: There is another way to help in such guessing. Suppose you notice that

– adding values for k=1 up to k=n of a polynomial of degree 0 (such as p(x)=1) gives an answer that is a “polynomial of degree 1”,

1+1++1=n,

and

– adding values for k=1 up to k=n of a polynomial of degree 1 (such as p(x)=x) gives an answer that is a “polynomial of degree 2”,

1+2+3++n=n(n+1)2.

Then you might guess that the sum

T1+T2+T3++Tn

will give an answer that is a polynomial of degree 3 in n. Suppose that

T1+T2+T3++Tn=An3+Bn2+Cn+D.

We can then use small values of n to set up equations which must be satisfied by A, B, C, D and solve them to find A, B, C, D:

– when n=0, we get D=0;

– when n=1, we get A+B+C=1;

– when n=2, we get 8A+4B+2C=4;

– when n=3, we get 27A+9B+3C=10.

This method assumes that we know that the answer is a polynomial and that we know its degree: it is called “the method of undetermined coefficients”.

There are various ways of improving the basic method (such as writing the polynomial An3+Bn2+Cn+D in the form

Pn(n1)(n2)+Qn(n1)+Rn+S,

which tailors it to the values n=0,1,2,3 that one intends to substitute).

(b) Let P(n) be the statement:

T1+T2+T3++Tn=n(n+1)(n+2)6”.

• LHS of P(1)=T1=1; RHS of P(1)=1×2×36=1. Since these two are equal, P(1) is true.

• Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k,

T1+T2+T3++Tk=k(k+1)(k+2)6.

We wish to prove that P(k+1) must then be true.

Now P(k+1) is an equation, so we start with the LHS of P(k+1) and try to simplify it in an appropriate way to get the RHS of P(k+1):

LHS of P ( k + 1 ) = T 1 + T 2 + T 3 + + T k + T k + 1 = [ T 1 + T 2 + T 3 + + T k ] + T k + 1 .

If we now use P(k), which we assume is true, then the first bracket is equal to

k(k+1)(k+2)6.

so the complete sum is equal to:

= k ( k + 1 ) ( k + 2 ) 6 + ( k + 1 ) ( k + 2 ) 2 = ( k + 1 ) ( k + 2 ) ( k + 3 ) 6 = RHS of P ( k + 1 ) .

Hence P(k+1) holds.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

Note: The triangular numbers T1,T2,T3,,Tk,Tn are also equal to the binomial coefficients k+1choose2. And the sum of these binomial coefficients is another binomial coefficient n+2choose3, so the result in Problem 237. can be written as:

(22)+(32)+(42)++(n+12)=(n+23).

You might like to interpret Problem 237. in the language of binomial coefficients, and prove it by repeated use of the basic Pascal triangle relation (Pascal (1623--1662)):

(kr)+(kr+1)=(k+1r+1).

Start by rewriting

(n+23)=(n+12)+(n+13).

238.

(a) We know from Problem 237.(b) that

12+23+34++n(n+1)=n(n+1)(n+2)3.

Also

1 2 + 2 3 + 3 4 + + n ( n + 1 ) = 1 ( 1 + 1 ) + 2 ( 2 + 1 ) + 3 ( 3 + 1 ) + + n ( n + 1 ) = ( 1 2 + 1 ) + ( 2 2 + 2 ) + ( 3 2 + 3 ) + + ( n 2 + n ) = ( 1 2 + 2 2 + 3 2 + + n 2 ) + ( 1 + 2 + 3 + + n ) .

Therefore

1 2 + 2 2 + 3 2 + + n 2 = n ( n + 1 ) ( n + 2 ) 3 - n ( n + 1 ) 2 = n ( n + 1 ) ( 2 n + 1 ) 6 .

(b) Guess:

123+234+345++n(n+1)(n+2)=n(n+1)(n+2)(n+3)4.

The proof by induction is entirely routine, and is left for the reader.

1 2 3 + 2 3 4 + + n ( n + 1 ) ( n + 2 ) = 1 ( 1 + 1 ) ( 1 + 2 ) + 2 ( 2 + 1 ) ( 2 + 2 ) + + n ( n + 1 ) ( n + 2 ) = ( 1 3 + 3 1 2 + 2 1 ) + ( 2 3 + 3 2 2 + 2 2 ) + + ( n 3 + 3 n 2 + 2 n ) = ( 1 3 + 2 3 + + n 3 ) + 3 ( 1 2 + 2 2 + + n 2 ) + 2 ( 1 + 2 + + n ) .

Therefore

1 3 + 2 3 + 3 3 + + n 3 = n ( n + 1 ) ( n + 2 ) ( n + 3 ) 4 - 3 [ n ( n + 1 ) ( 2 n + 1 ) 6 ] - n ( n + 1 ) = [ n ( n + 1 ) 2 ] 2 .

239.

(a) Let f(x) be any such polynomial. If f(ak)=0, then we know (by the Remainder Theorem) that f(x) has (xak) as a factor. Since the ak are all distinct, and f(ak)=0 for each k, 0kn1, we have

f(x)=(xa0)(xa1)(xa2)(xan1)g(x)

for some polynomial g(x). And since we are told that f(x) has degree n, g(x) has degree 0, so is a constant. Hence every such polynomial of degree n has the form

C(xa0)(xa1)(xa2)(xan1).

Since f(an)=b, we can substitute to find C:

C=b(ana0)(ana1)(ana2)(anan1).

(b) Let P(n) be the statement:

“Given any two labelled sets of n+1 real numbers a0,a1,a2,,an, and b0,b1,b2,,bn, where the ai are all distinct (but the bi need not be), there exists a polynomial fn of degree n, such that fn(a0)=b0, fn(a1)=b1, fn(a2)=b2, …, fn(an)=bn.”

• When n=0, we may choose f0(x)=b0 to be the constant polynomial. Hence P(0) is true.

• Suppose that P(k) is true for some particular (unspecified) k0; that is, we know that, for this particular k:

“Given any two labelled sets of k+1 real numbers a0,a1,a2,,ak, and b0,b1,b2,,bk, where the ai are all distinct (but the bi need not be), there exists a polynomial fk of degree k, such that fk(a0)=b0, fk(a1)=b1, fk(a2)=b2,,fk(ak)=bk.”

We wish to prove that P(k+1) must then be true.

Now P(k+1) is the statement:

“Given any two labelled sets of (k+1)+1 real numbers a0,a1,,ak+1, and b0,b1,b2,,bk+1, where the ai are all distinct (but the bi need not be), there exists a polynomial fk+1 of degree k+1, such that fk+1(a0)=b0, fk+1(a1)=b1, fk+1(a2)=b2, …, fk+1(ak+1)=bk+1.”

So to prove that P(k+1) holds, we must start by considering

any two labelled sets of (k+1)+1 real numbers a0,a1,a2,,ak+1, and b0,b1,b2,,bk+1, where the ai are all distinct (but the bi need not be).

We must then somehow construct a polynomial function fk+1 of degree k+1 with the required property.

Because we are supposing that P(k) is known to be true, we can focus on the first k+1 numbers in each of the two lists – a0,a1,a2,,ak, and b0,b1,b2,,bk – and we can then be sure that there is a polynomial fk of degree k such that

fk(a0)=b0,fk(a1)=b1,fk(a2)=b2,,fk(ak)=bk.

The next step is slightly indirect: we make use of the polynomial fk+1 which we are still trying to construct, and focus on the polynomial

f(x)=fk+1(x)fk(x)

satisfying

f(a0)=f(a1)==f(ak)=0,f(ak+1)=bk+1fk(ak+1)=b(say).

Part (a) guarantees the existence of such a polynomial f(x) of degree k+1 and tells us exactly what this polynomial function f(x) is equal to. Hence we can construct the required polynomial fk+1(x)) by setting it equal to f(x)+fk(x), which proves that P(k+1) is true.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”.

240.

(a) 5 cents cannot be made; 6=3+3; 7=3+4; 8=4+4; 9=3+3+3; etc.

Guess: Every amount > N = 5 can be paid directly (without receiving change).

(b) Let P(n) be the statement:

n cents can be paid directly (without change) using 3 cent and 4 cent coins”.

P(6) is the statement: “6 cents can be paid directly”. And 6=3+3, so P(6) is true.

– Now suppose that we know P(k) is true for some k6. We must show that P(k+1) must then be true.

To prove P(k+1) we consider the statement P(k+1):

k+1 cents can be paid directly”.

We know that P(k) is true, so we know that “k cents can be paid directly”.

– If a direct method of paying k cents involves at least one 3 cent coin, then we can replace one 3 cent coin by a 4 cent coin to produce a way of paying k+1 cents.

Hence we only need to worry about a situation in which the only way to pay k cents directly involves no 3 cent coins at all – that is, paying k cents uses only 4 cent coins. But then there must be at least two 4 cent coins (since k6), and we can replace two 4 cent coins by three 3 cent coins to produce a way of paying k+1 cents directly.

Hence

P(6) is true; and

• whenever P(k) is true for some k6, we know that P(k+1) is also true.

P(n) is true for all n6.

241.

(a) z2z+1=0, so z=1±32 (these are the two primitive sixth roots of unity).

z2=1±32 (the two primitive cube toots of unity), and

z2+1z2=1.

(b) z22z+1=0, so z=1 (repeated root). z2=1 and z2+1z2=2.

(c) (d) z23z+1=0, so z=3±52.

As soon as one starts calculating z2 and 1z2, it becomes clear that it is time to p-a-u-s-e and think.

(z+1z)2=(z2+1z2)+2,

so whenever z+1z=k is an integer,

z2+(1z)2=k22

is also an integer.

(e) Let P(n) be the statement:

“if z has the property that z+1z is an integer, then zm+1zm is also an integer for all m, 0mn”.

P(0) and P(1) are clearly both true; and P(2) was proved in part (d) above.

• Suppose that P(k) is true for some particular (unspecified) k2; that is, we know that, for this particular k:

“if z has the property that z+1z is an integer, then zm+1zm is also an integer for all m, 0mk”.

We wish to prove that P(k+1) must then be true.

If z+1z is an integer, then, by P(k),

zm+1zm is also an integer for all m, 0mk”.

So to prove that P(k+1) holds, we only need to show that

zk+1+1zk+1 is an integer”.

By the Binomial Theorem:

( z + 1 z ) k + 1 = ( z k + 1 + 1 z k + 1 ) + ( k + 1 1 ) ( z k - 1 + 1 z k - 1 ) + ( k + 1 2 ) ( z k - 3 + 1 z k - 3 ) +

The LHS is an integer (since z+1z is an integer), and (by P(k)) every term on the RHS is an integer except possibly the first. Hence the first term is the difference of two integers, so must also be an integer.

Hence P(k+1) is true.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”. QED

Note: If k+1=2m is even, the expansion of (z+1z)k+1 has an odd number of terms, so the RHS of the above re-grouped expansion ends with the term (2mm)·zm·(1z)m, which is also an integer.

242.

Note: In the solution to Problem 241. we included the condition on z as part of the statement P(n).

In Problem 242. the result to be proved has a similar background hypothesis – “Let p be a prime number”. It may make the induction clearer if, as in the statement of the Problem, this hypothesis is stated before starting the induction proof.

Let p be any prime number. We let P(n) be the statement:

npn is divisible by p ”.

P(1) is true (since 1p1=0=0×p, which is divisible by p).

• Suppose that P(k) is true for some particular (unspecified) k1; that is, we know that, for this particular k:

kpk is divisible by p”.

We wish to prove P(k+1) – that is,

(k+1) p (k+1) is divisible by p

must then be true. Using the Binomial Theorem again we see that

(k+1) p (k+1) = [ k p +( p p1 ) k p1 +( p p2 ) k p2 ++( p 1 )k+1 ] (k+1) = ( k p k)+[ ( p p1 ) k p1 +( p p2 ) k p2 ++( p 1 )k ].

By P(k), the first bracket on the RHS is divisible by p; and in each of the other terms each of the binomial coefficients ( p r ) , 0<r<p,

• is an integer, and

• has a factor “p” in the numerator and no such factor in the denominator.

Hence each term in the second bracket is a multiple of p. So the RHS (and hence the LHS) is divisible by p.

Hence P(k+1) is true.

If we combine these two bullet points, we have proved that “P(n) holds for all n1”. QED

243.

0.037037037 (for ever) =371000+371000000+371000000000+ (for ever).

This is a geometric series with first term a=371000 and common ratio r=11000, and so has sum

a1r=37999=127.

244.

(a) Each person receives in total:

14+(14)2+(14)3+(14)4+ (for ever) =13

(here a=14=r).

(b) You have

112+1418+ (for ever) =23

(here a=1, r=12); I have

1214+18 (for ever) =13

(here a=12, r=12).

245. The trains are 120 km apart, and the fly travels at 50 km/h towards Train B, which is initially 120 km away and travelling at 30 km/h.

The relative speed of the fly and Train B is 80 km/h, so it takes 32 hours before they meet. In this time Train A and Train B have each travelled 45 km, so they are now 30 km apart. The fly then turns right round and flies back to Train A.

The relative speed of the fly and Train A is then also 80 km/h, so it takes just 38 hours (or 22.5 minutes) for the fly to return to Train A. Train A and Train B have each travelled 454 km in this time, so they are now 304 km apart. The fly then turns round and flies straight back to Train B.

Train B is 304 km away and the relative speed of the fly and Train B is again 80 km/h, so the journey takes 332 hours (or 5.625 minutes).

Continuing in this way, we see that the fly takes

32+38+332+3128+ (for ever) =2 hours. Hence the fly travels 100 km before being squashed.

Note: The two trains are approaching each other at 60 km/h, so they crash in exactly 2 hours – during which time the fly travels 100 km.

246.

(a) (i) 32>22; therefore

132<122,

so

122+132<222=12.

(ii) 72>62>52>42; therefore

172<162<152<142,

so

142+152+162+172<442=14.

(b) The argument in part (a) gives an upper bound for each bracketed expression in the sum

(112)+(122+132)+(142+152+162+172)+(182++1152)+

Replacing each bracket by its upper bound, we see that the sum is

< 1 1 2 + 2 2 2 + 4 4 2 + 8 8 2 + = 1 + 1 2 + 1 4 + 1 8 + (for ever) = 2.

(c) The finite partial sums

Sn=112+122+132++1n2

increase steadily as we take more and more terms, and

• every partial sum Sn is less than 2. It is clear that these partial sums form a sequence

1=S1<S2<S3<<Sn<Sn+1<<2.

It follows that there is some (unknown) number S2 to which the partial sums converge as n, and we take this (unknown) exact value S to be the exact value of the endless sum

112+122+132++1n2+ (for ever)

To see, for example, that S>1712, notice that

S > S 4 = 1 1 2 + 1 2 2 + 1 3 2 + 1 4 2 = 1 + 1 4 + 1 9 + 1 16 > 17 12 .

Note 1: The claim that

“an increasing sequence of partial sums Sn, all less than 2, must converge to some number S2

is a fundamental property of the real numbers – called completeness.

Note 2: Just as one can obtain better and better lower bounds for S – like “1712<S”, so one can improve the upper bound “S<2”. For example, if in part (b) we avoid replacing the third term 19 by 14, we get a better upper bound “S<6736”, which is 536 less than 2.

247.

(a) Let P(n) be the statement:

112+122+132++1n221n”.

• Then LHS of P(1)=112=1, and RHS of P(1)=21=1. Hence P(1) is true.

• Suppose we know that P(k) is true for some k1. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 1 2 + 1 2 2 + 1 3 2 + + 1 k 2 + 1 ( k + 1 ) 2 = [ 1 1 2 + 1 2 2 + 1 3 2 + + 1 k 2 ] + 1 ( k + 1 ) 2 [ 2 - 1 k ] + 1 ( k + 1 ) 2 = 2 - [ 1 k - 1 ( k + 1 ) 2 ] < 2 - 1 k + 1 .

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1. QED

(b) Let P(n) be the statement:

112+122+132++1n2<1.681n”.

• Then

LHS of P(4)=112+122+132+142=1.423611111,

and RHS of P(4)=1.43. Hence P(4) is true.

• Suppose we know that P(k) is true for some k4. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 1 2 + 1 2 2 + 1 3 2 + + 1 k 2 + 1 ( k + 1 ) 2 = ( 1 1 2 + 1 2 2 + 1 3 2 + + 1 k 2 ) + 1 ( k + 1 ) 2 < [ 1.68 - 1 k ] + 1 ( k + 1 ) 2 = 1.68 - [ 1 k - 1 ( k + 1 ) 2 ] < 1.68 - 1 k + 1 .

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1.

248.

(a) (i) n!=n×(n1)×(n2)××3×2×12×2×2××2×1=2n1 whenever n1.

1n!12n1 for all n1.

10!+11!+12!++1n!1+1+12+122++12n1<3 for all n0.

(ii) As we go on adding more and more terms, each finite sum

10!+11!+12!++1n!

is bigger than the previous sum. Since every finite sum

10!+11!+12!++1n!<3,

the sums increase, but never reach 3, so they accumulate closer and closer to a value “e3. Moreover, this value “e” is certainly larger than the sum of the first two terms 10!+11!=2, so 2<e3.

(b) (i) Let P(n) be the statement:

10!+11!+12!++1n!31nn!”.

LHS of P(1)=2=RHS of P(1). Hence P(1) is true.

• Suppose we know that P(k) is true for some k1. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 0 ! + 1 1 ! + 1 2 ! + + 1 ( k + 1 ) ! = [ 1 0 ! + 1 1 ! + 1 2 ! + + 1 k ! ] + 1 ( k + 1 ) ! 3 - 1 k k ! + 1 ( k + 1 ) ! = 3 - 1 k ( k + 1 ) ! < 3 - 1 ( k + 1 ) ( k + 1 ) !

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1.

(ii) [The reasoning here uses the constant “3” while ignoring the refinement “31n.n!”, and so sounds exactly like part (a)(ii).] As we add more terms, each finite sum

10!+11!+12!++1n!

is bigger than the previous sum. Since every finite sum

10!+11!+12!++1n!<3,

the partial sums increase, but never reach 3; so they accumulate closer and closer to a value “e3. Moreover, this value “e” is certainly larger than the sum of the first three terms 10!+11!+12!=2.5, so 2.5<e3.

(c) Note: Examine carefully the role played by the number “3” in the above induction proof in (b)(ii). It is needed precisely to validate the statement P(1): since 10!+11!=311×1!”. But the number “3” plays no active part in the second induction step, and could be replaced by any other number we choose.

The exact value “e” of the infinite series is not really affected by what happens when n=1. Suppose we ask: “What number C2 should replace “3” if we only want to prove that

10!+11!+12!++1n!C21nn!, for all n2?

The only part of the induction proof where C2 then matters is when we try to check that P(2) holds; so we must choose the smallest possible C2 to satisfy

10!+11!+12!C212.2!:

that is, C2=2.75.

(i) Let P(n) be the statement:

10!+11!+12!++1n!2.751nn!”.

• LHS of P(2)=2.5; RHS of P(2)=2.7514. Hence P(2) is true.

• Suppose we know that P(k) is true for some k2. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 0 ! + 1 1 ! + 1 2 ! + + 1 ( k + 1 ) ! = [ 1 0 ! + 1 1 ! + 1 2 ! + + 1 k ! ] + 1 ( k + 1 ) ! 2.75 - 1 k k ! + 1 ( k + 1 ) ! = 2.75 - 1 k ( k + 1 ) ! < 2.75 - 1 ( k + 1 ) ( k + 1 ) !

Hence P(k+1) holds.

P(2) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n2. QED

(ii) As we add more terms, each finite sum

10!+11!+12!++1n!

is bigger than the previous sum.

Since every finite sum

10!+11!+12!++1n!<2.75,

the finite sums increase, but never reach 2.75, so they accumulate closer and closer to a value “e2.75. Moreover, this value “e” is certainly larger than the sum of the first four terms

10!+11!+12!+13!>2.66,

so 2.66<e2.75.

(d) (i) Let P(n) be the statement:

10!+11!+12!++1n!2.7222(for ever)1n.n!”.

LHS of P(3)=10!+11!+12!+13!=2.666(for ever); RHS of P(3)=2.7222(for ever) 118=2.666(for ever). Hence P(3) is true.

• Suppose we know that P(k) is true for some k3. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 0 ! + 1 1 ! + 1 2 ! + + 1 ( k + 1 ) ! = [ 1 0 ! + 1 1 ! + 1 2 ! + + 1 k ! ] + 1 ( k + 1 ) ! 2.7222 ( for ever ) - 1 k k ! + 1 ( k + 1 ) ! = 2.7222 ( for ever ) - 1 k ( k + 1 ) ! < 2.7222 ( for ever ) - 1 ( k + 1 ) ( k + 1 ) !

Hence P(k+1) holds.

P(3) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n3.

(ii) As we add more terms, each finite sum

10!+11!+12!++1n!

is bigger than the previous sum.

Since every finite sum

10!+11!+12!++1n!<2.7222 (for ever),

the finite sums increase, but never reach 2.7222 (for ever), so they accumulate closer and closer to a value “e2.7222 (for ever). Moreover, this value “e” is certainly larger than the sum of the first five terms

10!+11!+12!+13!+14!>2.708,

so 2.708<e2.7222 (for ever).

Note: This process of refinement can continue indefinitely. But we only have to go one further step to pin down the value of “e” with surprising accuracy.

The next step uses the same proof to show that

10!+11!+12!++1n!2.71851nn!, for all n4”,

and to conclude that the endless sum

10!+11!+12!++1n!+(for ever)

has a definite value “e” that lies somewhere between 2.716 and 2.71875.

We could then repeat the same proof to show that

10!+11!+12!++1n!2.718333(for ever)1nn!, for all n5,

and use the lower bound 2.7177 from the first seven terms to conclude that the endless sum

10!+11!+12!++1n!+ (for ever)

has a definite value “e” that lies somewhere between 2.7177 and 2.718333 (for ever). And so on.

249. Let P(n) be the statement:

11+12+13++1nn”.

• LHS of P(1)=1= RHS of P(1). Hence P(1) is true.

• Suppose we know that P(k) is true for some k1. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = 1 1 + 1 2 + 1 3 + + 1 k + 1 = ( 1 1 + 1 2 + 1 3 + + 1 k ) + 1 ( k + 1 ) k + 1 k + 1 k + 1 ( since 1 k + 1 1 k + 1 + k ) .

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1. QED

250. Let a, b be real numbers such that ab, and a+b>0.

One of a, b is then the greater, and we may suppose this is a – so that a>b. If a>b>0, then an>bn>0 for all n; if b<0, then a+b>0 implies that a=|a|>|b|, so an>bn for all n.

Let P(n) be the statement:

an+bn2a+b2n”.

• LHS of P(1)=a+b2=RHS of P(1). Hence P(1) is true.

• Suppose we know that P(k) is true for some k1. We want to prove that P(k+1) holds.

RHS of P ( k + 1 ) = ( a + b 2 ) k + 1 = a + b 2 ( a + b 2 ) k a + b 2 a k + b k 2 ( by P ( k ) ) = a k + 1 + b k + 1 4 + a b k + b a k 4 < a k + 1 + b k + 1 2 ( since ( a k - b k ) ( a - b ) > 0 ) .

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1.

251. Let x be any real number 1.

If x=1, then (1+x) n =01n=1+nx , for all n1.

Thus we may assume that x>1, so 1+x>0.

Let P(n) be the statement: “ (1+x) n 1+nx ”.

• LHS of P(1)=1+x=RHS of P(1). Hence P(1) is true.

• Suppose we know that P(k) is true for some k1. We want to prove that P(k+1) holds.

LHS of P ( k + 1 ) = ( 1 + x ) k + 1 = ( 1 + x ) ( 1 + x ) k ( 1 + x ) ( 1 + k x ) ( by P ( k ) , since 1 + x > 0 ) = 1 + ( k + 1 ) x + k x 2 1 + ( k + 1 ) x

Hence P(k+1) holds.

P(1) holds; and whenever P(k) is known to be true, P(k+1) is also true.

P(n) is true, for all n1.

252. The problem is discussed after the statement of Problem 252. in the main text.

253.

(a) (i) 3>2, so 13<12. 12+13<12+12=1.

(ii) 5,6,7>4; hence 15,16,17 are all <14. 14+15+16+17<14+14+14+14=1.

(iii) Let P(n) be the statement:

11+12+13++12n1<n ”.

Then

P(2) is true by (i), since

11+12+13<1+(12+12)=2.

• Suppose that P(k) is true for some k2.

LHS of P(k+1) = [ 1 1 + 1 2 + 1 3 ++ 1 2 k 1 ] +[ 1 2 k ++ 1 2 k+1 1 ].

The first bracket is <k (by P(k)); and each of the 2k terms in the second bracket is 12k, so the whole bracket is 1.

Hence the LHS of P(k+1)<k+1, so P(k+1) is true.

Hence P(n) is true for all n2.

(iv) At the very first stage (part (i)) we replaced 12+13 by 12+12=1. Hence when n2, we know that the two sides of P(n) differ by at least 1213. This difference is greater than 12n when n3, so (iv) follows.

(b)

(i) 3<4, so 13>14.

13+14>14+14=12.

(ii) 5,6,7<8; hence 15,16,17 are all >18.

15+16+17+18>18+18+18+18=12.

(iii) Let P(n) be the statement:

11+12+13++12n>1+n2”.

Then

P(2) is true by (i), since

1 1 + 1 2 + 1 3 + 1 4 = 1 + 1 2 + ( 1 3 + 1 4 ) > 1 + 1 2 + ( 1 4 + 1 4 ) = 1 + 2 × 1 2 .

• Suppose that P(k) is true for some k2.

LHS of P(k+1)=11+12+13++12k+12k+1++12k+1.

The first bracket is >1+k2 (by P(k)); and each of the 2k terms in the second bracket is 12k+1, so the whole bracket is 12. Hence the LHS of P(k+1)>1+k+12, so P(k+1) is true.

Hence P(n) is true for all n2.

254.

(a) We use induction. Let P(n) be the statement:

n identical rectangular strips of length 2 balance exactly on the edge of a table if the successive protrusion distances (first beyond the edge of the table, then beyond the leading edge of the strip immediately below, and so on) are the terms 1n,1n1,1n2,,13,12,11 of the finite harmonic series in reverse order.”

• When n=1, a single strip which protrudes distance 1 beyond the edge of the table has its centre of gravity exactly over the edge of the table. Hence P(1) is true.

• Suppose that we know that P(k) is true for some k1.

Let k+1 identical strips be arranged as described in the statement P(k+1).

The statement P(k) guarantees that the top k strips would exactly balance if the leading edge of the bottom strip were in fact the edge of the table; hence the combined centre of gravity of the top k strips is positioned exactly over the leading edge of the bottom strip.

Let M be the mass of each strip; since the leading edge of the bottom strip is distance 1k+1 beyond the edge of the table, the top k strips produce a combined moment about the edge of the table equal to kM×1k+1.

The centre of gravity of the bottom strip is distance 11k+1=kk+1 from the edge of the table in the opposite direction; hence it contributes a moment about the edge of the table equal to M×kk+1.

the total moment of the whole stack about the edge of the table is equal to zero, so the centre of gravity of the combined stack of k+1 strips lies exactly over the edge of the table. Hence P(k+1) is true.

Hence P(n) is true for all n1.

(b) Problem 253.(b)(iii) now guarantees that a stack of 2n strips can protrude a distance >1+n2 beyond the edge of the table.

Note: Ivars Petersen's Mathematical Tourist blog contains an entry in 2009

http://mathtourist.blogspot.com/2009/01/overhang.html

which explores how one can obtain large overhangs with fewer strips if one is allowed to use strips to counterbalance those that protrude beyond the edge of the table.

255.

(a) (i) Let P(n) be the statement:

s2p2<s2p<s2q+1<s2q1 for all p,q such that 1p,qn”.

P(1) is true (since s0 is the empty sum, so

0=s0<s2=12<s3=56<s1=1.

• Suppose that P(k) is true for some k1. Then most of the inequalities in the statement P(k+1) are part of the statement P(k); the only outstanding inequalities which remain to be proved are:

s2k<s2k+2<s2k+3<s2k+1.

which are true, since

s2k+3=s2k+2+12k+3=s2k+112k+2+12k+3

and

s2k+2=s2k+12k+112k+2.

Hence P(k+1) is true.

Hence P(n) is true for all n2.

(ii) The “even sums” s0,s2,s4, are increasing, but all are less than s1=1, so they approach some value seven1.

The “odd sums” s1,s3,s5, are decreasing, but all are greater than s2=12, so they approach some value sodd12.

The “even sums” s0,s2,s4, are increasing, but all are less than s5=4760, so they approach some value seven4760.

The “odd sums” s1,s3,s5, are decreasing, but all are greater than s6=3760, so they approach some value sodd3760.

Moreover, the difference between successive sums is 1n, and this tends towards zero, so the difference between each “odd sum” and the next “even sum” tends to zero, so seven=sodd.

(b) The proof from part (a) carries over word for word, with “1k” replaced at each stage by “ak”.

256. Let P(n) be the statement:

fk has at least k distinct prime factors”.

f1=2 has exactly 1 prime factor, so P(1) is true.

• Suppose that P(k) is true for some k1.

Then fk+1=fk(fk+1). The first factor fk has at least k distinct prime factors.

And the second factor fk+1>fk>1, so has at least one prime factor.

Moreover HCF(fk,fk+1)=1, so the second bracket has no factor in common with fk.

Hence fk+1 has at least k+1 distinct prime factors, so P(k+1) is true.

Hence P(n) is true for all n1.

Note: This problem [suggested by Serkan Dogan] gives a different proof of the result (Problem 76.(d)) that the list of prime numbers goes on for ever.

257.

(a) Let P(n) be the statement: “n distinct points on a straight line divide the line into n+1 intervals”.

• 0 points leave the line in pristine condition – namely a single interval – so P(0) is true.

• Suppose that P(k) is true for some k0.

Consider an arbitrary straight line divided by k+1 points A0,A1,,Ak.

Then the k points A1,,Ak divide the line into k+1 intervals (by P(k)).

The additional point A0 is distinct from A1, …, Ak and so must lie inside one of these k+1 intervals, and divides it in two – giving (k+1)+1=k+2 intervals altogether.

Hence P(k+1) is true.

Hence P(n) is true for all n0.

(b) (i) We want a function R satisfying

R0=1,R1=2,R2=4,R3=7.

If we notice that in part (a) n+1=1+(n1), then we might guess that

Rn=1+(n1)+(n2).

(ii) Let P(n) be the statement:

n distinct straight lines in the plane divide the plane into at most f(n)=1+(n1)+(n2) regions”.

• 0 lines leave the plane in pristine condition – namely a single region – so P(0) is true, provided that

1+(01)+(02)=1.

• Suppose that P(k) is true for some k0.

Consider the plane divided by k+1 straight lines m0,m1,,mk.

Then the k lines m1,,mk divide the plane into at most

Rk=1+(k1)+(k2)

regions (by P(k)).

The additional line m0 is distinct from m1,,mk and so meets each of these lines in at most a single point – giving at most k points on the line m0. These points divide m0 into at most k+1 intervals, and each of these intervals corresponds to a cut-line, where the line m0 cuts one of the regions created by the lines m1,m2,,mk into two pieces – giving at most

R k + ( k + 1 ) = 1 + ( k 1 ) + ( k 2 ) + k + 1 = 1 + ( k + 1 1 ) + ( k + 1 2 ) = R k + 1

regions altogether.

Hence P(k+1) is true.

Hence P(n) is true for all n0.

(c) (i) We want a function S satisfying

S0=1,S1=2,S2=4,S3=8,S4=15,

After thinking about the differences between successive terms in part (b), we might guess that

Sn=(n0)+(n1)+(n2)+(n3).

(ii) Let P(n) be the statement:

n distinct planes in 3-space divide space into at most

S n = ( n 0 ) + ( n 1 ) + ( n 2 ) + ( n 3 )

regions”.

• 0 planes leave our 3D space in pristine condition – namely a single region – so P(0) is true – provided that

(00)+(01)+(02)+(03)=1.

• Suppose that P(k) is true for some k0.

Consider 3D divided by k+1 planes m0,m1,,mk.

Then the k planes m1,,mk divide 3D into at most

Sk=(k0)+(k1)+(k2)+(k3)

regions (by P(k)).

The additional plane m0 is distinct from m1,,mk and so meets each of these planes in (at most) a line – giving rise to at most k lines on the plane m0. This arrangement of lines on the plane m0 divides m0 into at most

Rk=1+(k1)+(k2)

regions, and each of these regions on the plane m0 is the “cut” where the plane m0 cuts an existing region into two pieces – giving rise to at most

S k + R k = [ ( k 0 ) + ( k 1 ) + ( k 2 ) + ( k 3 ) ] + [ 1 + ( k 1 ) + ( k 2 ) ] = ( k + 1 0 ) + ( k + 1 1 ) + ( k + 1 2 ) + ( k + 1 3 ) = S k + 1

regions altogether. (There is no need for any algebra here: one only needs to use the Pascal triangle condition.)

Hence P(k+1) is true whenever P(k) is true.

Hence P(n) is true for all n0.

258. Notice that, given a dissection of a square into k squares, we can always cut one square into four quarters (by lines through the centre, and parallel to the sides), and so create a dissection with k+3 squares.

Let P(n) be the statement:

“Any given square can be cut into m (not necessarily congruent) smaller squares, for each m, 6mn”.

• Let n=6. Given any square of side s (say). We may cut a square of side 2s3 from one corner, leaving an L-shaped strip of width s3, which we can then cut into 5 smaller squares, each of side s3. Hence P(6) is true.

Let n=7. Given any square, we can divide the square first into four quarters; then divide one of these smaller squares into four quarters to obtain a dissection into 7 smaller squares. Hence P(7) is true.

Let n=8. Given a square of side s (say). We may cut a square of side 3s4 from one corner, leaving an L-shaped strip of width s4, which we can then cut into 7 smaller squares, each of side s4. Hence P(8) is true.

• Suppose that P(k) is true for some k8.

Then k26, so any given square can be dissected into k2 smaller squares (by P(k)). Taking this dissection and dividing one of the smaller squares into four quarters gives a dissection of the initial square into k2+3 squares. Hence P(k+1) is true.

Hence P(n) is true for all n6.

259. Let P(n) be the statement:

“Any tree with n vertices has exactly n1 edges”.

• A tree with 1 vertex is simply a vertex with 0 edges (since any edge would have to be a loop, and would then create a cycle). Hence P(1) is true.

• Suppose that P(k) is true for some k1.

Consider an arbitrary tree T with k+1 vertices.

[Idea: We need to find some way of reducing T to a tree T with k vertices. This suggests “removing an end vertex”. So we must first prove that “any tree T has an end vertex”.]

Definition The number of edges incident with a given vertex v is called the valency of v.

Lemma Let S be a finite tree with s>1 vertices. Then S has a vertex of valency 1 – that is an “end vertex”.

Proof Choose any vertex v0. Then v0 must be connected to the rest of the tree, so v0 has valency at least 1.

If v0 is an “end vertex”, then stop; if not, then choose a vertex v1 which is adjacent to v0.

If v1 is an “end vertex”, then stop; if not, choose a vertex v2v0 which is adjacent to v1.

If v2 is an “end vertex”, then stop; if not, choose a vertex v3v1 which is adjacent to v2.

Continue in this way.

All of the vertices v0,v1,v2,v3, must be different (since any repeat vm=vn with m<n would define a cycle

vm,vm+1,vm+2,,vn1,vn=vm

in the tree S). Since we know that the tree is finite (having precisely s vertices), the process must terminate at some stage. The final vertex ve is then an “end vertex”, of valency 1.

If we apply the Lemma to our arbitrary tree T with k+1 vertices, we can choose an “end vertex” v and remove both it and the edge e incident with it to obtain a tree T having k vertices. By P(k) we know that T has exactly k1 edges, so when we reinstate the edge e, we see that T has exactly (k1)+1 edges, so P(k+1) is true.

Hence P(n) is true for all n1.

260.

Note: All the polyhedra described in this solution are “spherical” by virtue of having their vertices located on the unit sphere.

(a) (i) A regular tetrahedron.

(ii) A square based pyramid with its apex at the North pole.

(b) If a spherical polyhedron has V vertices, E edges, and F faces, then

VE+F=2.

Now each edge has exactly two end vertices, so 2E counts the exact number of ordered pairs (v, e), where e is an edge, and v is a vertex “incident with e”.

On the other hand, in a spherical polyhedron, each vertex v has valency at least 3; so each vertex v occurs in at least 3 pairs (v, e) of this kind. Hence 2E3V.

In the same way, each edge e lies on the boundary of exactly 2 faces, so 2E counts the exact number of ordered pairs (f, e), where e is an edge of the face f.

On the other hand, in a spherical polyhedron, each face f has at least 3 edges; so each face f occurs in at least 3 pairs (f, e) of this kind. Hence 2E3F.

If E=7, then 143V, and 143F; now V and F are integers, so V4 and F4. Hence V+F8. However V+F=E+2=9. This contradiction shows that no such polyhedron exists.

(c) We show by induction how to construct certain “spherical” polyhedra, with at most one non-triangular face. Let P(n) be the statement:

“There exists a spherical polyhedron with at most one non-triangular face, and with e edges for each e, 8en”.

• We know that there exists a such a spherical polyhedron with n=6 edges – namely the regular tetrahedron (with four faces, which are all equilateral triangles).

We know there is no such polyhedron with n=7 edges (by part (b)).

When n=8, there is no spherical polyhedron with n=8 edges and all faces triangular (since we would then have 16=2E=3F, as in part (b)). However, there exists a spherical polyhedron with n=8 edges and just one non-triangular face – namely the square based pyramid with its apex at the North pole.

When n=9, we can join three points on the equator to the North and South poles to produce a triangular bi-pyramid (the dual of a triangular prism), with all faces triangular, and with n=9 edges.

When n=10, there is no spherical polyhedron with n=10 edges and with all faces triangles (since we would then have to have 20=2E=3F, as in part (b)); but there exists a spherical polyhedron with n=10 edges and just one face which is not an equilateral triangle – namely the pentagonal based pyramid with its apex at the North pole.

This provides us with a starting point for the inductive construction. In particular P(8), P(9), and P(10) are all true.

• Suppose that P(k) is true for some k10. The only part of the statement P(k+1) that remains to be demonstrated is the existence of a suitable polyhedron with k+1 edges.

Since k10, we know that k28, so (by P(k)) there exists a polyhedron with all its vertices on the unit sphere, with at most one non-triangular face, and with e=k2 edges. Take this polyhedron and remove a triangular face ABC. Now add a new vertex X on the sphere, internal to the spherical triangle ABC, and add the edges XA, XB, XC and the three triangular faces XAB, XBC, XCA, to produce a spherical polyhedron with e=(k2)+3=k+1 edges, and with at most one non-triangular face. Hence P(k+1) is true.

Hence P(n) is true for all n8.

261. To prove a result that is given in the form of an “if and only if” statement, we have to prove two things: “if”, and “only if”.

We begin by proving the “only if” part:

“a map can be properly coloured with two colours only if every vertex has even valency”.

Let M be a map that can be properly coloured with two colours. Let v be any vertex of the map M.

The edges e1,e2,e3, incident with v form parts of the boundaries of the sequence of regions around the vertex v (with e1, e2 bordering one region; e2, e3 bordering the next; and so on). Since we are assuming that the regions of the map M can be “properly coloured” with two colours, the succession of regions around the vertex v can be properly coloured with just two colours. Hence the colours of the regions around the vertex v must alternate (say black-white-black- …). And since the map is finite, this sequence must return to the start – so the number of such regions at the vertex v (and hence the number of edges incident with v – that is, the valency of v) must be even.

We now prove the “if” part:

“a map can be properly coloured with two colours if every vertex has even valency”.

Suppose that we have a map M in which each vertex has even valency. We must prove that any such map M can be properly coloured using just two colours.

Let P(n) be the statement:

“any map with m edges, in which each vertex has even valency, can be properly coloured with two colours whenever m satisfies 1mn,”.

• If n=1, a map in which every vertex has even valency, and which has just one edge e, must consist of a single vertex v, with e as a loop from v to v (so v has valency 2, since the edge e is incident with v twice). This creates a map with two regions – the “island” inside the loop, and the “sea” outside; so we can colour the “island” black and the “sea” white. Hence P(1) is true.

• Suppose that P(k) is true for some k1.

Most of the contents of the statement P(k+1) are already guaranteed by P(k). To prove that P(k+1) is true, all that remains to be proved is that

any map with exactly k+1 edges, in which every vertex has even valency, can be properly coloured using just two colours.

Consider an arbitrary map M with k+1 edges, in which each vertex has even valency.

[Idea: We need to find some way of reducing the map M to a map M with k edges, in which every vertex still has even valency.]

Since k1, the map M has at least 2 edges. Choose any edge e of M, with (say) vertices u1, u2 as its endpoints, and with regions R, S on either side of e.

Suppose first that u1=u2, so the boundary of the region R (say) consists only of the edge e. Hence e is a loop, and S is the only region neighbouring R. The edge e contributes 2 to the valency of u1; so if we delete the edge e, we obtain a map M in which every vertex again has even valency, in which the regions R and S have been amalgamated into a region S. Since M has just k edges, M can be properly coloured with just two colours. If we now reinstate the edge e and the region R, we can give S the same colour as S (in the proper colouring of M) and give R the opposite colour to S to obtain a proper colouring of the map M with just two colours.

Hence we may assume that u1u2, so that e is not the complete boundary of R. We may then slowly shrink the edge e to a point – eventually fusing the old vertices u1, u2 together to form a new vertex u, where two new regions R, S meet. The result is then a new map M, in which all other vertices are unchanged (and so have even valency), and in which

valency(u)=(valency(u1)1)+(valency(u2)1)

which is also even.

Hence every vertex of the new map M has even valency. Moreover, M has at most k edges, so (by P(k)) we know that the map M can be properly coloured with just two colours. And in this colouring of M, there are an odd number of colour changes as one goes from R to S through the other regions that meet around the old vertex u1 of M, so S receives the opposite colour to R. The guaranteed proper two-colouring of M therefore extends back to give a proper two-colouring of the original map M. Hence P(k+1) is true.

Hence P(n) is true for all n1.

262. Let P(n) be the statement:

“The 2n sequences of length n consisting of 0s and 1s can be arranged in a cyclic list such that any two neighbouring sequences (including the last and the first) differ in exactly one coordinate position.”

• When n=2 , the required cycle is obvious:

00101101(00). So P(2) is true.

• The general construction is perhaps best illustrated by first showing how P(2) leads to P(3).

The above cycle for sequences of length 2 gives rise to two disjoint cycles for sequences of length 3:

– first by adding a third coordinate “0”:

000100110010(000)

– then by adding a third coordinate “1”:

001101111011(001).

Now eliminate the final join in each cycle (010000 and 011001) and instead link the two cycles together by first reversing the order of the first cycle, and then inserting the joins 000001 and 011010 to form a single cycle.

In general, suppose that P(k) is true for some k1. Then we construct a single cycle for the 2k+1 sequences of length k+1 as follows:

Take the cycle of the 2k sequences of length k guaranteed by P(k), and form two disjoint cycles of length 2k

• first by adding a final coordinate “0“

• then by adding a final coordinate “1”.

Then link the two cycles into a single cycle of length 2k+1, by eliminating the final step

v1v2vk00000 in the first cycle, and v1v2vk10001

in the second cycle, reversing the first cycle, and inserting the joins

00000001 and v1v2vk1v1v2vk0

to produce a single cycle of the required kind joining all 2k+1 sequences of length k+1. Hence P(k+1) is true.

Hence P(n) is true for all n2.

Note: The significance of what we call Gray codes was highlighted in a 1953 patent by the engineer Frank Gray (1887-1969) – where they were called reflected binary codes (since the crucial step in their construction above involves taking two copies of the previous cycles, reversing one of the cycles, and then producing half of the required cycle by traversing the first copy before returning backwards along the second copy). Their most basic use is to re-encode the usual binary counting sequence

11011100101110111100010011010,

where a single step can lead to the need to change arbitrarily many binary digits (e.g. the step from 3=''11” to 4=''100” changes 3 digits, and the step from 7=''111” to 8=“1000” changes 4 digits, etc.) – a requirement that is inefficient in terms of electronic “switching”, and which increases the probability of errors. In contrast, the Gray code sequence changes a single binary digit at each step. However, the physical energy which is saved through reducing the amount of “switching” in the circuitry corresponds to an increase in the need for unfamiliar mathematical formulae, which re-interpret each vector in the Gray code as the ordinary integer in the counting sequence to which it corresponds.

263.

(a) The whole construction is inductive (each label derives from an earlier label). So let P(n) be the statement:

“if HCF(r,s)=1 and 2r+sn, then the positive rational rs occurs once and only once as a label, and it occurs in its lowest terms”.

• By construction the root is given the label 11, so 11 occurs. And it cannot occur again, since the numerator and denominator of each parent vertex are both positive, neither i nor j can ever be 0. Hence P(2) is true.

Notice that the basic construction:

“if ij is a `parent' vertex, then we label its `left descendant' as ii+j, and its `right descendant' i+jj

guarantees that, since we start by labelling the root with the positive rational 11, all subsequent `descendants' are positive.

Moreover, if any `descendant' were suddenly to appear not “in lowest terms”, then either

HCF(i,i+j)>1, in which case HCF(i,i+j)=HCF(i,j), so HCF(i,j)>1 at the previous stage; or

HCF(i+j,j)>1, in which case HCF(i+j,j)=HCF(i,j), so HCF(i,j)>1 at the previous stage.

Since we begin by labelling the root 11, where HCF(1,1)=1, it follows that all subsequent labels are positive rationals in lowest terms.

• Suppose that P(k) is true from some k2.

Most parts of the statement P(k+1) are guaranteed by P(k). To show that P(k+1) is true, it remains to consider cases where HCF(r,s)=1 and r+s=k+1 (3). Either (i) r>s, or (ii) s>r.

(i) Suppose that r>s. Then rs arises in this (fully cancelled) form only as a direct (right) descendant of rss. So rs occurs. Moreover, every label occurs in its lowest terms, so rs cannot occur again.

(ii) Suppose that s>r. Then rs arises in this (fully cancelled) form only as a direct (left) descendant of rsr. So rs occurs. Moreover, every label occurs in its lowest terms, so rs cannot occur again.

Hence P(k+1) is true.

Hence P(n) is true for all n2.

(b) The fact that the labels are left-right symmetric is also an inductive phenomenon. We note that the one fully “left-right symmetric” label, namely 11, occurs in the only fully “left-right symmetric” position – namely at the root.

All other labels occur in reciprocal pairs: rs and sr, where we may assume that r>s. The fact that these occur as labels of “left-right symmetric” vertices derives from the fact that

rs is the `right descendant' of rss and

sr is the `left descendant' of srs.

So if we know that the earlier reciprocal pair reciprocal pair rss and srs occur as labels of symmetrically positioned vertices, then it follows that the same is true of the descendant reciprocal pair rs and sr. We leave the reader to write out the proof by induction – for example, using the statement

P(n): if r,s>0, and 2r+sn, then the reciprocal pair rs, sr occur as labels of vertices at the same level below the root, with the two labelled vertices being mirror images of each other about the vertical mirror through the root vertex.”

264. The intervals in this problem may be of any kind (including finite or infinite). Each interval has two “endpoints”, which are either ordinary real numbers, or ± (signifying that the interval goes off to infinity in one or both directions).

Let P(n) be the statement:

“if a collection of n intervals on the x-axis has the property that any two intervals overlap in an interval (of possibly zero length – i.e. a point), then the intersection of all intervals in the collection is a non-empty interval”.

When n=2, the hypothesis of P(2) is the same as the conclusion. So P(2) is true.

Suppose that P(k) is true for some k2. We seek to prove that P(k+1) is true.

So consider a collection of k+1 intervals with the property that any two intervals in the collection intersect in a non-empty interval. If this collection includes one interval that is listed more than once, then the required conclusion follows from P(k). So we may assume that the intervals in our collection are all different.

Among the k+1 intervals, consider first those with the largest right hand endpoint. If there is only one such interval, denote it by I0; if there is more than one interval with the same largest right hand endpoint, let I0 be the interval among those with the largest right hand endpoint that has the largest left hand endpoint. In either case, put I0 aside for the moment, leaving a collection S of k intervals with the required property.

By P(k) we know that the intervals in the collection S intersect in a non-empty interval I, with left hand endpoint a and right hand endpoint b (say).

We have to show that the intersection II0 is non-empty.

The proof that follows works if the endpoint b is included in the interval I. The slight adjustment needed if b is not included in the interval I is left to the reader.

Since the right hand endpoint of I0 is the largest possible, and since points between a and b belong to all the intervals of S, we can be sure that the right hand endpoint of I0 is b.

Moreover, for each point x>b, we know that there must be some interval Ix in the collection S which does not stretch as far to the right as x. Since, by hypothesis, the intersection I0Ix is non-empty, the left hand endpoint of I0 lies to the left of every such point x, so I0 must overlap the interval I, whence it follows that II0 is a non-empty interval as required.

Hence P(k+1) is true.

Hence P(n) is true for all n2.

265. If one experiments a little, it should become clear

• that if tank T2 contains more than tank T1, then linking tank T to T2 leads to a better immediate outcome (i.e. a larger amount in tank T) than linking T to T1;

• that if, at some stage in the linking sequence, tank T contains an interim amount of a litres, and is about to link successively to a tank containing b litres, and then to the tank containing c litres, this ordered pair of changes alters the amount in the tank T to a+b+2c4 litres; so for a better final outcome we should always choose the sequence so that b<c;

• once the tap linking tank T to another tank has been opened, so that the two levels become equal, there is no benefit from opening the tap linking these two tanks ever again, so tank T should be linked with each other tank at most once.

These three observations essentially determine the answer – namely that tank T should be joined to the other tanks in increasing order of their initial contents.

For a proof by induction, let P(n) be the statement:

“given n tanks containing a1,a2,a3,,an litres respectively, where

a 1 < a 2 < a 3 < < a n ,

if T is the tank containing the smallest amount a1 litres, then the optimal sequence for linking the other n1 tanks to tank T (optimal in the sense that it transfers the maximum amount of water to tank T) is the sequence that links T successively to the other tanks in increasing order of their initial contents”.

• When n=2, there is only one possible sequence, which is the one described, so P(2) is true.

• Suppose that P(k) is true for some k2, and consider an unknown collection of k+1 tanks containing a1,a2,a3,,ak+1 litres respectively, where

a1<a2<a3<<ak+1,

and where T is the tank which initially contains a1 litres.

Suppose that in the optimal sequence of k successive joins to the other k tanks (that is, that transfers the largest possible amount of water to tank T), the succession of joins is to join T first to tank T2, then to tank T3, and so on up to tank Tk+1 (where tank Tm is not necessarily the tank containing am litres). There are now two possibilities: either

(i) Tk+1 is the tank containing ak+1 litres, or

(ii) Tk+1 contains less than ak+1 litres.

(i) Suppose tank Tk+1 is the tank containing ak+1 litres. Then the first k1 joins involve the k tanks containing a1,a2,a3,,ak litres. And we know (by the very first bullet point above) that, in order to maximize the final amount in tank T, the amount in tank T after linking it to tank Tk must be “as large as it could possibly be”. Hence, by P(k), the first k1 joins link T successively to the other tanks in increasing order of their contents – before finally linking to the tank containing ak+1 litres. Hence the conclusion of P(k+1) holds.

(ii) Now suppose that tank Tk+1 contains am<ak+1 litres.

By the very first bullet point, in order to guarantee the optimal overall outcome of the final linking with tank Tk+1 the amount in tank T after it has been linked to tank Tk must be “as large as it can possibly be” (given the amounts in the tanks T,T2,T3,,Tk). Hence statement P(k) applies to the initial sequence of k1 joins (of T to T2, then to T3, and so on up to Tk), and guarantees that these tanks must be in increasing order of their initial contents. In particular, the last tank in this sequence, Tk, must be the one containing ak+1 litres. But if we denote by a litres the amount in tank T just before it links with tank Tk (containing ak+1 litres), then the last two linkings, with b=ak+1 and c=am contradict the second bullet point at the start of this solution. Hence case (ii) cannot occur.

Hence P(k+1) is true.

Hence P(n) is true for all n2.

266.

Note: Like all practical problems, this one requires an element of initial “modelling” in order to make the situation amenable to mathematical analysis.

`Residue' clings to surfaces; so the total amount of `residue' will depend on

(a) the viscosity of the chemical (how `thick', or `sticky' it is), and

(b) the total surface area of the inside of the flask.

Since we are given no information about quantities, we may fix the amount of residue remaining in the `empty' flask at “1 unit”, and the amount of solvent in the other flask as “s units”.

If we add the solvent, we get a combined amount of 1+s units of solution – which we may assume (after suitable shaking) to be homogeneous, with the chemical concentration reduced to “1 part in 1+s”.

The first modelling challenge arises when we try to make mathematical sense of what remains at each stage after we empty the flask. The internal surface area of the flask, to which any diluted residue may adhere, is fixed. If we make the mistake of thinking of the original chemical as “thick and sticky” and the solvent as “thin”, then the viscosity of the diluted residue will change relative to the original, and will do so in ways that we cannot possibly know. Hence the only reasonable assumption (which may or may not be valid in a particular instance) is to assume that the viscosity of the original chemical is roughly the same as the viscosity of the chemical-solvent mixture. This then suggests that, on emptying the diluted mixture, roughly the same amount (1 unit) of diluted mixture will remain adhering to the walls of the flask. So we will be left with 1 unit of residue, with a concentration of 11+s. In particular, if s=1, using all the solvent at once reduces the amount of toxic chemical residue to 12 unit (with the other 12 unit consisting of solvent).

But what if we use only half of the solvent first, empty the flask, and then use the other half? Adding s2 units of solvent (and shaking thoroughly) produces 1+s2 units of homogeneous mixture, with a concentration of 1 part per 1+s2. When we empty the flask, we expect roughly 1 unit of residue with this concentration – so just 22+s units of the chemical, with s2+s units of solvent.

If we then add the other s2 units of solvent, this produces 1+s2 units of mixture with a concentration of 1 part per (1+s2)2. When we empty the flask, we expect roughly 1 unit of residue with concentration 1 part per (1+s2)2. In particular, if s=1, this strategy reduces the amount of toxic chemical in the 1 unit of residue to 49 units. Since 49<12 this two-stage strategy seems more effective than the previous “all at once” strategy.

Suppose that we use a four-stage strategy – using first one quarter of the solvent, then another quarter, and so on. We then land up with roughly 1 unit of residue with concentration 1 part per (1+s4)4. In particular, if s=1, we land up with the amount of toxic chemical in the 1 unit of residue equal to 256625 units, and 256625<49. More generally, if we use (1n)th of the solvent, n times, the final amount of toxic chemical in the 1 unit of residue is equal to (1+sn)n. And as n gets larger and larger, this expression gets closer and closer to es. In particular, when s=1, this strategy leaves a final amount of chemical in the 1 unit of residue approximately equal to 1e=0.367879.

Note: The situation here is similar to that faced by a washing machine designer, who wishes to remove traces of detergent from items that have been washed, without using unlimited amounts of water. The idea of having a “fixed amount of solvent” corresponds to the goal of “water efficient” rinsing. However, the washing machine cycle, or programme, clearly cannot repeat the rinsing indefinitely (as would be required in the limiting case above).

267.

(i) If 2=mn, then

2n2=m2

Hence m2 is even.

It follows that m must be even.

Note: It is a fact that, if m=2k is even, then m2=4k2 is also even. But this is completely irrelevant here. In order to conclude that “m must be even”, we have to prove:

Claim m cannot be odd.

Proof Suppose m is odd.

m=2k+1 for some integer k.

But then

m 2 = (2k+1) 2 =4 k 2 +4k+1

would be odd, contrary to “m2 must be even”.

Hence m cannot be odd.

(ii) Since m is even, we may write m=2m for some integer m. Equation (*) in (i) above then becomes n 2 =2 ( m ) 2 , so n2 is even. Hence, as in the Note above, n must be even, so we can write n=2n for some integer n.

(iii) If 2=mn, then m=2m, and n=2n are both even.

2=mn=2m2n=mn.

In the same way, it follows that m and n are both even, so we may write m=2m'', n=2n'' for some integers m'', n''.

Continuing in this way then produces an endless decreasing sequence of positive denominators

n>n>n''>>0.

contrary to the fact that such a sequence can have length at most n1 (or in fact, at most 1+log2n).

268.

(i) If a<b and c>0, then ac<bc.

If 0<21, then (multiplying by 2) it follows that 221, which is false. Hence 2>1.

We now know that 1<2, so multiplying by 2 gives 2<2. Hence 1<2<2. In particular, 2 cannot be written as a fraction with denominator 1, so P(1) is true.

(ii) Suppose P(k) is true for some k1. Most of the statement P(k+1) is implied by P(k): all that remains to be proved is that 2 cannot be written as a fraction with denominator n=k+1.

Suppose 2=mn, where n=k+1 and m are positive integers.

Then m=2m and n=2n are both even (as in Problem 267).

So 2=mn with nk, contrary to P(k). Hence P(k+1) holds.

P(n) is true for all n1.

269.

(a) Suppose that S is not empty. Then by the Least Element Principle the set S must contain a least element k: that is, a smallest integer k which is not in the set T. Then k1 (since we are told that T contains the integer 1). Hence k>1.

Therefore k1 is a positive integer which is smaller than k. So k1 is not an element of S, and hence must be an element of T. But if k1 is an element of T, then we are told that (k1)+1 must also be a member of T. This contradiction shows that S must be empty, so T contains all positive integers.

(b) Suppose that T does not have a smallest element. Clearly 1 does not belong to the set T (or it would be the smallest element of T). Hence 1 must be an element of the set S.

Now suppose that, for some k1, all positive integers 1,2,3,,k are elements of S, but k+1 is not an element of S. Then k+1 would be an element of T, and would be the smallest element of T, which is not possible. Hence S has the property that

“whenever k1 is an element of S, we can be sure that k+1 is also an element of S.”

The Principle of Mathematical Induction then guarantees that these two observations (that 1 is an element of S, and that whenever k is an element of S, so is k+1) imply that S contains all the positive integers, so that the set T must be empty – contrary to assumption.

Hence T must have a smallest element.

270.

(i) Triangle OPQ is a right angled triangle with POQ=45°. Hence the two base angles (at O and at Q) are equal, so the triangle is isosceles: PQ_=PO_.

(ii) Triangles QQP and QQR are congruent by RHS (since they share the hypotenuse QQ_, and have equal sides (QP_=QP_=QR_). Hence QP_=QR_.

(iii) If OQ_:OP_=m:n, we may choose a unit so that OQ_ has length m units and OP_ has length n units. Then

OP_=OQ_QP_=OQ_QP_=mn,

and

OQ_=OR_QR_=OR_QP_=OR_OP_=n(mn).

(iv) OP_<OQ_<OP_+PQ_, so n<m<n+n. Hence 0<mn<n, and 0<2nm.

(v) In the square OPQR, the ratio “diagonal: side” =OQ_:OP_=2:1. If the ratio OQ_:OP_=m:n, with m, n positive integers, then the construction here replaces the positive integers m, n by smaller positive integers 2nm and mn, with mn<n. And the process can be repeated indefinitely to generate an endless sequence of decreasing positive integers

n>mn>(2nm)(mn)=3n2m>>0.

Zarathustra's last, most vital lesson: “Now do without me.”

George Steiner (1929-)