M 2003  NUMBERS AND SETS – EXAMPLES SHEET 2  W. T. G.

1. Prove by induction that the following two statements are true for every positive integer n.

(i) The number 2^{n+2} + 3^{2n+1} is a multiple of 7. (ii) 1^{3} + 3^{3} + 5^{3} + … + (2n − 1)^{3} = n^{2}(2n^{2} − 1) .

2. Suppose that you have a 2^{n} × 2^{n} grid of squares (if n = 3 then you have a chessboard) and you remove one square. Prove that, wherever the removed square is, the remaining squares can be tiled with L-shaped tiles - that is, tiles consisting of three squares that form a 2 × 2 grid with one square removed.

3. By considering the equation (1 − 1)^{n} = 0, give another proof that exactly half the subsets of {1, 2, …, n} have even size.

4. Prove that

\binom{k}{k} + \binom{k + 1}{k} + … + \binom{n + k − 1}{k} = \binom{n + k}{k + 1}

for any n > k. [Hint: for each set of size k + 1 consider its largest element.]

5. Prove that

\binom{n}{0}^{2} + \binom{n}{1}^{2} + \binom{n}{2}^{2} + … + \binom{n}{n}^{2} = \binom{2n}{n} .

[Hint: \binom{n}{k} = \binom{n}{n−k}.]

6. There are four primes between 0 and 10 and four between 10 and 20. Does it ever happen again that there are four primes between two consecutive multiples of 10?

7. Is n^{2} + n + 41 prime for all positive integers n?

8. Does there exist a block of 100 consecutive positive integers, none of which is prime?

9. Is there a power of 2 that begins with a 7?

10. Write down carefully (while not looking at your notes) a proof that there are infinitely many primes. By considering numbers of the form 4p_{1}p_{2} … p_{k} − 1, prove that there are infinitely many primes of the form 4n−1. What would go wrong if we tried a similar proof to show that there are infinitely many primes of the form 4n + 1?

11. Translate the following sentence into a short English one, and write down its negation in symbolic form. (For this question the letters m, n, a, b should be understood as ranging over all positive integers - for instance, ∀m really means ∀m ∈ ℕ.)

∀m ∃n ∀a ∀b (n ≥ m) ∧ [(a = 1) ∨ (b = 1) ∨ ((ab ≠ n) ∧ (ab + 2 ≠ n))]

12. Find the highest common factor of 12345 and 54321.

13. Find integers x and y with 76x + 45y = 1. Do there exist integers x and y with 1992x + 1752y = 12?

14. Prove that if a is coprime to b and also to c then it is coprime to bc. Give two proofs: one based on Bezout’s theorem and one based on prime factorisation.

15. Is it true that for all positive integers a, b, c, d we have (a, b)(c, d) = (ac, bd)?

16. Show that a positive integer n is a multiple of 9 if and only if the sum of its digits is a multiple of 9. Find a rule for when a number is a multiple of 11 and prove that your rule works.

17. The Fibonacci numbers F_{1}, F_{2}, F_{3}, … are defined by: F_{1} = F_{2} = 1, and F_{n} = F_{n−1} + F_{n−2} for all n > 2 (so eg. F_{3} = 2, F_{4} = 3, F_{5} = 5). Is F_{2004} even or odd? Is it a multiple of 3?

18. Suppose that we have some positive integers (not necessarily distinct) whose sum is 100. How large can their product be?

19. We are given a binary operation ∗ on the positive integers, satisfying

(i) 1 ∗ n = n + 1 for all n (ii) m ∗ 1 = (m − 1) ∗ 2 for all m > 1 (iii) m ∗ n = (m − 1) ∗ (m ∗ (n − 1)) for all m, n > 1. Find the value of 5 ∗ 5.

20. The repeat of a positive integer is obtained by writing it twice in a row (so for example the repeat of 254 is 254254). Is there a positive integer whose repeat is a perfect square?