Problems

---

Solution: Since the common difference is \(a_2 - a_1\) we can find that \(a_n = a_1 + (n-1)(a_2-a_1)\), then \begin{align*} && a_1 &&+&& a_2 &&+&& \cdots &&+&& (a_1 + (n-2)(a_2 - a_1) && + && (a_1 + (n-1) (a_2 - a_1)) \\ + && (a_1 + (n-1) (a_2 - a_1))&&+&& (a_1 + (n-2)(a_2 - a_1)&&+&& \cdots &&+&& a_2 && + && a_1 \\ \hline \\ = && 2a_1 + (n-1)(a_2 - a_1) && + && 2a_1 + (n-1)(a_2 - a_1) && + && \cdots && + 2a_1 + (n-1)(a_2 - a_1) && + 2a_1 + (n-1)(a_2 - a_1) \\ = && n(2a_1 + (n-1) (a_2 - a_1)) \end{align*} Therefore the sum is \(a_1 n + \frac{n(n-1)}{2} (a_2 - a_1)\). Since \(b_n - b_1 = (b_n - b_{n-1}) + (b_{n-1} - b_{n-2}) + \cdots (b_2 - b_1)\), \(b_n - b_1 = a_1 (n-1) + \frac{(n-1)(n-2)}{2}(a_2 - a_1) = (b_2-b_1)(n-1) + \frac{(n-1)(n-2)}{2}(b_3 -2b_2 +b_1)\). So \(b_n = b_1 + (b_2 - b_1)(n-1) + \frac{(n-1)(n-2)}{2} (b_3 - 2b_2 + b_1)\). In particular \begin{align*} \sum_{i=1}^n b_i &= \sum_{i=1}^n \l b_1 + (b_2 - b_1)(n-1) + \frac{(n-1)(n-2)}{2} (b_3 - 2b_2 + b_1)\r \\ &= nb_1 + (b_2-b_1) \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)}{6}(b_3-2b_2+b_1) \end{align*} Let \(b_2 - b_1 = x\) and \(b_3 - 2b_2+b_1 = y\), then \begin{align*} b_4 - b_2 &= d &= &2x + 3y \\ b_6-b_4 &= 2d &=& 2x +(10-3)y \\ &&=&2x + 7y \\ 220-b_6&=6d &=& 220-(1 + 5x + 10y) \\ \end{align*} \begin{align*} && 4x + 6y &= 2x + 7y \\ && 6x+21y &= 219-5x-10y \\ \Rightarrow && 2x - y &= 0 \\ && 11x + 31y &= 219 \\ \Rightarrow && x &= 3 \\ && y &= 6 \end{align*} Therefore the final sum is \begin{align*} n + 3 \frac{n(n-1)}{2} + 6 \frac{n(n-1)(n-2)}{6} &= n^3-\frac32n^2+\frac32n \end{align*}

---

Solution: With \(n=1\) line, the plane is divided in half. With \(n=2\) lines the plane is divided into four pieces. (Each of the previous pieces are split in half) With \(n=3\) lines the plane is divided into up to \(7\) pieces. (The new line crosses two lines in two places dividing \(3\) regions into \(2\), thus increasing the number of regions by \(3\)). With \(n=4\) lines the plane is divided into \(11\) pieces. (The new line crosses three lines in three places doubling the number of regions of \(4\) places). Claim: With \(n\) lines the plane is divided into \(\frac12(n^2+n+2)\) regions. Proof: (By induction) (Base case) When \(n=1\) clearly the line is divided into \(2\) regions, and \(\frac12 (1^2 + 1^2 + 2) = 2\) so the base case is true. (Inductive step) Suppose our formula is true for \(n=k\), so we have placed \(k\) lines in general position and divided the plane into \(\frac12(k^2+k+2)\) regions. When we place a new line it will meet those \(k\) lines in \(k\) places (since no lines are parallel) and there will be k+1 regions the line will run through (since no three lines meet at a point). Each of those \(k+1\) regios is now split in half, so there are \(k+1\) "new regions". Therefore there are now \(\frac12(k^2+k+2)+(k+1) = \frac12(k^2+k+1+2k+2) = \frac12 ((k+1)^2+(k+1)+1)\) regions, ie our hypothesis is true for \(n=k+1\). (Conclusion) Therefore since our statement is true for \(n=1\) and since if it is true for some \(n=k\) it is true for \(n=k+1\) by the principle of mathematical induction it is true for all \(n \geq 1\) Proof: (Alternative). There are \(\binom{n}{2}\) places where the lines meet. Each intersection is the most extreme point (say lowest) for one region (if two are tied, rotate by a very small amount) so this is a unique mapping. There will be \(n+1\) regions which are infinite and don't have a most extreme point, hence \(\binom{n}{2} + n+1 = \frac12(n^2-n)+n+1 = \frac12(n^2+n+2)\)

