Problems

---

Solution: \begin{align*} && \sin(r + \tfrac12)x - \sin(r - \tfrac12) x &= \sin rx \cos \tfrac12x + \cos r x\sin\tfrac12x - \sin r x \cos \tfrac12 x + \cos rx \sin \tfrac12 x \\ &&&= 2\cos r x \sin\tfrac12 x \\ \\ && S &= \cos x + \cos 2x + \cdots + \cos n x \\ && 2\sin \tfrac12 x S &= \sin(1 + \tfrac12)x - \sin \tfrac12 x + \\ &&&\quad+ \sin(2+\tfrac12)x - \sin(2- \tfrac12)x + \\ &&&\quad+ \sin(3+\tfrac12)x - \sin(3 - \tfrac12)x + \\ &&& \quad + \cdots + \\ &&&\quad + \sin(n+\tfrac12)x - \sin(n-\tfrac12)x \\ &&&=\sin(n+\tfrac12)x - \sin\tfrac12 x \\ \Rightarrow && S &= \frac{\sin(n+\tfrac12)x - \sin\tfrac12 x}{2 \sin \tfrac12 x} \end{align*}

1. \(\,\) \begin{align*} && S_2(x) &= \sin x + \tfrac12 \sin 2 x \\ && S'_2(x) &= \cos x + \cos 2x \\ &&&= \cos x + 2\cos^2 x - 1 \\ &&&= (2\cos x -1)(\cos x + 1) \\ \end{align*} Therefore the turning points are \(\cos x= \frac12 \Rightarrow x = \frac{\pi}{3}\) and \(\cos x = -1 \Rightarrow x = \pi\)
   

   + - ↺
2. Suppose \(S_n(x)\) has a stationary point at \(x_0\), then $$ therefore \begin{align*} &&0 &= S_n'(x_0) \\ &&&= \cos x_0 + \cos 2x_0 + \cdots + \cos n x_0 \\ &&&= \frac{\sin(n+\tfrac12)x_0 - \sin \tfrac12x_0}{2 \sin \tfrac12 x_0} \\ \Rightarrow &&\sin\tfrac12 x_0&= \sin nx_0 \cos \tfrac12 x_0 + \cos nx_0 \sin \tfrac12x_0 \\ \Rightarrow && \sin nx_0 &= (1-\cos nx_0)\tan \tfrac12 x_0 \end{align*} Therefore \(S_n(x_0) -S_{n-1}(x_0) = \tfrac1n \sin n x_0 = \tfrac1n \underbrace{(1-\cos nx_0)}_{\geq 0}\underbrace{\tan\tfrac12 x_0}_{\geq 0} \geq 0\). Therefore if \(S_{n-1}(x) > 0\) for all \(x\) on \(0 < x < \pi\) then since \(S_n(x) > S_{n-1}(x)\) at the turning points and since they agree at the end points, it must be larger at all points inbetween.
3. Notice that \(S_1(x) = \sin x \geq 0\) for all \(x \in [0,1]\) and by our previous argument we can show \(S_n > S_{n-1}\) inside the interval and equal on the boundary we must have \(S_n(x) \geq 0\) for \(x \in [0, \pi]\)

---

