2.10: Comments and solutions

40.

(a) (i) 111111111

(ii) 9009 (1001 = 7 × 11 × 13 is a factorisation that is worth remembering for all sorts of reasons: for example, it incorporates 91 = 7 × 13; and it lies behind certain tests for divisibility by 7).

(b) (i) 1001001; (ii) 1001001; (iii) 3 003 003 (since 111 = 3 × 37)

41.

(i) ${(10+1)}^2=10^2+2\times 10+1^2=121$;

(ii) ${(10+1)}^3=10^3+3\times 10^2+3\times 10+1^3=1331$;

(iii) ${(100+1)}^2=100^2+2\times 100+1^2=10000+200+1=10201$

42.

(a) (i) Largest 8, smallest 7. (The smallest 3-digit number is 100 and the smallest 5-digit number is 10 000, so the smallest possible product is $10^2\times 10^4=10^6$- and so has 7 digits. The largest 3-digit number is just less than 1000 and the largest 5-digit number is just less than 100 000, so the largest possible product is just less than $10^3\times 10^5=10^8$ – and so has 8 digits.)

(ii) Largest $m+n$, smallest $m+n-1$. (The smallest m-digit number is $10^{m-1}$ and the smallest n-digit number is $10^{n-1}$, so the smallest possible product is $10^{m+n-2}$ – and so has $m+n-1$ digits. The largest m-digit number is just less than 10^m and the largest n-digit number is just less than 10ⁿ, so the largest possible product is just less than $10^m\times 10^n=10^{m+n}$ – and so has $m+n$ digits.)

(b) (i) $2^{10}=1024$ is very slightly larger than 10³. Hence $2^{20}=1024^2$ is very slightly larger than 10⁶, so has 7 digits.

(ii) 2²⁰ is very slightly larger than 10⁶. In fact

$$\begin{array}{c}{(10^3+24)}^2=10^6+2\times 10^3+24^2=10^6+2\times 10^3+576=1002576.\hfill \end{array}$$

${\left(\genfrac{}{}{0.1ex}{}{1}{2}\right)}^{20}$ is its reciprocal, so is slightly smaller than $10^{-6}=0.000001$, so it starts with six 0s after the decimal point and rounds up to 0.000001 (to 6 d.p.).

(c) No. (It can be equal to the product of its digits if it has just 1 digit. If a number N has k digits, with leading digit = m, then $N\ge m\times 10^{k-1}$, but the product of its digits is at most $m\times 9^{k-1}$.)

(d) (i) 3, 6. ($2^{15}\times 5^3=2^{12}\times 10^3=4096\times 10^3$)

(ii) 4, 4. (Most of us will need some rough work to supplement mental arithmetic here.

$$\begin{array}{c}20!=20\times 19\times 18···\times 2\times 1\hfill \\ =2^{18}\times 3^8\times 5^4\times 7^2\times 11\times 13\times 17\times 19\hfill \\ ={10}^4\times 2^{14}\times 3^8\times 7^2\times 11\times 13\times 17\times 19.\hfill \end{array}$$

So 20! ends in 4 zeros, and its last non-zero digit is equal to the units digit of $2^{14}\times 3^8\times 7^2\times 11\times 13\times 17\times 19$. If we work “mod 10” this is equal to the units digit of $4\times 1\times 9\times 1\times 3\times 7\times 9$.)

Note: The reader may notice that we have used “congruences”, or “modular arithmetic” (mod 10) here and at several points in Chapter 1 (e.g. in the solutions to Problem 2(d), Problem 13, Problem 16(b)).

In all these contexts one only needs to know that, if we fix the divisor n, then the remainders on division by n can be added and multiplied like ordinary numbers, since

$$\begin{array}{c}(an+r)+(bn+s)=(a+b)n+(r+s),\hfill \end{array}$$

and

$$\begin{array}{c}(an+r)(bn+s)=(abn+as+br)n+rs.\hfill \end{array}$$

Division is more delicate. We leave the reader to look up the details in any book on elementary number theory.

43. (a) 00 000123450 (b) 99 999 785 960

The initial number $(12\cdots 91011\cdots 5960)$ has $9+50\times 2+2=111$ digits. Hence we are left with a number having exactly 11 digits.

For the smallest integer, we delete digits to leave the smallest initial digits (preferably 0s).

For the largest integer, we delete digits to leave as many 9s at the front as possible (and then sort out the tail).

44.

$$\begin{array}{c}11111111=11110000+1111=1111\times 10001.\hfill \end{array}$$

In much the same way

$$\begin{array}{c}1111\cdots 1111000\hfill \end{array}$$

(with 1108 1s and three 0s) is exactly divisible by 1111. So the remainder is 111.

45. Compare $(10^5+1)(10^7+2)$ and $(10^5+2)(10^7+1)$.

The second is $10^7-10^5$ bigger than the first, so the second fraction is bigger than the first.

46. The fact that $3\times 7=21$, and the position of the zeros, suggests that we express the integer as:

$$\begin{array}{c}10^{35}+3\times 10^{24}+7\times 10^{11}+3\times 7=(10^{11}+3)(10^{24}+7).\hfill \end{array}$$

Note: If you feel you should have been “given a hint”, then pause for a moment. There is nothing misleading here. We have no standard techniques for analysing such large numbers. The very size of the number forces you to think whether there is anything familiar about it that you might use. And the number is so simple that the only thing that can possibly stand out is the 3, 7, and 21. The rest is up to you.

47.

(a) 11 is prime. And 111 is a multiple of 3: $111=3\times 37$. You should also be able to see that 1111 is a multiple of 11: $1111=11\times 101$.

It is unclear whether 11111 is prime or not. The Square Root Test says that to decide, we only need to check possible prime factors up to $\sqrt{11111}<107$. We can eliminate 2, 3, 5, 7, 11 mentally, with very little effort. And with a calculator, it is easy to check 13, 17, 19, 23, 29, 31, 37, 41, ... and to discover that $11111=41\times 271$.

Clearly $111111=11\times 10101=111\times 1001$.

So the sequence does not look too promising. All the even-numbered terms are divisible by 11; every third term is divisible by 111 (and of course, by 3); every fourth term is divisible by 1111 (and hence by 101); and so on. So the only possible candidates for primes are the second, third, fifth, seventh, eleventh, ... terms: that is the terms in prime positions.

Each of these terms is equal to the second bracket in the factorisation:

$$\begin{array}{c}10^p-1=(10-1)(10^{p-1}+10^{p-2}+\cdots +10+1),\hfill \end{array}$$

where p is a prime number.

We have seen that $111=3\times 37$, and that $11111=41\times 271$, which is not very encouraging. The 7^th, 11^th, 13^th, and 17^th terms are also not prime. But the 19^th term and the 23^rd terms are prime.

So primes seem scarce, but 11 is not the only prime in the sequence.

Note: Again, if you feel the problem was misleading, then pause for a moment. Part of “the essence of mathematics” is learning that some problems have a tidy solution, while others open up a rather different agenda. The only obvious way to begin to recognise this distinction is occasionally to be left to struggle to solve something that is presented as if it were a closed problem (with a tidy solution), only to discover that it is messier than one expected.

(b) We have already seen that $1001=7\times 11\times 13$.

Another reason for remembering this is that it is a simple instance of the standard factorisation:

$$\begin{array}{c}10^3+1=(10+1)(10^2-10+1)\hfill \end{array}$$

Because the signs in the second bracket are alternately “+” and “-”this factorisation extends to all odd powers of 10: for example,

$$\begin{array}{c}100001=10^5+1=(10+1)(10^4-10^3+10^2-10+1)\hfill \end{array}$$

So this time, 11 is the only prime in the list.

Note: The missing “odd” terms

$$\begin{array}{c}\mathrm{101,10}\mathrm{001,1}000\mathrm{001,100}000001,\dots \dots \hfill \end{array}$$