---

Solution: \begin{align*} \sum_{r = 0}^n \cos (\alpha + 2r \beta) &= \sum_{r = 0}^n \textrm{Re} \left ( \exp(i(\alpha + 2r \beta)) \right) \\ &= \textrm{Re} \left (\sum_{r = 0}^n \exp(i(\alpha + 2r \beta)) \right) \\ &= \textrm{Re} \left (e^{i \alpha} \sum_{r = 0}^n \ (e^{i 2 \beta})^r\right) \\ &= \textrm{Re} \left (e^{i \alpha} \frac{e^{2(n+1)\beta i}-1}{e^{2\beta i}-1} \right) \\ &= \textrm{Re} \left (e^{i \alpha} \frac{e^{(n+1)\beta i} (e^{(n+1)\beta i}-e^{-(n+1)\beta i})}{e^{\beta i}(e^{\beta i}-e^{-\beta i})} \right) \\ &= \textrm{Re} \left (\frac{e^{i \alpha} e^{(n+1)\beta i}}{e^{\beta i}} \frac{\sin (n+1) \beta}{\sin \beta} \right) \\ &= \textrm{Re} \left ( e^{i(\alpha + n \beta)}\frac{\sin (n+1) \beta}{\sin \beta} \right) \\ &= \frac{\cos (\alpha + n \beta)\sin (n+1) \beta}{\sin \beta} \end{align*} \begin{align*} \sum_{r = 0}^n \binom{n}{r} \cos (\alpha + 2r \beta) &= \sum_{r = 0}^n \textrm{Re} \left ( \binom{n}{r}\exp(i(\alpha + 2r \beta)) \right) \\ &= \textrm{Re} \left (\sum_{r = 0}^n \binom{n}{r} \exp(i(\alpha + 2r \beta)) \right) \\ &= \textrm{Re} \left (e^{i \alpha}(e^{2\beta i}+1)^n \right) \\ &= \textrm{Re} \left (e^{i \alpha}e^{n\beta i}(e^{\beta i}+e^{-\beta i})^n \right) \\ &= \textrm{Re} \left (e^{i \alpha}e^{n\beta i}2^n \cos^n \beta \right) \\ &= 2^n \cos(\alpha + n \beta) \cos ^n \beta \end{align*} \begin{align*} \sum_{r = 0}^n \cos r \theta \sec^r \theta &= \sum_{r = 0}^n \textrm{Re} ( e^{i r \theta})\sec^r \theta \\ &= \textrm{Re} \left ( \sum_{r=0}^n e^{i r \theta} \sec^r \theta\right) \\ &= \textrm{Re} \left ( \frac{e^{i (n+1) \theta}\sec^{n+1} \theta -1}{e^{i \theta}\sec \theta -1} \right) \\ &= \textrm{Re} \left ( \frac{e^{i (n+1) \theta}\sec^{n} \theta -\cos \theta}{e^{i \theta} -\cos \theta} \right) \\ &= \textrm{Re} \left ( \frac{e^{i (n+1) \theta}\sec^{n} \theta -\cos \theta}{i \sin \theta} \right) \\ &= \frac{1}{\sin \theta} \textrm{Im} \left ( e^{i (n+1) \theta}\sec^{n} \theta -\cos \theta \right) \\ &= \frac{\sin(n+1) \theta \sec^{n} \theta}{\sin \theta} \end{align*}