Solution: The coefficient of \(x^{r-1}\) in \((1+x)^n\) is \(\binom{n}{r-1}\) and the coefficient of \(x^r\) in \((1+x)^n\) is \(\binom{n}{r}\). The only ways to get \(x^r\) in the expansion of \((1+x)(1+x)^n\) is to either multiply the \(x^r\) term from the second expansion by \(1\) or the \(x^{r-1}\) term by \(x\). This is \(\binom{n}{r-1} + \binom{n}{r}\). However, the coefficient of \(x^r\) in \((1+x)^{n+1}\) is \(\binom{n+1}r\), so \(\binom{n}{r} + \binom{n}{n-1} = \binom{n+1}r\). Claim: \(B_{n+2} - B_{n+1} = B_{n}\). Proof: Consider \(n\) even, ie \(n = 2m\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} - \sum_{j=0}^m \binom{2m+1-j}{j} \\ &= \binom{2(m+1)-(m+1)}{m+1} +\sum_{j=0}^m \left ( \binom{2(m+1)-j}{j} - \binom{2m+1-j}{j} \right) \\ &= 1 + \sum_{j=1}^m \binom{2m+1-j}{j-1} \\ &= 1 + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \binom{m}{m} + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \sum_{j=0}^{m} \binom{2m-j}{j} \\ &= B_n \end{align*} Consider \(n\) even, ie \(n = 2m+1\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)+1-j}{j} - \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} \\ &= \sum_{j=0}^{m+1} \left (\binom{2(m+1)+1-j}{j} - \binom{2(m+1)-j}{j}\right)\\ &= \sum_{j=1}^{m+1} \binom{2(m+1)-j}{j-1} \\ &= \sum_{j=0}^{m} \binom{2m+1-j}{j} \\ &= B_n \end{align*} as required. \(B_0 = 1, B_1 = 2\), therefore \(B_n = F_{n+2}\)

---

Solution: Note that \({\bf p}_i \cdot {\bf p}_i = 1\) and \({\bf p}_i \cdot {\bf p}_j\) are all equal when \(i \neq j\) by symmetry and commutativity. \begin{align*} && 0 &= {\bf p}_i \cdot \left ( {\bf p}_1+ {\bf p}_2+{\bf p}_3+{\bf p}_4 \right) \\ &&&= 1 + \sum_{j \neq i} {\bf p}_i \cdot {\bf p}_j \\ &&&= 1 + 3 {\bf p}_i \cdot {\bf p}_j \\ \Rightarrow && {\bf p}_i \cdot {\bf p}_j &= -\frac13 \end{align*}

1. \(\,\) \begin{align*} && (XP_i)^2 &= ({\bf p}_i- {\bf x)}\,.\,({\bf p}_i- {\bf x}) \\ &&&= {\bf p}_i \cdot {\bf p}_i - 2 {\bf p}_i \cdot {\bf x} + {\bf x} \cdot {\bf x} \\ &&&= 2 - 2 {\bf p}_i \cdot {\bf x} \\ \Rightarrow && \sum_i (XP_i)^2 &= \sum_i \left (2 - 2 {\bf p}_i \cdot {\bf x} \right) \\ &&&= 8 - 2 \sum_i {\bf p}_i \cdot {\bf x} \\ &&&= 8 - 2 \left ( {\bf p}_1+ {\bf p}_2+{\bf p}_3+{\bf p}_4 \right) \cdot {\bf x} \\ &&&= 8 \end{align*}
2. Notice we have \(1 = \left \|\begin{pmatrix} a \\0 \\b \end{pmatrix} \right \|= a^2 + b^2\) and \(-\frac13 = \begin{pmatrix} a \\0 \\b \end{pmatrix} \cdot \begin{pmatrix} 0 \\0 \\ 1 \end{pmatrix} = b\). So \(b = -1/3\) and \(a = \sqrt{1-b^2} = 2\sqrt{2}/3\). Suppose another of the vertices has coordinates \((u,v,w)\) we must have \begin{align*} && 1 &= u^2+v^2+w^2 \\ && -\frac13&=w \\ && -\frac13 &= \frac{2\sqrt{2}}3 u +\frac19 \\ \Rightarrow && u &= -\frac{\sqrt2}3 \\ \Rightarrow && 1 &= \frac19 + \frac29 + v^2 \\ \Rightarrow && v &= \pm \sqrt{\frac{2}{3}} \end{align*} So \(P_3, P_4 = (-\frac{\sqrt2}3, \pm \frac{\sqrt{6}}3, -\frac13)\)
3. \(\,\) \begin{align*} && \sum_{i=1}^4 (XP_i)^4 &= \sum_i \left (2 - 2 {\bf p}_i \cdot {\bf x} \right)^2 \\ &&&= 4 \sum_i \left (1 - {\bf p}_i \cdot {\bf x} \right)^2 \\ &&&= 4 \sum_i (1 - 2{\bf p}_i \cdot {\bf x} + ({\bf p}_i \cdot {\bf x})^2) \\ &&&= 16 + 4\sum_i ({\bf p}_i \cdot {\bf x})^2 \\ &&&=16+ 4\left ( z^2+\left (\frac{2\sqrt{2}}3x-\frac13z \right)^2 +\left (-\frac{\sqrt{2}}3x-\frac{\sqrt{6}}3y-\frac13z \right)^2 +\left (-\frac{\sqrt{2}}3x+\frac{\sqrt{6}}3y-\frac13z \right)^2 \right) \\ &&&= 16+4 \left ( \frac43z^2 + \left (\frac89 + \frac29+\frac29 \right)x^2+\left (\frac69 + \frac69 \right)y^2 + 0xz + 0yz + 0zx \right) \\ &&&= 16+ 4\cdot\frac43(x^2+y^2+z^2) \\ &&&=16+\frac{16}{3}=\frac{64}{3} \end{align*}