are slightly different – each being of the form $x^2+1$.

The fact that there is an algebraic factorisation of

$$x^3+1=(x+1)(x^2-x+1)$$

implies that $1001=10^3+1$ has to factorise. But the lack of an algebraic factorisation of $x^2+1$ does not prevent any particular number of the form $x^2+1$ from factorising: for example, $3^2+1=2\times 5$, and $5^2+1=2\times 13$ both factorise; but $4^2+1$, $6^2+1$, and $10^2+1$ do not.

One may be forgiven for not knowing that $10^4+1=10001=73\times 137.$ But one should realize that

$$\begin{array}{c}10^6+1=100^3+1=(100+1)(100^2-100+1).\hfill \end{array}$$

48. The prime factorisation $111=3\times 37$ is worth remembering. If this is second nature, then one can do better in this problem than merely grind out the answer using long multiplication, by seeing how the output to the calculation $1001\times 333$ simply positions “333 thousands” and “333 units” next to each other:

$3\times 37=111$, so $9\times 37=333$.

Hence $9009\times 37=1001\times 333=333333$.

Note: The prime factorisation of 1001 is not needed here. But it is important elsewhere.

49. The very first step shows that the leading digit of the dividend must be 1; and since “three-digit minus two-digit leaves one-digit (d say)” the divisor has a multiple in the 90s.

The very next stage again gives “three-digit minus two-digit leaves one-digit”, and the remainder from the first division is now the hundreds digit, so d = 1. Hence the two-digit divisor has 99 as a multiple (at the first step of the long division) – so the divisor must be 11, 33, or 99.

The next division shows that the divisor has a two-digit multiple, which when subtracted from a two-digit number leaves a two-digit remainder, so the divisor cannot be 99.

The final stage shows that the divisor has a three-digit multiple, so it cannot be 11.

Hence the divisor must be 33.

50. Your solution will depend on the programming language used. We use this problem to attract the reader’s attention to some not so frequently discussed issues:

• The “formal written algorithms” of arithmetic are not entirely obvious.
• Their practical use is not really “formal”, it uses a number of unstated conventions. For example, it requires from the user an intuitive feel for the “data structures” involved and starts by writing one base 10 integer under another keeping digits in the same decimal position aligned in a column (a computer scientist would call it “parsing the input”).
• Base 10 integers contain different numbers of digits and shorter ones may need to be padded with zeroes (mentally, in calculations on paper, or explicitly, as may be necessary when writing code), that is, $1234+56$ has to be treated as $1234+0056$.
• Digits in the number are read and used from right to left, the opposite way to reading text. (This may be a piece of fossilised history: our decimals are Arabic, and Arabs write from right to left.)

51.

(a) This exploits the fact that

$$\begin{array}{c}(10^k-1)=(10-1)(10^{k-1}+10^{k-2}+\dots +10+1),\hfill \end{array}$$

and so is divisible by $(10-1)$ (a fact which is obvious when we write $10-1=9$, $10^2-1=99$, $10^3-1=999$, etc.). For example:

$$\begin{array}{ccc}\mathrm{12\; 345}\hfill & =\hfill & \mathbf{1}\times 10^4+\mathbf{2}\times 10^3+\mathbf{3}\times 10^2+\mathbf{4}\times 10+\mathbf{5}\hfill \\ \hfill & =\hfill & [\mathbf{1}\times (10^4-1)+\mathbf{2}\times (10^3-1)+\mathbf{3}\times (10^2-1)+\mathbf{4}\times (10-1)]\hfill \\ \hfill & \hfill & +[\mathbf{1}+\mathbf{2}+\mathbf{3}+\mathbf{4}+5]\hfill \\ \hfill & =\hfill & \left[\text{a sum of terms, each of which is a multiple of 9}\right]\hfill \\ \hfill & \hfill & +\left[\text{the sum of the digits of “}\mathrm{12\; 345}\text{”}\right]\hfill \end{array}$$

If the LHS is divided by 9, the remainder from the first bracket on the RHS is zero, so the overall remainder is the same as the remainder from dividing the digit sum by 9.

Since 9 is a multiple of 3, the first bracket is exactly divisible by 3. Hence if the LHS is divided by 3, the remainder from the first bracket on the RHS is zero, and the overall remainder is the same as the remainder from dividing the digit sum by 3.

Note: If we were only interested in “divisibility by 9”, then we could have managed without appealing to the algebraic factorisation

$$\begin{array}{c}(10^k-1)=(10-1)(10^{k-1}+10^{k-2}+\dots +10+1),\hfill \end{array}$$

since

$$\begin{array}{c}10-1=9,10^2-1=99,10^3-1=999,\dots \hfill \end{array}$$

are all visibly “multiples of 9”. However, the structure of the above solution extends naturally to prove that, when an integer is written in base b, the remainder on division by $b-1$ is the same as the remainder on dividing the base b “digit sum” by $b-1$.

(b) If an integer N is divisible by 6, then we can write $N=6m$ for some integer m.

Hence $N=(2\times 3)m=2\times \left(3m\right)$, so N is a multiple of 2; and $N=3\times \left(2m\right)$, so N is a multiple of 3.

If an integer N is divisible by 2, then we can write $N=2k$ for some integer k. If N is also divisible by 3, then 3 divides exactly into 2k. But HCF(2, 3) = 1, so the 3 must go exactly into the second factor k, so $k=3m$ for some integer m, and $N=6m$ is divisible by 6.

Note: It is crucial that HCF(2, 3) = 1. (E.g. 12 is divisible by 6 and by 4; but 12 is not divisible by $6\times 4$.)

52.

(a) N is divisible by 3. Hence its digit-sum is divisible by 3.

But then “three times the sum of its digits” is a multiple of 9: hence the integer is divisible by 9, and so the sum of its digits is divisible by 9.

But then it is divisible by “three time a multiple of 9” – that is divisible by 27. So $N=27$, or 54, or 81, or 108, or .... (However, you soon come to the first multiple of 27 that is not “divisible by 3 times the some of its digits”.)

(b) 27. (Suppose the integer N has k digits. Then $N\ge 10^{k-1}$, and its digit-sum is at most 9k. If N is equal to “three times the sum of its digits”, then $10^{k-1}\le N\le 27k$ which means $k\le 2$. And from part (a) we know that N is a multiple of 27.)

(c) 288. (If the digit sum is equal to 9 (or any odd multiple of 9), then at least one digit must be odd; so we only need to worry about integers with digit-sum equal to 18, or 36, or .... The only such multiple of 9 up to 100 is 99. All multiples of 9 between 100 and 200 have an odd hundreds digit. In the 200s, the first integer with digit-sum 18 is 279 – with two odd digits. The next is 288.)

53. (a) This exploits the fact that

$$\begin{array}{c}(11^k-1)=(11-1)(11^{k-1}+11^{k-2}+\dots +11+1),\hfill \end{array}$$

and so is divisible by (11 — 1) – a fact which is obvious if we introduce a new digit X in base 11 to stand for “ten”, and then notice that

$$\begin{array}{c}11-1=X_{\text{base}11},11^2-1=X{X}_{\text{base}11},11^3-1=XX{X}_{\text{base}11},\text{etc.}\hfill \end{array}$$

For example:

$$\begin{array}{ccc}{12345}_{\text{base}11}\hfill & =\hfill & \mathbf{1}\times 11^4+\mathbf{2}\times 11^3+\mathbf{3}\times 11^2+\mathbf{4}\times 11+\mathbf{5}\hfill \\ \hfill & =\hfill & [\mathbf{1}\times (11^4-1)+\mathbf{2}\times (11^3-1)+\mathbf{3}\times (11^2-1)+\mathbf{4}\times (11-1)]\hfill \\ \hfill & \hfill & +[\mathbf{1}+\mathbf{2}+\mathbf{3}+\mathbf{4}+5]\hfill \\ \hfill & =\hfill & \left[\text{a sum of terms, each of which is a multiple of ten}\right]\hfill \\ \hfill & \hfill & +\left[\text{the sum of the digits of “}\mathrm{12\; 345}\text{”}\right]\hfill \end{array}$$