---

Solution: \begin{align*} \mathbb{P}(M = m, N = n) &= \left ( \frac{3}{12} \right)^m \left ( \frac{9}{12} \right)^n \frac{3}{12} \\ &= \frac{3^n}{4^{m+n+1}} \end{align*}

1. \begin{align*} \mathbb{P}(M = m) &= \sum_{n = 1}^{\infty} \mathbb{P}(M=m,N=n) \\ &= \sum_{n = 1}^{\infty} \frac{3^n}{4^{m+n+1}} \\ &= \frac{1}{4^{m+1}} \sum_{n = 1}^{\infty} \left ( \frac34\right)^n \\ &= \frac{1}{4^{m+1}} \frac{3/4}{1/4} \\ &= \frac{3}{4^{m+1}} \\ \\ \mathbb{P}(N = n) &= \sum_{m = 0}^{\infty} \mathbb{P}(M=m,N=n) \\ &= \sum_{m = 0}^{\infty} \frac{3^n}{4^{m+n+1}} \\ &= \frac{3^n}{4^{n+1}} \sum_{m = 0}^{\infty} \left ( \frac14\right)^n \\ &= \frac{3^n}{4^{n+1}} \frac{1}{3/4} \\ &= \frac{3^{n-1}}{4^{n}} \\ \end{align*}
2. \(M+1 \sim Geo(\frac34) \Rightarrow \mathbb{E}(M) = \frac43 -1 = \frac13\) \(N \sim Geo(\frac14) \Rightarrow \mathbb{E}(N) = 4\)

\(M,N\) are independent since \(\mathbb{P}(M = m, N =n ) = \mathbb{P}(M=m)\mathbb{P}(N=n)\) \begin{align*} \mathbb{P}(N > k) &= \sum_{n=k+1}^{\infty} \mathbb{P}(N = n) \\ &= \sum_{n=k+1}^{\infty} \frac{3^{n-1}}{4^{n}} \\ &= \frac{3^k}{4^{k+1}} \sum_{n = 0}^{\infty} \left ( \frac34\right)^n \\ &= \frac{3^k}{4^{k+1}} \frac{1}{1/4} \\ &= \frac{3^k}{4^k} \end{align*} \begin{align*} \mathbb{P}(N > M) &= \sum_{m=0}^{\infty} \mathbb{P}(N > m) \mathbb{P}(M = m) \\ &= \sum_{m=0}^{\infty} \left (\frac34 \right)^m \frac{3}{4^{m+1}}\\ &=\sum_{m=0}^{\infty} \frac{3^{m+1}}{4^{2m+1}}\\ &= \frac{3}{4} \frac{1}{13/16} \\ &= \frac{12}{13} \\ \\ \mathbb{P}(N=M) &= \sum_{m=1}^{\infty} \mathbb{P}(N=m, M=m) \\ &= \sum_{m=1}^{\infty} \frac{3^m}{4^{2m+1}} \\ &= \frac{3}{64} \sum_{m=0}^{\infty} \left ( \frac{3}{16} \right)^m \\ &= \frac{3}{64} \frac{1}{13/16} \\ &= \frac{3}{52}\\ \\ \mathbb{P}(N < M) &= 1 - \frac34 - \frac3{52} \\ &= 1 - \frac{48}{52} - \frac{3}{52} \\ &= 1 - \frac{51}{52} \\ &= \frac{1}{52} \end{align*}

---

Solution: \[ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k \]