Note: It may be better to view the last part of this question in terms of linear transformations. There are two possible approaches. One is to show \(T:{\bf x} \mapsto \sum_i ({\bf p}_i \cdot x) {\bf p}_i\) is \(\frac43I\) (easy since it has three eigenvectors with the same eigenvalue which span \(\mathbb{R}^3\) and we are interested in the value \({\bf x} \cdot T\mathbf{x} = \frac43 \lVert {\bf x} \rVert^2\). The second is to consider \(\sum_I ({\bf p}_i \cdot {\bf x})^2 = {\bf x}^TM{\bf x}\) where \(M = \sum_i {\bf p}_i{\bf p}_i^T\) and note that this matrix is invariant under rotations.

---

Solution: \begin{align*} \sum_{r=0}^{n-1} \e^{2i(\alpha + r\pi/n)} &= e^{2i\alpha} \sum_{r=0}^{n-1} \left (\e^{2i\pi/n} \right)^r \\ &= e^{2i\alpha} \frac{1-\left (\e^{2i\pi/n} \right)^n}{1-\e^{2i\pi/n} } \\ &= 0 \end{align*} \(d = s + r \cos \theta\) ie \(s = d - r \cos \theta\) Therefore \(d = \frac{r}{k} + r \cos \theta \Rightarrow r = \frac{kd}{1+k \cos \theta}\). The \(l_j\) will come from \(r(\alpha + \frac{j \pi}{n} )+r(\alpha + \pi + \frac{j \pi}{n} )\) \begin{align*} && l_j &= r(\alpha + \frac{(j-1) \pi}{n} )+r(\alpha + \pi + \frac{(j-1) \pi}{n} ) \\ &&&= \frac{kd}{1+k \cos \left ( \alpha + \frac{(j-1) \pi}{n}\right)}+\frac{kd}{1+k \cos \left ( \alpha+\pi+ \frac{(j-1) \pi}{n}\right)}\\ &&&= \frac{kd}{1+k \cos \left ( \alpha + \frac{(j-1) \pi}{n}\right)}+\frac{kd}{1-k \cos \left ( \alpha+ \frac{(j-1) \pi}{n}\right)}\\ &&&= \frac{2kd}{1-k^2 \cos^2 \left ( \alpha + \frac{(j-1) \pi}{n}\right)}\\ \Rightarrow && \sum_{j=1}^n \frac 1 {l_j} &= \sum_{j=0}^{n-1} \frac{1-k^2 \cos^2 \left ( \alpha + \frac{j \pi}{n}\right)}{2kd} \\ &&&= \frac{n}{2kd}-\frac{k^2}{2kd} \sum_{j=0}^{n-1} \cos^2 \left ( \alpha + \frac{j \pi}{n}\right) \\ &&&= \frac{n}{2kd}-\frac{k^2}{2kd} \sum_{j=0}^{n-1} \frac{1+ \cos \left ( 2\alpha + \frac{2j \pi}{n}\right)}{2} \\ &&&= \frac{n}{2kd}-\frac{nk^2}{2kd}-\frac{k^2}{4kd} \sum_{j=0}^{n-1}\cos \left ( 2\alpha + \frac{2j \pi}{n}\right) \\ &&&= \frac{n}{2kd}-\frac{nk^2}{2kd}-\frac{k^2}{4kd} \underbrace{\textrm{Re} \left ( \sum_{j=0}^{n-1}e^{ 2i(\alpha + \frac{j \pi}{n})} \right)}_{=0} \\ &&&= \frac{n}{2kd} - \frac{nk^2}{4kd} \\ &&&= \frac{n(2-k^2)}{4kd} \end{align*}

---

Solution:

1. Notice that \(\E[X_1] = \frac{a}{n}\) and consider \(\E[X_i]\) with \(i > 1\). the probability that this is \(1\) is \(\frac{b}{n} \cdot \frac{a}{n-1}\). So \begin{align*} && \E[S] &= \E[X_1] + \sum_{i=2}^n \E[X_i] \\ &&&= \frac{a}{n} + (n-1) \frac{ab}{n(n-1)} \\ &&&= \frac{a(b+1)}{n} \end{align*}
2. 1. The probability \(X_1X_j = 1\) is \(\frac{a}{n} \cdot \frac{b}{n-1} \cdot \frac{a-1}{n-2} = \frac{a(a-1)b}{n(n-1)(n-2)}\) since there is nothing special about the order, and the first is an \(A\) with probability \(\frac{a}{n}\) and given this occurs there are now \(a-1\) \(A\) and \(n-1\) letters left etc... Therefore \(\E[X_1X_j] = \frac{a(a-1)b}{n(n-1)(n-2)}\)
   2. \(\E[X_iX_j]\) when the pairs don't overlap is \(\frac{a}{n} \frac{b}{n-1} \frac{a-1}{n-2} \frac{b-1}{n-3}\), and so \begin{align*} && \sum\limits_{i=2}^{n-2} \bigg( \sum\limits_{j=i+2}^n \E(X_iX_j)\bigg) &= \sum\limits_{i=2}^{n-2} \bigg( \sum\limits_{j=i+2}^n \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)}\bigg) \\ &&&= \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)}\sum\limits_{i=2}^{n-2} \bigg( \sum\limits_{j=i+2}^n 1\bigg) \\ &&&= \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)}\sum\limits_{i=2}^{n-2} (n-(i+1)) \\ &&&= \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)} \left ((n-1)(n-3)-\frac{(n-2)(n-1)}{2}+1 \right) \\ &&&= \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)} \left ( \frac{2n^2-8n-6-n^2+3n-2+2}{2}\right) \\ &&&= \frac{a(a-1)b(b-1)}{n(n-1)(n-2)(n-3)} \left ( \frac{n^2-5n-6}{2}\right) \\ &&&= \frac{a(a-1)b(b-1)}{2n(n-1)} \end{align*}
   3. We also need to consider the other cross terms. \(X_iX_{i+1}=0\). (Since \(X_i = 1\) means the \(i\)th letter is \(A\) and \(X_{i+1} = 1\) means the \(i\)th letter is \(B\)). It's the same story for \(X_1X_2\), and so all the cross terms are accounted for. Therefore \begin{align*} && \E[S^2] &= \E \left [\sum X_i^2 + 2\sum_{i \neq j} X_i X_j \right] \\ &&&= \frac{a(b+1)}{n} +2(n-2)\frac{a(a-1)b}{n(n-1)(n-2)}+ 2 \frac{a(a-1)b(b-1)}{2n(n-1)} \\ &&&= \frac{a(b+1)}{n} +\frac{2a(a-1)b}{n(n-1)} + \frac{a(a-1)b(b-1)}{n(n-1)} \\ &&&= \frac{a(b+1)}{n} +\frac{a(a-1)b(b+1)}{n(n-1)} \\ && \var[S] &= \E[S^2] - \left ( \E[S] \right)^2 \\ &&&= \frac{a(b+1)}{n} + \frac{a(a-1)b(b+1)}{n(n-1)} - \frac{a^2(b+1)^2}{n^2} \\ &&&= \frac{a(b+1) \left (n(n-1) + (a-1)b n -a(b+1)(n-1) \right)}{n^2(n-1)} \\ &&&= \frac{a(b+1) \left ( (n-a)(n-b-1) \right)}{n^2(n-1)} \\ &&&= \frac{a(b+1) \left ( b(a-1) \right)}{n^2(n-1)} \\ \end{align*}

---

Solution: \begin{align*} \text{COM}: && \sum_{i=1}^n im \cdot \frac{u}{i} &= \left ( km + \sum_{i=1}^n im \right) v \\ \Rightarrow && nu &= \left ( k + \frac{n(n+1)}{2} \right) v \\ \Rightarrow && v &= \frac{2nu}{2k + n(n+1)} \end{align*} If \(2k = N(N+1)\), there will be no more collisions when \(v_n > \frac{u}{n+1}\), ie \begin{align*} && \frac{u}{n+1} &<\frac{2nu}{2k + n(n+1)} \\ \Leftrightarrow && N(N+1) + n(n+1) &< 2n(n+1) \\ \Leftrightarrow && N(N+1) &< n(n+1) \\ \end{align*} Therefore \(n = N+1\) and there will be \(N+1\) collisions. The loss of kinetic energy is: \begin{align*} && \text{initial k.e.} &= \sum_{k=1}^{N+1} \frac12 im \cdot \frac{u^2}{i^2} \\ &&&= \frac12 m u^2 \left ( \sum_{k=1}^{N+1} \frac{1}{i}\right) \\ && \text{final k.e.} &= \frac12 \left ( k + \frac{(N+1)(N+2)}{2}\right)m \left ( \frac{2(N+1)u}{N(N+1)+(N+1)(N+2)} \right)^2 \\ &&&= \frac12 m u^2 \frac{2(N+1)^2}{(N+1)(2N+2)} \\ &&&= \frac12 mu^2 \\ \Rightarrow && \Delta \text{ k.e.} &= \frac12 m u^2 \left ( \sum_{k=2}^{N+1} \frac{1}{i}\right) \end{align*}

---

Solution:

1. \begin{align*} \sum_{n=1}^{\infty} \frac{n+1}{n!} &= \sum_{n=1}^\infty \left ( \frac{1}{(n-1)!} + \frac{1}{n!} \right) \\ &= \sum_{n=0}^\infty \frac{1}{n!} + \sum_{n=1}^\infty \frac{1}{n!} \\ &= \sum_{n=0}^\infty \frac{1}{n!} + \sum_{n=0}^\infty \frac{1}{n!} - 1 \\ &= e + e - 1 \\ &= 2e-1 \end{align*} \begin{align*} \sum_{n=1}^{\infty} \frac{(n+1)^2}{n!} &= \sum_{n=1}^{\infty} \frac{n(n-1) + 3n + 1}{n!} \\ &= \sum_{n=2}^{\infty} \frac{1}{(n-2)!} + 3 \sum_{n=1}^\infty \frac1{(n-1)!} + \sum_{n=1}^\infty \frac{1}{n!} \\ &= \sum_{n=0}^{\infty} \frac{1}{n!} + 3 \sum_{n=0}^\infty \frac1{n!} + \sum_{n=0}^\infty \frac{1}{n!} -1 \\ &= 5e-1 \end{align*} \begin{align*} \sum_{n=1}^\infty \frac{(2n-1)^3}{n!} &= \sum_{n=1}^\infty \frac{8n^3-12n^2+6n-1}{n!} \\ &= \sum_{n=1}^\infty \frac{8n(n-1)(n-2)+12n^2-10n-1}{n!} \\ &= \sum_{n=1}^\infty \frac{8n(n-1)(n-2)+12n(n-1)+2n-1}{n!} \\ &= 8 e+12e+2e-(e-1) \\ &=21e+1 \end{align*}
2. \begin{align*} \frac{n^2+1}{(n+1)(n+2)} &= \frac{n^2+3n+2-3n-1}{(n+1)(n+2)}\\ &= 1 - \frac{3n+1}{(n+1)(n+2)} \\ &= 1 + \frac{2}{n+1} - \frac{5}{n+2} \\ -\log(1-x) &= \sum_{n=1}^\infty \frac1{n}x^{n} \\ \log(2) &= \sum_{n=1}^\infty \frac{2^{-n}}{n} \\ \sum_{n=0}^\infty \frac{(n^2+1)2^{-n}}{(n+1)(n+2)} &= \sum_{n=0}^{\infty} 2^{-n} + 2 \sum_{n=0}^\infty \frac{2^{-n}}{n+1}-5 \sum_{n=0}^\infty \frac{2^{-n}}{n+2} \\ &= 2 + 2\log2-5 \sum_{n=2}^\infty \frac{2^{-n+2}}{n} \\ &= 2 + 2 \log 2 - 5 \left (2\log 2 - 2 \right) \\ &= 12-8\log2 \end{align*}

---

Solution:

The curves touch when \(\sin x = 1\) ie \(x = \frac{4n+1}{2} \pi\). therefore \begin{align*} && I &= \int e^{-x} \sin x \d x \\ &&&= -e^{-x} \sin x + \int e^{-x} \cos x \d x \\ &&&= -e^{-x} \sin x -e^{-x} \cos x - I \\ && I &= -\frac{e^{-x}}2 ( \sin x + \cos x)\\ \\ && A_n &= \int_{\frac{4n+3}{2}\pi}^{\frac{4n-1}{2}\pi} e^{-x} (1-\sin x) \d x \\ &&&= \left [ -e^{-x} - \frac{e^{-x}}2(\sin x + \cos x) \right]_{\frac{4n+1}{2}\pi}^{\frac{4n+5}{2}\pi} \\ &&&= -\frac12\exp \left ( -\frac{4n+1}{2}\pi\right)+ \frac12\exp \left ( -\frac{4n-3}{2}\pi\right) \\ &&&= \frac12 (e^{2 \pi}-1) \left ( -\frac{4n+1}{2}\pi\right) \\ \\ && \sum_{n=1}^\infty A_n &= \frac12(e^{2\pi}-1)e^{-\pi/2} \sum_{n=1}^\infty e^{-2n\pi} \\ &&&= \frac12(e^{2\pi}-1)e^{-\pi/2} \frac{e^{-2\pi}}{1-e^{-2\pi}} \\ &&&= \frac12e^{-\pi/2} \end{align*}

---

Solution: \begin{array}{c|r} n & F_n \\ \hline 1 & 1 \\ 2 & 1 \\ 3 & 2 \\ 4 & 3 \\ 5 & 5 \\ 6 & 8 \\ 7 & 13 \\ 8 & 21 \\ 9 & 34 \\ 10 & 55 \end{array} \begin{questionparts} \item Claim: \(\frac1{F_i} > \frac1{2F_{i-1}}\) for \(i \geq 4\). Proof: Since \(F_i = F_{i-1}+F_{i-2}\) and \(F_i > 1\) for \(i \geq 1\) we have \(F_i > F_{i-1}\) for \(i \geq 3\). In particular we have \(F_i = F_{i-1}+F_{i-2} < 2F_{i-1}\) for \(i -1 \geq 3\) or \(i \geq 4\). Therefore \(\frac{1}{F_i} > \frac1{2F_{i-1}}\)

---

Solution: \begin{align*} \P(X = r) &= \P(X_1 = r, X_2 \leq r) + \P(X_2 = r, X_1 < r) \\ &= \P(X_1 = r) \P(X_2 \leq r) + \P(X_2 = r)\P( X_1 < r) \\ &= \frac{1}{N} \frac{r}{N} + \frac{1}{N} \frac{r-1}{N} \\ &= \frac{2r-1}{N^2} \end{align*} \begin{align*} \E(X) &= \sum_{r=1}^N r \P(X = r) \\ &= \sum_{r=1}^N \frac{2r^2 - r}{N^2} \\ &= \frac{1}{N^2} \l \frac{N(N+1)(2N+1)}{3} - \frac{N(N+1)}{2} \r \\ &= \frac{N+1}{N} \l \frac{4N-1}{6} \r \end{align*} When \(N = 100\), this is equal to \(\frac{101 \cdot 399}{6 \cdot 100} = \frac{101 \cdot 133}{200} = 67.165\) \begin{align*} &&\frac12 &\leq \P(X \leq m) \\ &&&=\sum_{r=1}^m \P(X=r) \\ &&&=\sum_{r=1}^m \frac{2r-1}{N^2} \\ &&&= \frac{1}{N^2} \l m(m+1) - m \r \\ &&&= \frac{m^2}{N^2} \\ \Rightarrow && m^2 &\geq \frac{N^2}{2} \\ \Rightarrow && m &\geq \frac{N}{\sqrt{2}} \\ \Rightarrow && m &= \left \lceil \frac{N}{\sqrt{2}} \right \rceil \end{align*} When \(N = 100\), \(100/\sqrt{2} = \sqrt{2}50\). \(\sqrt{2} > 1.4 \Rightarrow 50\sqrt{2} > 70\) \(\sqrt{2} < 1.42 \Rightarrow 50 \sqrt{2} < 71\), therefore \(\displaystyle \left \lceil \frac{100}{\sqrt{2}} \right \rceil = 71\) \begin{align*} \lim_{N \to \infty} \frac{\frac{(N+1)(4N-1)}{6N}}{ \left \lceil\frac{N}{\sqrt{2}} \right \rceil} &= \lim_{N \to \infty} \frac{\sqrt{2}}{3}\l \frac{4N^2 +3N - 1}{2N^2} \r \tag{since the floor will be irrelevant}\\ &= \lim_{N \to \infty} \frac{\sqrt{2}}{3}\l 2 + \frac{3}{2N} - \frac{1}{N^2} \r \\ &= \lim_{N \to \infty} \frac{2\sqrt{2}}{3} \end{align*}

---

Solution:

1. \begin{align*} &&(n+1)^k &= \sum_{r=0}^n \left [ (r+1)^k - r^k \right] \\ &&&= \sum_{r=0}^n \left [ \left ( \binom{k}{0}r^k+\binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) - r^k\right] \\ &&&= \sum_{r=0}^n \left ( \binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) \\ &&&=k \sum_{r=0}^n r^{k-1} + \binom{k}{2}\sum_{r=0}^nr^{k-2} + \cdots + \binom{k}{k} \sum_{r=0}^n 1 \\ &&&= kS_{k-1}(n) + \binom{k}2 S_{k-2}(n) + \cdots +\binom{k}{k-1}S_1(n) + (n+1) \\ \Rightarrow && k S_{k-1}(n) &= (n+1)^k -(n+1) -\binom{k}2 S_{k-2}(n) - \cdots -\binom{k}{k-1}S_1(n) \\ && 4S_3(n) &= (n+1)^4-(n+1) - \binom{4}{2} \frac{n(n+1)(2n+1)}{6} - \binom{4}{3} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ( (n+1)^3-1 - n(2n+1)-2n \right) \\ &&&= (n+1) \left ( n^3+3n^2+3n+1-1 - 2n^2-3n \right) \\ &&&= (n+1) \left ( n^3+n^2 \right) \\ &&&= n^2(n+1)^2 \\ \Rightarrow && S_3(n) &= \frac{n^2(n+1)^2}{4} \\ \\ &&5S_4(n) &=(n+1)^5-(n+1) - \binom{5}{2} \frac{n^2(n+1)^2}4 - \binom{5}{3} \frac{n(n+1)(2n+1)}{6} - \binom{5}{4} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ((n+1)^4 - 1-\frac{5n^2(n+1)}{2} - \frac{5n(2n+1)}{3} -\frac{5n}{2}\right)\\ &&&= \frac{n+1}{6} \left (6(n+1)^4-6-15n^2(n+1)-10n(2n+1)-15n \right) \\ &&&= \frac{n+1}{6} \left (6n^4+24n^3+36n^2+24n+6 -6-15n^3-15n^2-20n^2-10n-15n\right) \\ &&&= \frac{n+1}{6} \left (6n^4+9n^3+n^2-n\right) \\ &&&= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{6} \\ \Rightarrow && S_4(n) &= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{30} \end{align*}
2. Proceeding by induction, since \(S_k(n)\) is a polynomial of degree \(k+1\) for small \(k\), we can see that \[ (k+1)S_k(n) = \underbrace{(n+1)^{k+1}}_{\text{poly deg }=k+1} - \underbrace{(n+1)}_{\text{poly deg}=1} - \underbrace{\binom{k+1}{2}S_{k-1}(n)}_{\text{poly deg}=k} - \underbrace{\cdots}_{\text{polys deg}< k} - \underbrace{\binom{k+1}{k} S_1(n)}_{\text{poly deg}=1}\] therefore \(S_k(n)\) is a polynomial of degree \(k+1\) (in fact with leading coefficient \(\frac{1}{k+1}\). Since \(S_k(0) = \sum_{r=0}^{0} r^k = 0\) there is no constant term, and since \(S_k(1) = \sum_{r=0}^1 r^k = 1\) the sum of the coefficients is \(1\)

---

Solution:

1. \(\,\) \begin{align*} \mathbb{P}(\text{stop after r}) &= \mathbb{P}(\text{both stop at r}) + 2\mathbb{P}(\text{first stops before r second stops at r})\\ &= (q^2)^{r-1} p^2 + 2\cdot q^{r-1} p\cdot(1-q^{r-1}) \\ &= q^{r-1}p\left (2-2q^{r-1}+pq^{r-1} \right) \\ &= q^{r-1}p\left (2-q^{r-1}(1+p+q-p) \right) \\ &= q^{r-1}p\left (2-q^{r-1}-q^r\right) \\ \end{align*} \begin{align*} \E[\text{throws}] &= \sum_{r=1}^{\infty} r \mathbb{P}(\text{stop after r}) \\ &= \sum_{r=1}^{\infty} r q^{r-1}p\left (2-q^{r-1}-q^r\right) \\ &= \sum_{r=1}^{\infty} 2r q^{r-1}p-\sum_{r=1}^{\infty}r pq^{2r-2}-\sum_{r=1}^{\infty}r q^{2r-1}p \\ &=2p \sum_{r=1}^{\infty} r q^{r-1}-pq^{-2}\sum_{r=1}^{\infty}r q^{2r}-pq^{-1}\sum_{r=1}^{\infty}r q^{2r} \\ &= 2p(1-q)^{-2} - pq^{-2}q^2(1-q^2)^{-2}-pq^{-1}q^2(1-q^2)^{-2} \\ &= 2pp^{-2} -p(1+q)(1-q^2)^{-2} \\ &= 2p^{-1}-p(1+q)(1+q)^{-2}p^{-2} \\ &= 2p^{-1}-p^{-1}(1+q)^{-1} \\ &= \frac{2(1+q)-1}{p(1+q)} \\ &= \frac{1+2q}{p(1+q)} \\ &= \frac{3-2p}{p(2-p)} \end{align*}
2. \(\,\) \begin{align*} && m &= \frac{3-2p}{p(2-p)} \\ \Rightarrow && 2mp-mp^2 &= 3-2p \\ \Rightarrow && 0 &= mp^2-(2m+2)p + 3 \\ \Rightarrow && p &= \frac{2m+2 \pm \sqrt{(2m+2)^2-12m}}{2m} \\ &&&= \frac{m+1- \sqrt{m^2-m + 1}}{m} \\ \end{align*} If we are looking for an approximation, we could say \(p^2 \approx 0\) and \(p \approx \frac{3}{2(m+1)}\)