If the LHS is divided by ten, the remainder from the first bracket on the RHS is zero, so the overall remainder is the same as the remainder from dividing the digit sum by ten.

54.

(a) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78.

(b) Combine two copies of the required sum. If we do this algebraically, we get

$$\begin{array}{c}\begin{array}{ccccccccc}\hfill 1\hfill & \hfill +\hfill & \hfill 2\hfill & \hfill +\hfill & \hfill 3\hfill & \hfill +\hfill & \hfill \cdots \hfill & \hfill +\hfill & \hfill n\hfill \\ \hfill n\hfill & \hfill +\hfill & \hfill n-1\hfill & \hfill +\hfill & \hfill n-2\hfill & \hfill +\hfill & \hfill \cdots \hfill & \hfill +\hfill & \hfill 1\hfill \end{array}\hfill \end{array}$$

and observe that each of the n vertically aligned columns adds to n+1.

Hence

$$\begin{array}{c}{T}_n=1+2+3+\cdots +n=\genfrac{}{}{0.1ex}{}{n(n+1)}{2}.\hfill \end{array}$$

If we do the same geometrically, then we can combine two “staircases”

$$\begin{array}{c}\begin{array}{cccccc}\hfill •\hfill & \hfill •\hfill & \hfill •\hfill & \hfill •\hfill & \hfill \hfill & \hfill \hfill \\ \hfill •\hfill & \hfill •\hfill & \hfill •\hfill & \hfill \hfill & \hfill \hfill & \hfill •\hfill \\ \hfill •\hfill & \hfill •\hfill & \hfill \hfill & \hfill \hfill & \hfill •\hfill & \hfill •\hfill \\ \hfill •\hfill & \hfill \hfill & \hfill \hfill & \hfill •\hfill & \hfill •\hfill & \hfill •\hfill \\ \hfill \hfill & \hfill \hfill & \hfill •\hfill & \hfill •\hfill & \hfill •\hfill & \hfill •\hfill \end{array}\hfill \end{array}$$

of dots (one of which is inverted) into an n by $n+1$ array of dots (either with n columns and $n+1$ dots in each column, or with $n+1$ columns and n dots in each column).

Note: The n^th triangular number is defined by the “formula”

$$\begin{array}{c}{T}_n=1+2+3+\cdots +n.\hfill \end{array}$$

But this “formula” has serious limitations: in particular, there is no way to calculate Tioo without first calculating T₁, then T₂, then T₃, ... all the way up to Tgg. Hence it is just a “recurrence relation”, which tells us how to find T_n once we know T_n-1 (just “add n”).

The formula

$$\begin{array}{c}{T}_n=\genfrac{}{}{0.1ex}{}{n(n+1)}{2}\hfill \end{array}$$

derived in part (b) is much more useful, in that it allows us to work out the value of T_n as soon as we know the value of n. This is what we call a “closed formula”. (The language may seem strange, but it refers to the fact that the calculation is direct, and that the formula involves a small, fixed number of operations – whereas using the recurrence requires more and more work as n gets larger.)

(c) Note: There are two reasons why these questions are worth asking. The first is that whenever we focus attention on certain special classes of objects, it is always good practice to consider whether the notions we have defined are completely separate, and to try to identify any overlaps. The second reason is less obvious, but can be surprisingly fruitful: sometimes two ideas may be interesting, yet have nothing to do with each other; but at other times, the two ideas may not only be interesting in their own right, but may “combine” in a way that gives rise to surprising subtleties. Here two of the combinations are routine and uninteresting; but two combinations generate more interesting mathematics than we have a right to expect.

(i) We know that one of the two factors n and $n+1$ in the numerator is odd, and the other is even. If the triangular number

$$\begin{array}{c}{T}_n=\genfrac{}{}{0.1ex}{}{n(n+1)}{2}\hfill \end{array}$$

is to be a power of 2, then any odd factor of T_n must be equal to 1, so $n<3:n=2$ does not give a power of 2. Hence $n=1$, and $T_n=1$ is the only triangular number which is also a power of 2.

(ii) If the triangular number T_n is to be prime, then either

* n is odd and one of n, $\genfrac{}{}{0.1ex}{}{n+1}{2}$ is equal to 1 (so $n=1$ and $T_1=1$ is not prime), or

* n is even and one of $\genfrac{}{}{0.1ex}{}{n}{2}$, $n+1$ is equal to 1, so $n=2$, and $T_2=3$ is the only triangular number which is also prime.

(iii) The only immediately obvious “square triangular numbers T_n“ are the first and the eighth – namely $T_1=1$ and $T_8=36$. But what seems obvious is rarely the whole truth. There are in fact infinitely many such “square triangular numbers” (e.g. $T_{\mathrm{49}}=1225$, $T_{\mathrm{288}}=41616$, $T_{\mathrm{1681}}=1413721$, ...). This is a consequence of the formula in part (b). For example:

When n is even, we notice that $a=\genfrac{}{}{0.1ex}{}{n}{2}$ and $n+1=2a+1$ are integers with no common factors. We want their product to be a square. Because $HCF(a\mathrm{,2}a+1)=1$, this occurs precisely when both $a(=b^2)$ and $2a+1(=c^2)$ are both squares. So we see that solutions correspond to pairs of integers b, c which satisfy the Pell equation $c^2=2b^2+1$. Notice that $b=2$, $c=3$ is one solution, and that they satisfy the equation $c^2-2b^2=1$.

We have already met

$$a^2+b^2=(a+bi)(a-bi)$$

as the norm (or square of the length) of the complex number $a+bi$ (Problem 25). In a similar way, we can “factorise”

$$\begin{array}{c}{c}^2-2b^2=(c+b\sqrt{2})(c-b\sqrt{2}).\hfill \end{array}$$

So once we have one solution of the equation $c^2-2b^2=1$, we can take powers to get more solutions:

$$\begin{array}{c}\left[{(c+b\sqrt{2})}^2\right]\left[{(c-b\sqrt{2})}^2\right]=1^2=1,\text{etc.}.\hfill \end{array}$$

Hence, for example,

$$\begin{array}{c}{(3+2\sqrt{2})}^2=17+12\sqrt{2}\hfill \end{array}$$

gives rise to the solution $b=12$, $c=17$ -- corresponding to $\mathit{a}=144$, $n=288$.

Similarly

$$\begin{array}{c}{(3+2\sqrt{2})}^3=\dots +\dots \sqrt{2}\hfill \end{array}$$

gives rise to the solution $b=\dots$, $c=\dots$, corresponding to ($a=\dots$), $n=\dots$.

Note: If you are not yet familiar with complex numbers, or with the idea of a norm, don’t worry. Make a note of it as something that seems to be powerful and is worth learning. It will reappear later.

(iv) The only obvious cube triangular number is the first one – namely $T_1=1$. Basic algebra leads quickly to an equation as in part (i):

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{n(n+1)}{2}=m^3,\hfill \end{array}$$

which is equivalent to

$$\begin{array}{c}{(2n+1)}^2-1={\left(2m\right)}^3.\hfill \end{array}$$

So ${\left(2m\right)}^3$ and ${\left(2m\right)}^3+1$ are consecutive integers that are both proper powers. Catalan (1814–1894) conjectured in 1844 that $8=2^3$ and $9=3^2$ are the only consecutive powers (other than 0 and 1). This simple-sounding conjecture was finally proved only in 2004. It follows that $T_1=1$ is the only triangular number that is also a cube.