1. \begin{align*} (1+1)^n &= \sum_{k=0}^n \binom{n}{k} \\ (1-1)^n &= \sum_{k=0}^n (-1)^n\binom{n}{k} \\ &= \sum_{\text{even }k, 0 \leq k \leq n} \binom{n}{k} -\sum_{\text{odd }k, 0 \leq k \leq n} \binom{n}{k} \end{align*} Therefore \(\displaystyle \sum_{\text{even }k, 0 \leq k \leq n} \binom{n}{k} = \sum_{\text{odd }k, 0 \leq k \leq n} \binom{n}{k} = \frac{2^n}{2} = 2^{n-1}\)
2. \begin{align*} && (1+x)^n &= \sum_{k=0}^n \binom{n}{k}x^k \\ \frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{k=0}^n k\binom{n}{k} x^{k-1} \\ x = 1: && n2^{n-1} &= \sum_{k=1}^n k\binom{n}{k} \end{align*} as required

\begin{align*} \sum_{r=0}^n (r + (-1)^r) \binom{n}{r} &= n2^{n-1}+0 = n2^{n-1} \end{align*}

---

Solution:

1. Claim: \[ \sum_{r=1}^{n}r(r+1)(r+2)(r+3)(r+4)=\tfrac{1}{6}n(n+1)(n+2)(n+3)(n+4)(n+5) \] Proof: (By Induction) Base case: (n=1) \begin{align*} LHS &= 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 5! \\ RHS &= \frac16 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 5! \end{align*} Therefore the base case is true. Inductive step: Suppose our statement is true for some \(n=k\), then consider \(n = k+1\) \begin{align*} \sum_{r=1}^{k+1} r(r+1)(r+2)(r+3)(r+4) &= \sum_{r=1}^{k} r(r+1)(r+2)(r+3)(r+4) + (k+1)(k+2)(k+3)(k+4)(k+5) \\ &\underbrace{=}_{\text{assumption}} \frac16 k(k+1)(k+2)(k+3)(k+4)(k+5) + (k+1)(k+2)(k+3)(k+4)(k+5) \\ &= (k+1)(k+2)(k+3)(k+4)(k+5) \l \frac{k}{6} +1\r \\ &= \frac16 (k+1)(k+2)(k+3)(k+4)(k+5)(k+6) \end{align*} Therefore our statement is true for \(n = k+1\). Therefore since our statement is true for \(n=1\) and if it is true for \(n=k\) then it is true for \(n = k+1\) by the principle of mathematical induction it is true for all \(n \geq 1\) Since \begin{align*} \sum_{r=1}^{n}r^5 &< \sum_{r=1}^{n}r(r+1)(r+2)(r+3)(r+4) \\ &= \frac16 n(n+1)(n+2)(n+3)(n+4)(n+5) \end{align*}
2. \begin{align*}\sum_{r=0}^{n-1} r^5 &> \sum_{r=0}^{n-1} (r-4)(r-3)(r-2)(r-1)r \\ &= \sum_{r=0}^{n-5} r(r+1)(r+2)(r+3)(r+4) \\ &= \frac16 (n-5)(n-4)(n-3)(n-2)(n-1)n \end{align*}
3. Let \(f(x) = x^5\) \begin{align*} S_{1,n} &= \sum_{r=0}^{n-1}\frac{a}{n}f\left(\frac{ra}{n}\right) \\ &= \sum_{r=0}^{n-1}\frac{a}{n}\left(\frac{ra}{n}\right)^5 \\ &=\frac{a^6}{n^6} \sum_{r=0}^{n-1}r^5\\ \end{align*} Therefore \(\frac{a^6}6 \frac{(n-5)(n-4)(n-3)(n-2)(n-1)n}{n^6} < S_{1,n} < \frac{a^6}6 \frac{(n-1)n(n+1)(n+2)(n+3)(n+4)}{n^6}\) and so \(\lim_{n\to\infty} S_{1,n} = \frac{a^6}{6}\). Similarly, \begin{align*} S_{2,n} &= \sum_{r=1}^{n}\frac{a}{n}f\left(\frac{ra}{n}\right) \\ &= \sum_{r=1}^{n}\frac{a}{n}\left(\frac{ra}{n}\right)^5 \\ &= \frac{a^6}{n^6} \sum_{r=1}^{n} r^5 \end{align*} Therefore \(\frac{a^6}6 \frac{(n-4)(n-3)(n-2)(n-1)n(n+1)}{n^6} < S_{2,n} < \frac{a^6}6 \frac{n(n+1)(n+2)(n+3)(n+4)(n+5)}{n^6}\) and so \(\lim_{n\to\infty} S_{2,n} = \frac{a^6}{6}\). Since both limits exist are are equal, we have \[ \int_{0}^{a}x^{5}\,\mathrm{d}x=\tfrac{1}{6}a^6. \]

