The sequence of real numbers \(x_n\) satisfies \[x_{n+1} = x_n + x_{n-1}, \quad x_0 = a, \quad x_1 = b, \quad a \neq 0, \quad b \neq 0.\] Find a solution of the form \(x_n = A\lambda^n + B\mu^n\), and hence prove that as \(n \to \infty\) the ratio of successive terms in the sequence tends to a certain number (to be found), unless the ratio \(a:b\) takes a certain value. What happens then?
(i) Guess an expression for \[\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right) \cdots \left(1-\frac{1}{n^2}\right),\] valid for \(n \geq 2\), and prove your guess by mathematical induction. (ii) Show that \[\sum_{r=0}^{k} (-1)^r \binom{n}{r} = (-1)^k \binom{n-1}{k},\] for all \(k = 0, 1, \ldots, n-1\), where \(\binom{n}{r}\) is the usual binomial coefficient.
Let \(p(x)\) be a polynomial of degree 4, with real coefficients, and satisfying the property that, for all rational numbers \(\alpha\), \(p(\alpha)\) is a rational number. Prove that \(p(x)\) has rational coefficients. If \(q(x)\) is a polynomial with rational coefficients, and \(q(n)\) is an integer for every integer \(n\), does it follow that \(q(x)\) has integer coefficients? Give either a proof or a counter-example. [A rational number is a number of the form \(p/q\) where \(p\), \(q\) are integers, \(q \neq 0\).]
A \(3 \times 3\) floor-tile comprises nine unit squares. The small squares are to be coloured red, white or blue in such a way that two squares with an edge in common must be of different colours. Two tiles are considered to have the same colouring if one can be rotated into the other. How many differently coloured floor-tiles can be produced? [Hint: consider the number of ways to colour the cross obtained by deleting the four corner squares.]
Prove that if \(p\) is a positive prime number and if \(k = 1, \ldots, p - 1\), then the binomial coefficient \(\binom{p}{k}\) is divisible by \(p\). Deduce, by induction or otherwise, that \(n^p - n\) is divisible by \(p\), for all positive integers \(n\) and prime numbers \(p\).
If \(p\) is a positive integer and \(n\) an integer in the range 1 to \(p\), describe the positions in the Argand diagram of the \(p\) points \[\left(\cos\frac{2n\pi}{p+1} + i \sin\frac{2n\pi}{p+1}\right)^m, \quad m=1,2,\ldots,p.\] Hence or otherwise prove that \[\sum_{m=1}^{p} \cos\frac{2nm\pi}{p+1} = -1\] for any \(n\) in the range specified.
Let \(G\) be the group of symmetries of the equilateral triangle \(ABC\). Express all the symmetries of the triangle under reflection and rotation by the permutations which they induce on the letters \(A\), \(B\), \(C\). Let \(R\) in \(G\) correspond to a rotation of the triangle by \(\frac{2\pi}{3}\), and \(M\) in \(G\) to a reflection of the triangle about an altitude. Show that all elements of \(G\) may be expressed as \(R^i\) or \(R^i M\) for \(i = 0, 1, 2\). Given a subgroup \(H\) of \(G\) and an element \(g\) of \(G\), we define \(gH\) to be the set \(\{gh : h \in H\}\); similarly \(Hg = \{hg : h \in H\}\). \(H\) is then said to be a normal subgroup if \(gH = Hg\) for all \(g\) in \(G\). Show that the subgroup \(\{E, R, R^2\}\), where \(E\) is the identity permutation of \(G\), is normal. Find a subgroup of \(G\) which is not normal, and justify your answer.
A square matrix \(B\) has an inverse \(B^{-1}\); \(B\) satisfies \[BX = \lambda X\] for some scalar \(\lambda\) and non-zero column vector \(X\). Show that the inverse of \(B\) satisfies \[B^{-1}X = \lambda^{-1}X.\] For \(B = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}\) show there are exactly two values \(\lambda_1\), \(\lambda_2\) such that (*) has a solution for \(X\), and find corresponding normalized vectors \(X_1\), \(X_2\) (a column vector \(\begin{pmatrix} x \\ y \end{pmatrix}\) is normalized if \(x^2 + y^2 = 1\)). Show that \(\lambda_1 X_1 X_1^T + \lambda_2 X_2 X_2^T = B\), where \(X_i^T\) is the row vector transpose of \(X_i\), \(i = 1, 2\). Assuming a similar representation for \(B^{-1}\), determine \(B^{-1}\).
Five points \(A\), \(B\), \(C\), \(D\) and \(E\) lie in that order on a circle. The lengths \(AB\) and \(DE\) are equal, and the lengths \(BC\) and \(CD\) are equal. The tangents to the circle at \(C\) and \(A\) meet at \(F\), and the line \(AB\) is extended to meet \(FC\) at \(G\). Prove that triangles \(AFG\) and \(EBA\) are similar.
Let a convex quadrilateral \(Q\) have sides \(a\), \(b\), \(c\), \(d\). Let \(a\) and \(b\) include the angle \(\alpha\), \(c\) and \(d\) the angle \(\beta\), and define \(\gamma = \alpha + \beta\). If \(A\) denotes the area of \(Q\), show that \begin{align} \text{(i)} \quad & 2A = ab\sin\alpha + cd\sin\beta,\\ \text{(ii)} \quad & a^2 + b^2 - 2ab\cos\alpha = c^2 + d^2 - 2cd\cos\beta, \end{align} and deduce that \begin{align} \text{(iii)} \quad & 16A^2+(a^2+b^2-c^2-d^2)^2 = 4(ab+cd)^2-16abcd\cos^2(\tfrac{1}{2}\gamma),\\ \text{(iv)} \quad & A^2 = (s-a)(s-b)(s-c)(s-d) - abcd\cos^2(\tfrac{1}{2}\gamma), \end{align} where \(2s = a+b+c+d\). By using the inequality relating geometric and arithmetic means, deduce that, among all quadrilaterals of given perimeter, the square has the greatest area. [Standard formulae for triangles may be quoted without proof.]