(i) Show that \(\sum_{r=0}^{n} \binom{n}{r} = 2^n\) for each positive integer \(n\), where \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\). (ii) Show that, for all positive integers \(r\) and \(n\), \(\sum_{s=0}^{n} \binom{r+s}{r} = \binom{n+r+1}{r+1}\).
(i) Prove that 24 is the largest integer divisible by the product of all integers less than its square root. (ii) Show that in any set of \(n + 1\) numbers chosen from \(1, 2, ..., 2n\), there is always a pair of different numbers, one of which divides the other.
Let \(a\) be a positive integer, and write \(r = \sqrt{a} + \sqrt{(a+1)}\). Show, for each positive integer \(n\), that \(a_n = \frac{1}{4}(r^{2n} + r^{-2n} - 2)\) is an integer, and that \(r^n = \sqrt{a_n} + \sqrt{(a_n + 1)}\). [Positive square roots are to be taken throughout.]
Show that, if \(p = \cos A + \cos B\) and \(q = \sin A + \sin B\), then \(\sin(A + B) = \frac{2pq}{p^2+q^2}\) and \(\cos(A + B) = \frac{p^2-q^2}{p^2+q^2}\). Hence, or otherwise, find the general solution of the equation \(\frac{\sin\theta-\cos\theta}{\sin\theta+\cos\theta} = \frac{\sqrt{2}-2\sin\theta}{\sqrt{2}+2\cos\theta}\).
A theorem in combinatorial theory may be stated as follows: Let \(G_1, G_2, ..., G_n\) be \(n\) girls and \(B_1, B_2, ..., B_n\) \(n\) boys. In order for all boys to be able to choose as dancing partners girls with whom they are friendly, it is necessary and sufficient that, for each subset \(S\) of boys, the number of girls friendly with at least one boy in \(S\) is at least equal to the number of boys in \(S\). Prove the necessity of the condition on subsets of boys, and establish its sufficiency for \(n \leq 3\). Find the number of ways in which dancing partners may be chosen so that only friendly couples dance together, in the following situation with \(n = 5\): \begin{align*} G_1 \text{ is friendly only with } B_1, B_2, B_3 \text{ and } B_4\\ G_2 \text{ is friendly only with } B_1, B_2 \text{ and } B_5\\ G_3 \text{ is friendly only with } B_4 \text{ and } B_5\\ G_4 \text{ is friendly only with } B_1, B_2 \text{ and } B_4 \text{, and}\\ G_5 \text{ is friendly only with } B_3 \end{align*}
Let \(p\) be a prime number, and let \(C\) denote the set of all complex \(p'\)th-power roots of unity (that is, the set of all \(\exp(2\pi in/p^r)\) with \(n\) and \(r\) positive integers). Show that \(C\) is a commutative group with respect to multiplication of complex numbers. Identify all the subgroups of \(C\). [It may be helpful to use the fact that, for integers \(m\) and \(n\), with no common factors other than \(\pm 1\), there are (not necessarily positive) integers \(a\) and \(b\) such that \(am + bn = 1\).]
(i) Show that every group all of whose non-identity elements have order 2 is commutative. (ii) Let \(G\) be the set of \(3 \times 3\) matrices of the form \(\begin{pmatrix} 1 & x & y \\ 0 & 1 & z \\ 0 & 0 & 1 \end{pmatrix}\) with entries integers modulo 3. Show that, with respect to matrix multiplication, \(G\) is a non-commutative group all of whose non-identity elements have order 3. [The order of an element \(x\) of a group is the least integer \(n \geq 1\) such that \(x^n\) is the identity element. You may assume that \((AB)C = A(BC)\) for \(3 \times 3\) matrices \(A, B\) and \(C\).]
\(ABC\) is a triangle, and \(BCA', CAB', ABC'\) are equilateral triangles; \(A, A'\) being on opposite sides of \(BC\), \(B, B'\) on opposite sides of \(CA\) and \(C, C'\) on opposite sides of \(AB\). Prove that the lines \(AA', BB', CC'\) are of equal length and meet in a point.
\(ABCD\) is a square, whose opposite vertices \(A,C\) lie, respectively, on the lines \(y = mx, y = -mx\). If the equation of \(AC\) is \(\frac{x}{a} + \frac{y}{b} = 1\), find the coordinates of \(B\) and \(D\). Hence, or otherwise, show that if \(AC\) varies in such a way that \(B\) lies on the line \(px + qy + r = 0\), then the locus of \(D\) is a straight line, and find its equation.
Show that the four points \((at_i^2, 2at_i)\), for \(i = 1,2,3,4\), of the parabola \(y^2 = 4ax\) are concyclic if, and only if, \(t_1 + t_2 + t_3 + t_4 = 0\). \(PP'\) is a chord of a parabola perpendicular to the axis. A circle touches the parabola in \(P\) and meets it again in \(Q\) and \(R\). Show that \(QR\) is parallel to the tangent at \(P'\).