---

Solution: In order to receive \(n\) marks over the two papers, where \(m < n \leq 2m\) the student must receive \(k\) and \(n-k\) marks in each paper. Since \(n > m\), \(n-k\) is a valid mark when \(n-k \leq m\) ie when \(n-m\leq k\), therefore the probability is: \begin{align*} \sum_{k = n-m}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k=n-m}^m \frac{1}{(m+1)^2} \\ &= \frac{m-(n-m-1)}{(m+1)^2} \\ &= \frac{2m-n+1}{(m+1)^2} \end{align*} If \(0 \leq n \leq m\) then we need \(n-k\) marks in the second paper to be positive, ie \(n-k \geq 0 \Rightarrow n \geq k\), so \begin{align*} \sum_{k = 0}^n \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k = 0}^n \frac{1}{(m+1)^2} \\ &= \frac{n+1}{(m+1)^2} \end{align*} On the first paper, they can score any number of marks, since \(n > m\), so we must have: \begin{align*} \sum_{k=0}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \frac{1}{m+1} \sum_{k=0}^m \mathbb{P}(\text{scores }n-k\text{ on second papers}) \\ &= \frac{1}{m+1}\l \sum_{k=0}^{n-m} \frac{2m-(n-k)+1}{(m+1)^2} +\sum_{k=n-m+1}^m \frac{n-k+1}{(m+1)^2}\r \end{align*}

---

Solution: Let \(S = \log_{2}\mathrm{e}-\log_{4}\mathrm{e}+\log_{16}\mathrm{e}-\ldots+(-1)^{n}\log_{2^{2^{n}}}\mathrm{e}+\ldots\) then \begin{align*} S &= \sum_{n=0}^{\infty} (-1)^n \log_{2^{2^n}} e \\ &= \sum_{n=0}^{\infty} (-1)^n \frac{\log e}{\log {2^{2^n}}} \\ &= \sum_{n=0}^{\infty} (-1)^n \frac{\log e}{2^n\log {2}} \\ &= \frac{\log e}{\log 2} \sum_{n=0}^{\infty} \frac{(-1)^n}{2^n} \\ &= \frac{1}{\log_e 2} \frac{1}{1+\frac12} \\ &= \frac{1}{\ln (2^{3/2})} \\ &= \frac{1}{\ln (2 \sqrt{2})} \end{align*}

---