55.

(a)(i) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

(ii) 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34; 1, 1, 0, 1, 1, 2, 3, 5, 8, 13

(iii) m^th term of k^th sequence of differences $=F_{m-k}$

(b) (i) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048

(ii) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024; 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

(iii) m^th term of k^th sequence of differences $=2^m$

56.

(a) (i) 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, ...

(ii) $x^{n+1}-1=(x-1)(x^n+x^{n-1}+\cdots +x+1)$.

When $x=2$, the first factor on the RHS ($(x-1)=1$, so

$$\begin{array}{c}{2}^0+2^1+2^2+\cdots +2^n=2^{n+1}-1.\hfill \end{array}$$

[Alternatively:

$$\begin{array}{ccc}{2}^0+(2^0+2^1+2^2+\cdots +2{}^n)\hfill & =\hfill & (2^0+2^0[=2^1])+(2^1+2^2+\cdots +2{}^n)\hfill \\ \hfill & =\hfill & (2^1+2^1[=2^2])+(2^2+2^3+\cdots +2^n)\hfill \\ \hfill & =\hfill & (2^2+2^2[=2^3])+(2^3+2^4+\cdots +2^n)\hfill \\ \hfill & =\hfill & \dots \hfill \\ \hfill & =\hfill & (2^n+2^n)=2^{n+1}.\hfill \end{array}$$

(b) (i) 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, ...

(ii) $$\begin{array}{c}{F}_0+F_1=F_2=F_3-F_1\hfill \\ F_0+F_1+F_2=(F_3-F_1)+F_2=(F_3+F_2)-F_1=F_4-F_1\hfill \\ F_0+F_1+F_2+F_3=(F_4-F_1)+F_3=(F_4+F_3)-F_1=F_5-F_1.\hfill \end{array}$$

Claim:

$$F_0+F_1+F_2+\cdots +F_{n-1}=F_{n+1}-F_1$$

holds for all $n\ge 1$.

Proof: When $n=1$, the $LHS=F_0=0=1-1=F_2-F_1=RHS$.

We proved the next few case $n=2$, $n=3$, $n=4$ above.

Suppose we have already proved the required relation holds all the way up to the ${(k-1)}^{\mathrm{th}}$ equation:

$$F_0+F_1+F_2+\cdots +F_{k-1}=F_{k+1}-F_1.$$

Then the $k^{\mathrm{th}}$ equation follows like this:

$$\begin{array}{ccc}\hfill (F_0+F_1+F_2+\cdots +F_{k-1})+F_k& =\hfill & (F_{k+1}-F_1)+F_k\hfill \\ \hfill & =\hfill & (F_{k+1}+F_k)-F_1\hfill \\ \hfill & =\hfill & F_{k+2}-F_1.\hfill \end{array}$$

So we have shown

* that the identity holds for the first few values, and

* that whenever we know it is true up to the ${(k-1)}^{\mathrm{th}}$ identity, it also holds for the $k^{\mathrm{th}}$ identity.

Hence the identity holds for all $n\ge 1$ QED

Alternatively:

$$\begin{array}{ccc}\hfill F_1+(F_0+F_1+\cdots +F_k)& =\hfill & (F_1+F_0[=F_2])+(F_1+F_2+\cdots +F_k)\hfill \\ \hfill & =\hfill & (F_2+F_1[=F_3])+(F_2+F_3+\cdots +F_k)\hfill \\ \hfill & =\hfill & (F_3+F_2[=F_4])+(F_3+F_4+\cdots +F_k)\hfill \\ \hfill & =\hfill & \dots \hfill \\ \hfill & =\hfill & F_{k+1}+F_k=F_{k+2}.\hfill \end{array}$$

Note: In 56(a)(ii) we appealed directly to the factorisation of $x^{n+1}-1$ as though this were a “known fact” which is easy to prove. And in the “alternative” proof, we repeatedly combined “$2^k+2^k$“ to make $2^{k+1}$, inserting dots “... “ to indicate that this replacement operation is repeated $n+1$ times. Both of these involved thinly veiled applications of the principle of Mathematical Induction, which is addressed in detail in Chapter 6. In 56(b)(ii) we had no way of concealing the use of “proof by Mathematical Induction “, which is likely to be lurking whenever we have a proposition, or statement, P(n) involving the parameter n andwe wish to prove the infinite collection of assertions:

“P(n) is true for every $n=\mathrm{1,2}\mathrm{,3},\dots$ ”

The standard way of achieving this apparent miracle of proving infinitely many things at once is to check that $\mathbf{P}\left(1\right)$ holds (that is, to check that $\mathbf{P}\left(n\right)$ is true when $n=1$ ); then to suppose that we have checked all of the instances P(1), P(2), …, up to P(k) for some $k\ge 1$ , and to show that the next instance $\mathbf{P}(k+1)$ must then also be true.

We then conclude that P(n) is true for all $n\ge 1$.

57.

(a) (i) 0, 2, 3, 10, 24, 65, 168, ...

(ii) Guess:

$$\begin{array}{c}{F}_{n-1}{F}_{n+1}=F_n^2+{(-1)}^n{F}_1,\text{for all}n\ge 1.\hfill \end{array}$$

Proof: By part (i), this identity holds for $n=\mathrm{1,2}\mathrm{,3}\mathrm{,4}\mathrm{,5}\mathrm{,6}\mathrm{,7}$.

Suppose we have checked it as far as the $k^{th}$ instance:

$$\begin{array}{c}{F}_{k-1}{F}_{k+1}=F_k^2+{(-1)}^k{F}_1.\hfill \end{array}$$

Then the next instance follows, since

$$\begin{array}{ccc}{F}_{(k+1)-1}{F}_{(k+1)+1}\hfill & =\hfill & F_k{F}_{k+2}\hfill \\ \hfill & =\hfill & (F_{k+1}-F_{k-1})(F_k+F_{k+1})\hfill \\ \hfill & =\hfill & F_{k+1}^2+(F_{k+1}{F}_k-F_{k-1}{F}_k)-F_{k-1}{F}_{k+1}\hfill \\ \hfill & =\hfill & F_{k+1}^2+(F_k^2-F_{k-1}{F}_{k+1})\hfill \\ \hfill & =\hfill & F_{k+1}^2+{(-1)}^{k+1}{F}_1.\hfill \end{array}$$

So we have shown that the identity holds for the first few values of n, and whenever we know it is true up to the k^th identity, it also holds for the ${(k+1)}^{th}$ identity. Hence the identity holds for all $n\ge 1$. QED

(b)(i) We suppose that

$$\genfrac{}{}{0.1ex}{}{b}{a}<\genfrac{}{}{0.1ex}{}{d}{c}$$

(if the inequality is reversed, the expression for the area is multiplied by “−1”).

The lines $x=0$, $y=0$, $x=a+c$, $y=b+d$ form a rectangle of area $(a+c)(b+d)$, which surrounds the parallelogram.

To get from this to the area of the parallelogram, we must subtract

* the two external corner rectangles (top left, and bottom right) – each of area bc; and

* the four external right angled triangles–which fit together in pairs to make rectangles of areas ab and cd. Hence

$$\begin{array}{c}\text{area}\left(OABC\right)=(a+c)(b+d)-2bc-ab-cd=ad-bc.\hfill \end{array}$$

(ii) 1

(iii) Half of the 2^nd parallelogram is equal to half of the 1^st – so both have the same area, namely 1.

Half of the 3^rd parallelogram is equal to half of the 2^nd – so they both have the same area, namely 1.

And so on. Hence the area of the n^th parallelogram is equal to

$$\begin{array}{c}|ad-bc|=|F_{n-1}{F}_{n+1}-F_n^2|=1.\hfill \end{array}$$

Part (a)(ii) is more precise in that it says that $F_{n-1}{F}_{n+1}-F_n^2={(-1)}^n$: this says that the relative positions of the generators (a, b), (c, d) for successive Fibonacci parallelograms alternate, with first $\genfrac{}{}{0.1ex}{}{b}{a}>\genfrac{}{}{0.1ex}{}{d}{c}$, and then $\genfrac{}{}{0.1ex}{}{b}{a}<\genfrac{}{}{0.1ex}{}{d}{c}$. (In fact the gradient of successive versions of the line OA, or the ratio of successive Fibonacci numbers, converges to the Golden Ratio $\tau$, with successive Fibonacci points $A=(F_{n-1},F_n)$ alternately above and below the line with equation $y=\tau x$.)

58.

(a) 1, 2, 5, 13, 34, ...

(b) Guess:

$$\begin{array}{c}{F}_{n-1}^2+F_n^2=F_{2n-1}.\hfill \end{array}$$

Note: When part (a) gives rise unexpectedly to “the odd-numbered terms of the Fibonacci sequence”, it is almost impossible to believe that this is an accident. Yet the attempt to prove that this “Guess” is correct may well prove elusive – for it is hard to see how to relate the ${(n-1)}^{\mathrm{th}}$ and $n^{\mathrm{th}}$ terms to the ${(2n-1)}^{\mathrm{th}}$ term.

One approach is to

“try to prove something stronger than what seems to be required”.

Claim: For each $n\ge 1$, both of the following are true:

$$\begin{array}{c}{F}_{n-1}^2+F_n^2=F_{2n-1}\text{and}{F}_{n+1}^2-F_{n-1}^2=F_{2n}.\hfill \end{array}$$

Proof: We have already checked that the first relation holds for n = 1,2, 3,4, 5.

And it is easy to check that

$$\begin{array}{ccc}{F}_{1+1}^2-F_{1-1}^2\hfill & =\hfill & 1-0=1=F_2,\hfill \\ F_{2+1}^2-F_{2-1}^2\hfill & =\hfill & 4-1=3=F_4,\hfill \\ F_{3+1}^2-F_{3-1}^2\hfill & =\hfill & 9-1=8=F_6.\hfill \end{array}$$

So both identities hold for the first few values of n.

Now suppose we have checked that both relations hold all the way up to the $k^{\mathrm{th}}$ pair of relations.

Then simply adding the two relations in the $k^{\mathrm{th}}$ pair gives the first relation of the next pair:

$$\begin{array}{ccc}{F}_k^2+F_{k+1}^2\hfill & =\hfill & (F_{k-1}^2+F_k^2)+(F_{k+1}^2-F_{k-1}^2)\hfill \\ \hfill & =\hfill & F_{2k-1}+F_{2k}\hfill \\ \hfill & =\hfill & F_{2k+1}\hfill \end{array}$$

To see that the second relation of the next pair also follows, consider

$$\begin{array}{ccc}{F}_{k+2}^2-F_k^2\hfill & =\hfill & {(F_k+F_{k+1})}^2-F_k^2\hfill \\ \hfill & =\hfill & F_{k+1}^2+2F_k{F}_{k+1}\hfill \\ \hfill & =\hfill & (F_{k+1}^2-F_{k-1}^2)+F_{k-1}^2+2F_k{F}_{k+1}\hfill \\ \hfill & =\hfill & F_{2k}+{(F_{k+1}-F_k)}^2+2F_k{F}_{k+1}\hfill \\ \hfill & =\hfill & F_{2k}+(F_{k+1}^2+F_k^2)\hfill \\ \hfill & =\hfill & F_{2k}+F_{2k+1}\hfill \\ \hfill & =\hfill & F_{2k+2}.\hfill \end{array}$$

So we have shown

– that the identities hold for the first few values of n, and

– that whenever we know the k^th pair of identities hold, the ${(k+1)}^{\mathrm{th}}$ pair also hold.

Hence the two identities hold for all $n\ge 1$. QED

59.

(a) (i) 0, 5, 8, 26, 63,...

(ii) Guess: $F_{n-2}{F}_{n+2}=F_n^2+{(-1)}^{n+1}$.

Proof: By part (i), this identity holds for n = 2, 3,4, 5, 6.

Suppose we have checked it as far as the k^th instance:

$$\begin{array}{c}{F}_{k-2}{F}_{k+2}=F_k^2+{(-1)}^{k+1}.\hfill \end{array}$$

Then the next instance follows using 57, since

$$\begin{array}{ccc}{F}_{(k+1)-2}{F}_{(k+1)+2}\hfill & =\hfill & F_{k-1}{F}_{k+3}\hfill \\ \hfill & =\hfill & F_{k-1}(F_{k+1}+F_{k+2})\hfill \\ \hfill & =\hfill & F_{k-1}{F}_{k+1}+F_{k-1}{F}_{k+2}\hfill \\ \hfill & =\hfill & F_k^2+{(-1)}^k+(F_{k+1}-F_k)(F_k+F_{k+1})\hfill \\ \hfill & =\hfill & {(-1)}^k+F_{k+1}^2.\hfill \end{array}$$

(b) (i) 0,13, 21, 68,...

(ii) Guess:

$$\begin{array}{c}{F}_{n-3}{F}_{n+3}=F_n^2+{(-1)}^{n+3-1}{F}_3^2.\hfill \end{array}$$

This suggests that we should reinterpret our previous guesses, and that the “correction terms” on the RHS:

* in Problem 57(a) should have been written as “${(-1)}^{n+0-1}{F}_0^2$”,

* in Problem 57(a)(ii) should have been written as “${(-1)}^{n+1-1}{F}_1^2$“, and

* in Problem 59(a)(ii) should have been written as “${(-1)}^{n+2-1}{F}_2^2$”.

We leave the proof (or otherwise) of this conjecture as an exercise for the reader.

60.

(i) 10%

(ii) 21% – notice that

$$\begin{array}{c}\left(1.1a\right)\left(1.1b\right)={(1+0.1)}^{2}ab=(1+0.2+0.01)ab=1.21ab.\hfill \end{array}$$

(iii) 0% – notice that

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{1.1a}{1.1b}=\genfrac{}{}{0.1ex}{}{a}{b}.\hfill \end{array}$$

61. If x is doubled in the expression “x”, then the value of the expression doubles.

If y is doubled in the expression $x÷y$, then the value of the expression is halved.

If z is doubled in the expression $x÷(y÷z)$, then the bracket is halved, and the expression is doubled.

Replacing “x, y, z” by “d, e, f” we see that, if the value of f is doubled, the value of the bracket $(d÷(e÷f\left)\right)$ is also doubled.

If we now take $x=b$, $y=c$, $z=(d÷(e÷f\left)\right)$, then, when f is doubled, z is doubled, and the value of $(b÷(c÷(d÷(e÷f\left)\right)\left)\right)$ is doubled.

Hence the value of the whole expression

$$\begin{array}{c}a÷(b÷(c÷(d÷(e÷f\left)\right)\left)\right)\hfill \end{array}$$

is halved.

62.

(a) The fact that one can add the entries in any order depends on the commutative and associative laws of addition. Expressing the subtotal in the second row as $2(1+2+3+4)$ uses the distributive law. And expressing the overall sum

$$\begin{array}{c}(1+2+3+4)+2(1+2+3+4)+3(1+2+3+4)+4(1+2+3+4)\hfill \end{array}$$

as ${(1+2+3+4)}^2$ uses the distributive law again.

(b) (i) $1=1^3$, $8=2^3$, $27=3^3$, $64=4^3$.

(ii) $(4+8+12+16)+(12+8+4)=4T_4+4T_3$. Similarly, the k^th reverse L-shape has sum

$$\begin{array}{c}k\cdot T_k+k\cdot T_{k-1}=\genfrac{}{}{0.1ex}{}{1}{2}{k}^2(k+1)+\genfrac{}{}{0.1ex}{}{1}{2}{k}^2(k-1)=k^3.\hfill \end{array}$$

Hence

$$\begin{array}{c}{C}_n=1^3+2^3+3^3+\cdots +n^3={(1+2+3+\dots +n)}^2=\genfrac{}{}{0.1ex}{}{1}{4}\cdot n^2{(n+1)}^2.\hfill \end{array}$$

63.

(a) The terms are $1\times 2$, $2\times 3$, $3\times 4$, etc,; so the $r^{\mathrm{th}}$ term is r(r+1), and the last term is $(n-1)\left(\right(n-1)+1)$.

The $r^{\mathrm{th}}$ term can be expressed as “$r^2+r$”, so the sum

$$\begin{array}{c}1\times 2+2\times 3+3\times 4+\cdots +r(r+1)+\cdots +(n-1)n\hfill \end{array}$$

can be expressed as

$$\begin{array}{c}(1^2+2^2+3^2+\cdots +{(n-1)}^2)+(1+2+3+\cdots +(n-1\left)\right)=S_{n-1}+T_{n-1}.\hfill \end{array}$$

(b) (i) * $n=2:6=1\times 2\times 3$.

* $n=3:6+18=24=2\times 3\times 4$.

* $n=4:6+18+36=60=3\times 4\times 5$.

Guess: $3(S_{n-1}+T_{n-1})=(n-1)n(n+1).$.

Proof: This is true for $n=\mathrm{1,\; 2,\; 3,\; 4}$.

Suppose we have checked the claim for all values up to

$$\begin{array}{c}3(S_{k-1}+T_{k-1})=(k-1)k(k+1).\hfill \end{array}$$

Then

$$\begin{array}{ccc}3(S_k+T_k)\hfill & =\hfill & 3([S_{k-1}+k^2]+[T_{k-1}+k])\hfill \\ \hfill & =\hfill & (k-1)k(k+1)+3k(k+1)\hfill \\ \hfill & =\hfill & k(k+1)(k+2).\hfill \end{array}$$

Hence our guess is true for all $n\ge 1$.

(ii)

$$\begin{array}{c}{S}_n+T_n=\genfrac{}{}{0.1ex}{}{n(n+1)(n+2)}{3},\hfill \end{array}$$

so

$$\begin{array}{c}{S}_n=\genfrac{}{}{0.1ex}{}{n(n+1)(n+2)}{3}-T_n=\genfrac{}{}{0.1ex}{}{n(n+1)(2n+1)}{6}.\hfill \end{array}$$

64. If one tries to apply the usual algorithms for decimals, then one is likely to get in something of a mess. But if we re-interpret each decimal as a fraction, then things are much easier.

(a) $\genfrac{}{}{0.1ex}{}{5}{9}+\genfrac{}{}{0.1ex}{}{6}{9}=\genfrac{}{}{0.1ex}{}{11}{9}=1.22222\cdots$.

(b) $0.99999\cdots =\genfrac{}{}{0.1ex}{}{9}{9}=1$; $1+\genfrac{}{}{0.1ex}{}{1}{9}=1.11111\cdots$.

(c) $\genfrac{}{}{0.1ex}{}{10}{9}-\genfrac{}{}{0.1ex}{}{2}{9}=\genfrac{}{}{0.1ex}{}{8}{9}=0.88888\cdots$

(d) $\genfrac{}{}{0.1ex}{}{1}{3}\times \genfrac{}{}{0.1ex}{}{2}{3}=\genfrac{}{}{0.1ex}{}{2}{9}=0.22222\cdots$.

(e) $\genfrac{}{}{0.1ex}{}{11}{9}\times \genfrac{}{}{0.1ex}{}{9}{11}=1$.

65.

(a) Such a decimal is by definition equal to the fraction with numerator

$$\begin{array}{c}{b}_n{b}_{n-1}\cdots b_1{b}_0{b}_{-1}{b}_{-2}\cdots b_{-k}\hfill \end{array}$$

(an integer with $n+k+1$ decimal digits) and with and denominator 10^k.

(b) If $\genfrac{}{}{0.1ex}{}{p}{q}$ is equivalent to a fraction with numerator

$$\begin{array}{c}m={b_n{b}_{n-1}\cdots b_1{b}_0}_{base10}\hfill \end{array}$$

and denominator 10^k, then m has decimal representation

$$\begin{array}{c}{b}_n{b}_{n-1}\cdots b_k.b_{k-1}\cdots b_1{b}_0.\hfill \end{array}$$

(c) Parts (a) and (b) show that fractions $\genfrac{}{}{0.1ex}{}{p}{q}$ with $HCF(p,q)=1$, whose decimals terminate are precisely those which are equivalent to fractions having denominator a power of 10: that is, those for which the denominator q is a factor of some integer of the form $10^k=2^k\times 5^k$.

(d) If q does not divide some power of 10, then its decimal does not terminate. Hence, when carrying out the division of p by q we never get remainder 0. So the only possible remainders are 1, 2,... ,q — 1. The first remainder after the decimal point is equal to p (mod q)). In the ensuing q decimal places, there are just q – 1 distinct possible remainders, so some remainder (say r) must occur for the second time by the q^th step, and the outputs (and remainders) thereafter will then be the same as they were the first time that the remainder r occurred.

(e) Suppose d has a decimal with a repeating block of length b starting in the ${(k+1)}^{\mathrm{th}}$ decimal place. (e.g. $d=1234.567890909090909090\cdots$ has $b=2$, $k=4$). Then the infinite decimal tails cancel when we subtract $M=10^{b}d-d$, and the difference M becomes an integer N if we multiply by $10^k:N=M\times 10^k$. Hence $d(10^b-1)10^k=N$, and d is equal to a fraction with denominator $(10^b-1)10^k$.

66.

(a) (i) $\genfrac{}{}{0.1ex}{}{1}{27}$; (ii) $\genfrac{}{}{0.1ex}{}{10}{27}$; (iii) $\genfrac{}{}{0.1ex}{}{19}{27}$

(b) (i) $\genfrac{}{}{0.1ex}{}{a}{9}$; (ii) $\genfrac{}{}{0.1ex}{}{ab}{99}$; (iii) $\genfrac{}{}{0.1ex}{}{abc}{999}$

67.

(a) $0.166666\cdots$ (block length 1); $0.833333\cdots$ (block length 1)

(b) All have block length 6:

$$\begin{array}{c}0.142857142857142857\cdots ;\hfill \\ 0.285714285714285714\cdots ;\hfill \\ 0.428571428571428571\cdots ;\hfill \\ 0.571428571428571428\cdots ;\hfill \\ 0.714285714285714285\cdots ;\hfill \\ 0.857142857142857142\cdots .\hfill \end{array}$$

Note: The repeating blocks are all cyclically related: e.g. the block for $\genfrac{}{}{0.1ex}{}{2}{7}$ is the same as for $\genfrac{}{}{0.1ex}{}{1}{7}$, but starting at “2” instead of at “1”.

(c) All have block length 2:

$$\begin{array}{c}0.090909\cdots ;0.181818\cdots ;0.272727\cdots ;0.363636\cdots ;0.454545\cdots ;\hfill \\ 0.545454\cdots ;0.636363\cdots ;0.727272\cdots ;0.818181\cdots ;0.909090\cdots .\hfill \end{array}$$

Note: The repeating blocks are not all cyclically the same, but fall into five pairs:

– $\genfrac{}{}{0.1ex}{}{1}{11}$ and $\genfrac{}{}{0.1ex}{}{10}{11}$ are cyclically related;

– as are those for $\genfrac{}{}{0.1ex}{}{2}{11}$ and $\genfrac{}{}{0.1ex}{}{9}{11}$;

– and those for $\genfrac{}{}{0.1ex}{}{3}{11}$ and $\genfrac{}{}{0.1ex}{}{8}{11}$;

– and those for $\genfrac{}{}{0.1ex}{}{4}{11}$ and $\genfrac{}{}{0.1ex}{}{7}{11}$;

– and those for $\genfrac{}{}{0.1ex}{}{5}{11}$ and $\genfrac{}{}{0.1ex}{}{6}{11}$.

(d) All have block length 6.

Note: They fall into two families of six, where each family is cyclically related :

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{1}{13}=0.076923076923076923\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{3}{13}=0.230769230769230769\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{4}{13}=0.307692307692307692\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{9}{13}=0.692307692307692307\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{10}{13}=0.769230769230769230\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{12}{13}=0.923076923076923076\cdots ;\hfill \end{array}$$

and

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{2}{13}=0.153846153846153846\cdots ;\hfill \\ \genfrac{}{}{0.1ex}{}{5}{13}=0.384615384615384615\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{6}{13}=0.461538461538461538\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{7}{13}=0.538461538461538461\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{8}{13}=0.615384615384615384\cdots ,\hfill \\ \genfrac{}{}{0.1ex}{}{11}{13}=0.846153846153846153\cdots .\hfill \end{array}$$

68.

(a) Does not recur. (If it did, it would have a recurring block of length b say. But by the time the counting sequence 1, 2, 3,. .. reaches 10^2b the decimal will contain a periodic block of 2b zeros, so the recurring block must consist of 0s, in which case the decimal terminates.)

(b) Does not recur. (Similar to part (a).)

(c) Does not recur. (If it did recur, then $\sqrt{2}$ would be a rational number: see Problems 267, 268, 270.)

69. Claim Decimal fractions have two decimal representations. All other numbers have exactly one decimal representation.

Proof: Every “decimal fraction” (that is, any fraction which can be written with denominator a power of 10) has two representations – one that terminates and one that ends with an endless string of 9s: if the last non-zero digit of the terminating decimal is k, then the second representation of the same number is obtained by changing the “k” to “k — 1” and following it with an endless string of 9s.

Consider an unknown number with two different decimal representations $\alpha$ and $\beta$. Since they are “different”, $\alpha$ and $\beta$ must differ in at least one position. Suppose the first, or left-most, position in which they differ is that in the $k^{\mathrm{th}}$ decimal place (corresponding to $10^{-k}$), and that the two digits in that position are $a_k$ (for $\alpha$) and $b_k$ (for $\beta$).

We may suppose that $a_k<b_k$. Then $b_k=a_k+1$ (otherwise $b_k-a_k>1$, and $\beta -\alpha >10^{-k}$, so $\alpha \ne \beta$).

Moreover, since $\beta$ is not larger than $\alpha$, the digits following $b_k$ must all be equal to 0, and the digits following $a_k$ must all be equal to 9. QED

70. In case (d), A only has to choose a recurring block (such as “$55555\cdots$“, or “$090909\cdots$“, or “$123123123\cdots$“) for his/her positions – no matter where they are. B’s control terminates at some stage, after which A’s recurring block guarantees that the resulting number is rational.

The other parts all offer a guaranteed strategy for B. Let the positions chosen by B be numbered

$$\begin{array}{c}{n}_1,n_2,n_3,n_4,\dots ,n_k,\dots .\hfill \end{array}$$

Now exploit the fact that the positive rationals are countable – that is, can be included in a single list. To see this we can use Cantor’s (1845-1918) diagonal enumeration

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{0}{1};\genfrac{}{}{0.1ex}{}{1}{1};\genfrac{}{}{0.1ex}{}{1}{2},\genfrac{}{}{0.1ex}{}{2}{1};\genfrac{}{}{0.1ex}{}{1}{3},\genfrac{}{}{0.1ex}{}{3}{1};\genfrac{}{}{0.1ex}{}{1}{4},\genfrac{}{}{0.1ex}{}{2}{3},\genfrac{}{}{0.1ex}{}{3}{2},\genfrac{}{}{0.1ex}{}{4}{1};\genfrac{}{}{0.1ex}{}{1}{5},\genfrac{}{}{0.1ex}{}{5}{1};\genfrac{}{}{0.1ex}{}{1}{6},\genfrac{}{}{0.1ex}{}{2}{5},\genfrac{}{}{0.1ex}{}{3}{4},\genfrac{}{}{0.1ex}{}{4}{3},\genfrac{}{}{0.1ex}{}{5}{2},\genfrac{}{}{0.1ex}{}{6}{1};\genfrac{}{}{0.1ex}{}{1}{7},\dots ,\hfill \end{array}$$

which lists all rationals $\genfrac{}{}{0.1ex}{}{p}{q}$ with $HCF(p,q)=1$

• first those with $p+q=1$,
• then those with $p+q=2$,
• then those with $p+q=3$,

and so on.

All B needs to do is to make sure that the resulting decimal is not the decimal of any number in this list, and s/he can do this by choosing a digit in the $n_k^{\mathrm{th}}$ position which is different from the digit which the k^th rational in the above list has in that position. The resulting real number is then different from every number in the list – and hence must be irrational.

71.

(a) 101 010 (in each column (i) $0+0=0$, (ii) $1+0=1$, (iii) $1+1=$ “0 and carry 1”).

(b) (i) 1010100 (ii) 101010 (iii) 101010

(c) 2

Note: Trying to do this should make it clear how easily we confound “the fourteenth positive integer” with its familiar base 10 representation. It takes time and effort to learn to see “14_base 10” as “2 × 7”, and “21_base 10” as 3 × 7, and hence to spot the common multiple “42_{base 10}“. In base 2 the same numbers evoke no such familiar echoes.

72. Let $N={(a_k{a}_{k-1}\cdots a_1{a}_0)}_{\mathrm{base}2}$.

(i) N is divisible by 2 precisely when the units digit $a_0$ is equal to 0.

(ii) N is divisible by 3 precisely when the alternating sum

$$“a_0-a_1+a_2-a_3+\cdots \pm a_k”$$

is divisible by 3.

Proof

$$\begin{array}{ccc}N\hfill & =\hfill & {(a_k{a}_{k-1}\cdots a_1{a}_0)}_{base2}\hfill \\ \hfill & =\hfill & 2^k{a}_k+2^{k-1}{a}_{k-1}+\cdots +2a_1+a_0.\hfill \end{array}$$

For each odd suffix m, increase the coefficient 2m by 1: then

$$\begin{array}{c}{2}^m+1=(2+1)(2^{m-1}-2^{m-2}+\cdots -2+1)\hfill \end{array}$$

has 3 as a factor.

For each even suffix $m=2n$, decrease the coefficient by 1: then

$$\begin{array}{c}{2}^{2n}-1=(2^2-1)(2^{2n-2}+2^{2n-4}+\cdots +2^2+1)\hfill \end{array}$$

has 3 as a factor.

Hence

$$\begin{array}{ccc}N\hfill & =\hfill & 2^k{a}_k+2^{k-1}{a}_{k-1}+\cdots +2a_1+a_0\hfill \\ \hfill & =\hfill & \left(\text{multiple of}3\right)+(a_0-a_1+a_2-\cdots \pm a_k).\hfill \end{array}$$

(iii) N is divisible by 4 precisely when the last two digits a₁ and a₀ are both equal to 0.

(iv) N is divisible by 5 precisely when the alternating sum

$$\begin{array}{c}“a_1{a}_0\text{”}-“a_3{a}_2\text{”}+“a_5{a}_4\text{”}-\cdots \hfill \end{array}$$

is divisible by 5.

Proof:

$$\begin{array}{ccc}N\hfill & =\hfill & {(a_k{a}_{k-1}\cdots a_1{a}_0)}_{base2}\hfill \\ \hfill & =\hfill & 2^k{a}_k+2^{k-1}{a}_{k-1}+\cdots +2a_1+a_0\hfill \\ \hfill & =\hfill & (2a_1+a_0)+2^2(2a_3+a_2)+2^4(2a_5+a_4)+\cdots \hfill \\ \hfill & =\hfill & (2^2+1)(2a_3+a_2)+(2^4-1)(2a_5+a_4)+\cdots \hfill \\ \hfill & \hfill & +[(2a_1+a_0)-(2a_3+a_2)+(2a_5+a_4)-\cdots ]\hfill \\ \hfill & =\hfill & \left(\text{a multiple of}5\right)+[“a_1{a}_0\text{”}-“a_3{a}_2\text{”}+“a_5{a}_4\text{”}-\cdots ].\hfill \end{array}$$

73.

(a) To weigh an object with weight 1, we must have w₀ = 1.

To weigh an object with weight 2, we must have w₁ = 2. We can then weigh any object of weight 3, but not one of weight 4.

(i) Now assume each positive weight w can be balanced in exactly one way. Then we cannot have w₂ = 3, so w₂ = 4.

Suppose that, continuing in this way, we have deduced that $w_i=2^i$ for each $i=\mathrm{0,1}\mathrm{,2},\dots ,k$.

Then the binary numeral system reveals precisely that every weight w from 0 up to

$$\begin{array}{c}{2}^{k+1}-1=1+2+2^2+\dots +2^k\hfill \end{array}$$

can be uniquely represented, but $2^{k+1}$ cannot. Hence

$$w_{k+1}=2^{k+1}.$$

The result follows by induction.

(ii) If the representation of each integer is not unique, then the sequence

$$w_0,w_1,w_2,\dots$$

need not include the powers of 2. For example, it could begin

$$1,2,3,5,\dots$$

(b) If each integer w is to be weighed in this way, then w has to be represented in the form

$$\begin{array}{c}w=a_1{w}_1+a_2{w}_2+a_3{w}_3+\cdots \hfill \end{array}$$

where each coefficient $a_i=0$ (if the weight $w_i$ is not used to weigh w), or = 1 (if the weight $w_i$ is used to balance w), or = −1 (if the weight $w_i$ is used to supplement w).

If each representation is to be unique, then one can prove as in (a)(i) that the sequence of weights must be the successive powers of 3.

74. Write m in “base 2”:

$$\begin{array}{c}m={(a_{n-1}\cdots a_1{a}_0)}_{\text{base}2},\hfill \end{array}$$

where each $a_k=0$ or 1. Then

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{m}{2^n}=\genfrac{}{}{0.1ex}{}{a_0}{2^n}+\genfrac{}{}{0.1ex}{}{a_1}{2^{n-1}}+\cdots +\genfrac{}{}{0.1ex}{}{a_{n-1}}{2}.\hfill \end{array}$$

That is,

$$\begin{array}{c}\genfrac{}{}{0.1ex}{}{m}{2^n}={(0.a_{n-1}\cdots a_1{a}_0)}_{\text{base}2}.\hfill \end{array}$$

75. We give an example, starting with $N=110111001_{\text{base}2}$.

Write N, and pair off the digits, starting at the units digit.

1 || 10 || 11 || 10 || 01

The left-most digit stands for 2⁸, so the square root is at least 2⁴ (and less than 2⁵). Hence the required square root has five digits (one for each “pair” of digits of N), and starts with a 1.

Root 1 || ? || ? || ? || ?

[We can also see that the final units digit will have to be a “1”. But this is not the time to add such information.]

Let x = 10 000, and subtract x² = 100 000 000 from N:

1 00 00 00 00
|| 10 || 11 || 10 || 01

This residue has to be equal to “$2xy+y^2$”. However, as with long division, our immediate interest is in determining the next digit of our “partial square root”.

If the next digit is a 1 (contributing $2^3$), then $2xy\ge 2^8$, which would spill over and change the digit we have already determined. Hence the next digit is a 0.

Root 1 || 0 || ? || ? || ?

So we can again let x = 10 000 giving the same remainder, which has to be equal to “$2xy+y^2$“, but this time $y<2^3$ has at most three digits.

The remainder

|| 10 || 11 || 10 || 01

is greater than $2^7$, so $y\ge 2^2$ and the next digit must be a “1”.

Root 1 || 0 || 1 || ? || ?

Now let $x=10100$, and subtract $x^2=110010000$ from N, leaving

|| 10 || 0 || 01

This residue has to equal $2xy+y^2$, with $x=10100$.

If the next digit in the square root is 1, then $2xy⩾2^6>101001=2xy+y^2$.

Hence the next digit is 0, and the last digit is then 1.

Hence the required square root is equal to:

Root 1 || 0 || 1 || 0 || 1

76.

(b)(i) The fact that

$$n_1=p_1+1$$

says that

“$n_1$ is equal to a multiple of $p_1$ with remainder = 1”.

(c)(i) The fact that

$$n_2=p_1\times p_2+1$$

says that

“$n_2$ is equal to a multiple of $p_1$ with remainder = 1”.

and that

“$n_2$ is equal to a multiple of $p_2$ with remainder = 1”.

Hence neither p₁ nor p₂ are factors of n₂.

(d) The fact that

$$\begin{array}{c}{n}_k=p_1\times p_2\times \cdots \times p_k+1\hfill \end{array}$$

says that

“$n_k$ is equal to a multiple of $p_i$ with remainder = 1”

for each suffix i, $1\le i\le k$. Hence none of the primes $p_1,p_2,p_3,\dots ,p_k$ is a factor of $n_k$.

So the smallest prime factor of n_k always gives us a new prime $p_{k+1}$.

(e) If we start with $p_1=2$, then $n_1=p_1+1=3$, so $p_2=3$.

Then $n_2=p_1\times p_2+1=7$, so $p_3=7$.

Then $n_3=p_1\times p_2\times p_3+1=43$, so $p_4=43$.

Then $n_4=p_1\times p_2\times p_3\times p_4+1=1807=13\times 139$, so $p_5=13$.

77.

(a) We write $\lceil x\rceil$ for the “first integer $\ge x$”. Then

$$\begin{array}{ccc}\pi \left(\lceil e^1\rceil \right)\hfill & =\hfill & \pi \left(3\right)=2;\hfill \\ \pi \left(\lceil e^2\rceil \right)\hfill & =\hfill & \pi \left(8\right)=4;\hfill \\ \pi \left(\lceil e^3\rceil \right)\hfill & =\hfill & \pi \left(21\right)=8;\hfill \\ \pi \left(\lceil e^4\rceil \right)\hfill & =\hfill & \pi \left(55\right)=16;\hfill \\ \pi \left(\lceil e^5\rceil \right)\hfill & =\hfill & \pi \left(149\right)=35;\hfill \\ \pi \left(\lceil e^6\rceil \right)\hfill & =\hfill & \pi \left(404\right)=79;\hfill \\ \pi \left(\lceil e^7\rceil \right)\hfill & =\hfill & \pi \left(1097\right)=184;\hfill \\ \pi \left(\lceil e^8\rceil \right)\hfill & =\hfill & \pi \left(2981\right)=429;\hfill \\ \pi \left(\lceil e^9\rceil \right)\hfill & =\hfill & \pi \left(8104\right)=1019.\hfill \end{array}$$

(b) The initial “doubling” is an accident of small numbers, which soon turns into “slightly more than doubling”.

The observation that should (eventually) jump out at you concerns the ratio $e^N:\pi \left(N\right)$, which seems to be surprisingly close to N − 1. This suggests the possible

Conjecture: $\pi \left(x\right)\sim \genfrac{}{}{0.1ex}{}{x}{\ln \left(x\right)-1}$ (where $\ln \left(x\right)={\log }_e\left(x\right)$).