KMB, 04/11/99

M1F Foundations of Analysis—Problem Sheet 5

This is assessed coursework (unless you’re JMC) and it’s due in on Friday 12th November.

1) Prove the following (using induction might be a good idea):

a) If n ≥ 1 is an integer, then the integer 2^{4n−1} ends in an 8.

b) If x ≥ 2 is a real number and n ≥ 1 is an integer, then x^{n} ≥ nx.

c) If n ≥ 3 is an integer, then 5^{n} > 4^{n} + 3^{n} + 2^{n}.

d) The sum of the first 1999 cubes (1 + 8 + 27 + … + 1999^{3} ) is a perfect square.

(Hint for (d): try working out, by experimentation, a formula for the sum of the first n cubes, valid for any n.)

2) The Lucas sequence (L_{n})_{n≥1} is defined as follows.

L_{1} = 1, L_{2} = 3,

and for n ≥ 3,

L_{n} = L_{n−1} + L_{n−2}.

So the Lucas sequence begins 1, 3, 4, 7, 11. . .. Let α and β be the two roots of X^{2} − X − 1 = 0. Prove that L_{n} = α^{n} + β^{n} for all integers n ≥ 1 in the following way:

(i) Show that if k ≥ 3 then α^{k} = α^{k−1} + α^{k−2}, and that β^{k} = β^{k−1} + β^{k−2}. (ii) Check that L_{1} = α + β and L_{2} = α^{2} + β^{2}. (iii) Show that if P (n) is the statement “L_{n} = α^{n} + β^{n}”, then for all k ≥ 3,

P (k − 2) and P (k − 1) together imply P (k).

(iv) Now explain how to deduce the general result.

3) The Fibonacci sequence (F_{n})_{n≥1} is defined by

F_{1} = F_{2} = 1,

and for n ≥ 3,

F_{n} = F_{n+1} + F_{n−2}.

So the sequence begins 1, 1, 2, 3, 5, 8…. Is F_{1999} odd or even? (Hint: Work out whether or not the first 10 or so terms are odd or even.

Do you see a pattern? Motivated by this, for n ≥ 1, make up a statement P (n) which is about all three of the numbers F_{3n−2}, F_{3n−1} and F_{3n}, and prove it by induction.)

(Another hint: you’ll get 0 marks for just guessing.)

4) When I was a student, Chicken McNuggets used to be sold in boxes of 6 or 9, and also in a “family pack” containing 20. A friend of mine once asked me what was the largest number of Chicken McNuggets that it was impossible to buy. For example, it was possible to buy 12 Chicken McNuggets (= 6 + 6) or 15 (= 6 + 9) but it was not possible to buy 13 because you couldn’t buy single McNuggets or anything like that. So what was the answer to my friend’s question?

(Remark: this is tricky, and marks will be given for partial results. Congratulations if you manage to solve it completely. You might want to try experimenting with smaller numbers first if you want to get the hang of this question. At some stage you might want to try and prove that above some bound N, you can buy any number of McNuggets. You might want to use (slightly modified) strong induction to prove this.)