Solution: \(\sin x = \frac{e^{ix} - e^{-ix}}{2i}\). Also let \(z = e^{ \frac{2\pi i}{23}}\) \begin{align*} \sum_{k=0}^{10} \sin \l \frac{(4k +2)\pi}{23} \r &= \sum_{k=0}^{10} \textrm{Im} \l \exp\l \frac{(4k +2)\pi i}{23} \r \r \\ &= \textrm{Im} \l \sum_{k=0}^{10} \exp\l \frac{(4k +2)\pi i}{23} \r \r \\ &= \textrm{Im} \l e^{ \frac{2\pi i}{23}} \sum_{k=0}^{10} z^{2k} \r \\ &= \textrm{Im} \l z \l \frac{z^{22}-1}{z^2-1} \r \r \\ &= \textrm{Im} \l z \l \frac{z^{11}(z^{11}-z^{-11})}{z(z-z^{-1})} \r \r \\ &= \textrm{Im} \l \frac{z^{11}2i \sin \frac{22 \pi}{23} }{2i \sin \frac{2 \pi}{23}} \r \r \\ &= \frac{\sin \frac{22 \pi}{23}}{\sin \frac{2 \pi}{23}} \textrm{Im} ( z^{11}) \\ &= \frac{\sin^2 \frac{22 \pi}{23}}{\sin \frac{2 \pi}{23}} \\ &= \frac{\sin^2 \frac{\pi}{23}}{2\sin \frac{\pi}{23}\cos \frac{\pi}{23}} \\ &= \frac12 \tan \frac{\pi}{23} \end{align*} Similarly, \begin{align*} \sum_{k=0}^{10} (-1)^k\sin \l \frac{(4k +2)\pi}{23} \r &= \sum_{k=0}^{10} \textrm{Im} \l (-1)^k\exp\l \frac{(4k +2)\pi i}{23} \r \r \\ &= \textrm{Im} \l \sum_{k=0}^{10} (-1)^k\exp\l \frac{(4k +2)\pi i}{23} \r \r \\ &= \textrm{Im} \l e^{ \frac{2\pi i}{23}} \sum_{k=0}^{10} (-1)^kz^{2k} \r \\ &= \textrm{Im} \l z \l \frac{z^{22}+1}{z^2+1} \r \r \\ &= \textrm{Im} \l z \l \frac{z^{11}(z^{11}+z^{-11})}{z(z+z^{-1})} \r \r \\ &= \textrm{Im} \l \frac{z^{11}2 \cos \frac{22 \pi}{23} }{2 \cos\frac{2 \pi}{23}} \r \r \\ &= \frac{\cos\frac{22 \pi}{23}}{\cos \frac{2 \pi}{23}} \textrm{Im} ( z^{11}) \\ &= \frac{\cos \frac{22 \pi}{23}\sin \frac{22 \pi}{23}}{\cos\frac{2 \pi}{23}} \\ &= \frac12 \frac{\sin \frac{44 \pi}{23}}{\cos\frac{2 \pi}{23}} \\ &= \frac12 \frac{-\sin \frac{2\pi}{23}}{\cos\frac{2 \pi}{23}} \\ &= -\frac12 \tan \frac{2\pi}{23} \end{align*}

---

Solution: \(\displaystyle \int_x^{x+1} nP_{n-1}(x) \, dx = P_n(x+1) - P_n(x)\) Claim: \(P_{n}(x+1)-P_{n}(x)=nx^{n-1},\) for \(n \geq 1\) Proof: (By induction). (Base case, \(n=1\)). \(P_1(x) = x - \frac12\), \(P_1(x+1) - P_1(x) = 1 x^{0}\) as required. Assume the equation is true for \(n = k\). So \(P_k(x+1) - P_k(x) = kx^{k-1}\) now consider \begin{align*} P_{k+1}(x+1) - P_{k+1}(x) &= \int_0^{x+1} (k+1) P_k(t) \d t + P_{k+1}(0)- \int_0^{x} (k+1) P_k(t) \d t - P_{k+1}(0) \\ &= \int_0^x (k+1)(P_k(t+1)-P_k(t)) \d t + \int_0^1 (k+1)P_k(t) \d t \\ &= (k+1)x^{k} + 0 \end{align*} So by induction we are done. \begin{align*} n\sum_{m=0}^{k}m^{n-1} &= \sum_{m=0}^{k}n \cdot m^{n-1} \\ &= \sum_{m=0}^{k}\l P_n(m+1)-P_n(m) \r \\ &= P_n(k+1) - P_n(0) \end{align*} We need to find \(P_4\) \begin{align*} P_0(x) &= 1 \\ P_1(x) &= x - \frac12 \\ P_2(x) &= x^2 -x - \int_0^1 \l x^2 - x \r \d x \\ &= x^2 - x + \frac16 \\ P_3(x) &= x^3 -\frac{3}{2}x^2 + \frac12x - \int_0^1 \l x^3 -\frac{3}{2}x^2 + \frac12x \r \d x \\ &= x^3 -\frac{3}{2}x^2 + \frac12x \\ P_4(x) &= x^4 - 2x^3 + x^2 + c \end{align*} Therefore the sum we are interested in is \(\frac14 \l P_4(1001) - P_4(0) \r = \frac14 (1001)^2 (1001-1)^2 = (1001 \cdot 500)^2 = (500500)^2\)