Problems

---

Solution:

1. Claim: \(\displaystyle T_n = \frac{1}{2^{2n}}\binom{2n}{n}\) Proof: (By Induction) Base case: \(n=0\). Note that \(T_0 = 1\) and \(\frac{1}{2^0}\binom{0}{0} = 1\) so the base case is true. Assume true for some \(n=k\), ie \(T_k = \frac{1}{2^{2k}} \binom{2k}{k}\) so \begin{align*} && T_{k+1} &= \frac{2(k+1)-1}{2(k+1)} \frac{1}{2^{2k}} \binom{2k}{k} \\ &&&= \frac{2k+1}{k+1} \frac{1}{2^{2k+1}} \frac{(2k)!}{k!k!} \\ &&&= \frac{2(k+1)(2k+1)}{(k+1)(k+1)} \frac{1}{2^{2(k+1)}} \frac{(2k)!}{k!k!} \\ &&&= \frac{1}{2^{2(k+1)}} \frac{(2k+2)!}{(k+1)!(k+1)!} \\ &&&= \frac{1}{2^{2(k+1)}} \binom{2(k+1)}{k+1} \end{align*} and therefore it's true for all \(n\).
2. Notice that \((1-x)^{-\frac12} = 1 + (-\tfrac12)(-x) + \frac{(-\frac12)(-\frac32)}{2!}(-x)^2+\cdots\) in particular \(a_r = \frac{(-\frac12 - r)}{r}(-1)a_{r-1} = \frac{2r-1}{2r}a_{r-1}\). Since \(a_0 = 1\) we have \(a_r = T_r\) for all \(r\).
3. Notice that \begin{align*} && (1-x)^{-\frac32} &= \sum_{r=0}^\infty b_r x^r \\ &&&= \sum_{r=0}^\infty \frac{(-\frac32)\cdot(-\frac32-1)\cdots (-\frac32-(r-1))}{r!}(-x)^r \\ &&&= \sum_{r=0}^\infty \frac{(-\frac12-1)\cdot(-\frac12-2)\cdots (-\frac12-r)}{r!}(-x)^r \\ \end{align*} Therefore \(\frac{b_r}{a_r} = \frac{r+\frac12}{\frac12} = 2r+1\) so \(b_r = \frac{2r+1}{2^{2r}} \binom{2r}{r}\)
4. Notice that \begin{align*} && (1-x)^{-\frac32} &= (1-x)^{-\frac12}(1-x)^{-1} \\ &&&= (1 + x+ x^2 + \cdots) \sum_{r=0}^{\infty} a_r x^r \\ &&&= \sum_{i=0}^{\infty} \sum_{k=0}^n a_r x^i \end{align*} So we must have \(b_r = \sum_{i=0}^ra_i\) which is the required result

---

Solution:

1. \begin{align*} && \mathbb{P}(Y_k \leq y) &= \sum_{j=k}^n\mathbb{P}(\text{exactly }j \text{ values less than }y) \\ &&&= \sum_{j=k}^m \binom{m}{j} y^j(1-y)^{n-j} \end{align*}
2. This is the number of ways to choose a committee of \(m\) people with the chair from those \(m\) people. This can be done in two ways. First: choose the committee in \(\binom{n}{m}\) ways and choose the chair in \(m\) ways so \(m \binom{n}{m}\). Alternatively, choose the chain in \(n\) ways and choose the remaining \(m-1\) committee members in \(\binom{n-1}{m-1}\) ways. Therefore \(m \binom{n}{m} = n \binom{n-1}{m-1}\) \begin{align*} (n-m) \binom{n}{m} &= (n-m) \binom{n}{n-m} \\ &= n \binom{n-1}{n-m-1} \\ &= n \binom{n-1}{m} \end{align*} \begin{align*} f_{Y_k}(y) &= \frac{\d }{\d y} \l \sum^{n}_{m=k}\binom{n}{m}y^{m}\left(1-y\right)^{n-m} \r \\ &= \sum^{n}_{m=k} \l \binom{n}{m}my^{m-1}\left(1-y\right)^{n-m} -\binom{n}{m}(n-m)y^{m}\left(1-y\right)^{n-m-1} \r \\ &= \sum^{n}_{m=k} \l n \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n \binom{n-1}{m} y^{m}\left(1-y\right)^{n-m-1} \r \\ &= n\sum^{n}_{m=k} \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n\sum^{n+1}_{m=k+1} \binom{n-1}{m-1} y^{m-1}\left(1-y\right)^{n-m} \\ &= n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \end{align*} \begin{align*} &&1 &= \int_0^1 f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1} \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \Rightarrow && \frac{1}{n \binom{n-1}{k-1}} &= \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \end{align*}
3. \begin{align*} && \mathbb{E}(Y_k) &= \int_0^1 y f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k}(1-y)^{n-k} \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k+1-1}(1-y)^{n+1-(k+1)} \d y \\ &&&= n \binom{n-1}{k-1} \frac{1}{(n+1) \binom{n}{k}}\\ &&&= \frac{n}{n+1} \cdot \frac{k}{n} \\ &&&= \frac{k}{n+1} \end{align*}

---

Solution: \begin{align*} \frac{r+1}{r} \left(\frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}}\right) &= \frac{r+1}{r} \l \frac{r!(n-1)!}{(n+r-1)!} - \frac{r!n!}{(n+r)!} \r \\ &= \frac{(r+1)!(n-1)!}{r(n+r-1)!} \l 1 - \frac{n}{n+r} \r \\ &= \frac{(r+1)!(n-1)!}{r(n+r-1)!} \frac{r}{n+r} \\ &= \frac{(r+1)!n!}{(n+r)!} \\ &= \frac{1}{^{n+r}\C_{r+1}} \end{align*} \begin{align*} \sum_{n=1}^{\infty}{\frac{1}{^{n+r}\C_{r+1}}} &= \sum_{n=1}^{\infty} \l \frac{r+1}{r} \left(\frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}}\right) \r \\ &= \frac{r+1}{r} \sum_{n=1}^{\infty} \l \frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}} \r \\ &= \frac{r+1}{r} \lim_{N \to \infty} \sum_{n=1}^{N} \l \frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}} \r \\ &= \frac{r+1}{r} \lim_{N \to \infty} \l \frac{1}{^{1+r-1}\C_{r}} - \frac{1}{^{N+r}\C_{r}}\r \\ &= \frac{r+1}{r} \frac{1}{^{1+r-1}\C_{r}} \tag{since \(\frac{1}{^{N+r}\C_{r}} \to 0\)} \\ &= \frac{r+1}{r} \end{align*} When \(r = 2\), we have: \begin{align*} && \frac{3}{2} &= \sum_{n=1}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ && &=\frac{1}{^{1+2}\C_{3}} + \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ && &= 1 + \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ \Rightarrow && \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} &= \frac12 \end{align*} \begin{align*} \frac{1}{^{n+1}\C_{3}} &= \frac{3!}{(n+1)n(n-1)} \\ &= \frac{3!}{n^3-n} \\ &> \frac{3!}{n^3} \end{align*} \begin{align*} \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} &= \frac{5!}{(n+1)n(n-1)} - \frac{5!}{(n+2)(n+1)n(n-1)(n-2)} \\ &= \frac{5!}{n^3} \frac{n^2}{n^2-1}\l 1- \frac{1}{n^2-4} \r \\ &= \frac{5!}{n^3} \frac{n^2}{n^2-1}\l \frac{n^2-5}{n^2-4} \r \\ &= \frac{5!}{n^3} \frac{n^2(n^2-5)}{(n^2-1)(n^2-4)} \\ &< \frac{5!}{n^3} \end{align*} Since \(k(k-5) < (k-1)(k-4) \Leftrightarrow 0 < 4\), this only makes sense if \(n \geq 3\) \begin{align*} &&\frac{3!}{n^3} &< \frac{1}{^{n+1}\C_{3}} \tag{if \(n \geq 3\)} \\ \Rightarrow &&\sum_{n=3}^\infty \frac{3!}{n^3} &< \sum_{n=3}^\infty \frac{1}{^{n+1}\C_{3}} \\ \Rightarrow && \frac{6}{1^3} + \frac{6}{2^3} + \sum_{n=3}^\infty \frac{3!}{n^3} &< \frac{6}{1^3} + \frac{6}{2^3} + \sum_{n=3}^\infty \frac{1}{^{n+1}\C_{3}} \\ \Rightarrow && \sum_{n=1}^\infty \frac{3!}{n^3} &< 6 + \frac{3}{4} + \sum_{n=2}^\infty \frac{1}{^{n+2}\C_{2+1}} \\ \Rightarrow && \sum_{n=1}^\infty \frac{3!}{n^3} &< 6 + \frac{3}{4} + \frac{1}{2} = \frac{29}{4} \\ \Rightarrow && \sum_{n=1}^\infty \frac{1}{n^3} &< \frac{29}{24} = \frac{116}{96} \\ \end{align*} \begin{align*} && \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} &< \frac{5!}{n^3} \\ \Rightarrow && \sum_{n=3}^\infty \l \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} \r &< \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{20}{^{n+1}\C_3} - \sum_{n=3}^\infty \frac{1}{^{n+2}\C_{5}} &< \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=2}^\infty \frac{20}{^{n+2}\C_{2+1}} - \sum_{n=1}^\infty \frac{1}{^{n+4}\C_{4+1}} &< \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \frac{20}{2} - \frac{4+1}{4} &< \sum_{n=1}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{115}{96} &< \sum_{n=1}^\infty \frac{1}{n^3} \\ \end{align*}

---

Solution:

1. \(\frac{(-N)(-N-1)\cdots(-N-n+1)}{n!} = \binom{N+n-1}{n}\), so \[ (1-x)^{-N} = \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\] \begin{align*} && (1-x)^{-N-1} &= (1-x)^{-1}(1-x)^{-N} \\ &&&= (1 + x + x^2 + \cdots)\left ( \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\right)\\ [x^{n}]: && \binom{N+1+n-1}{n} &= \sum_{j=0}^n \underbrace{1}_{x^{n-j} \text{ from 1st bracket}}\cdot\underbrace{\binom{N+j-1}{j}}_{x^j\text{ from second bracket}} \\ \Rightarrow && \binom{N+n}{n} &= \sum_{j=0}^n \binom{N+j-1}{j} \end{align*}
2. Consider \((1+x)^{m+n} = (1+x)^m(1+x)^n\) and consider the coefficient of \(x^r\) from each side. On the left hand side this is clearly \(\binom{m+n}{r}\) on the right hand side we can take \(x^j\) from \((1+x)^m\) and \(x^{n-j}\) from \((1+x)^n\) and \(j\) can take any value from \(0\) to \(r\), ie \[ \binom{m+n} r = \sum _{j=0}^r \binom m j \binom n {r-j} \]
3. Consider \((1-x)^{-(N+m+1)} = (\)

---

Solution: \(c_r = \binom{n}{r}a^{n-r}b^r\) \begin{align*} && c_m &\geq c_{m+1} \\ \Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m+1} a^{n-m-1}b^{m+1} \\ \Rightarrow && \frac{1}{(n-m)}a &\geq \frac{1}{m+1}b \\ \Rightarrow && (m+1)a &\geq (n-m)b \\ \Rightarrow && m(a+b) &\geq nb -a \\ \Rightarrow && m &\geq \frac{n(b+1)-a-b}{a+b}=\frac{n(b+1)}{a+b} - 1 \\ \\ && c_m &\geq c_{m-1} \\ \Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m-1} a^{n-m+1}b^{m-1} \\ \Rightarrow && \frac{1}m b &\geq \frac{a}{(n-m+1)} \\ \Rightarrow && (n-m+1)b &\geq ma \\ \Rightarrow && (n+1)b &\geq m(a+b) \\ \Rightarrow && m &\leq \frac{(n+1)b}{a+b} \end{align*} Since \(m\) lies between two values \(1\) apart is is either equal to one of those two values or is the unique integer between them. Let \(\displaystyle G(n,a,b) = \left \lfloor \frac{b(n+1)}{a+b} \right \rfloor\), so

1. \(\,\) \begin{align*} && G(9,1,3) &= \left \lfloor \frac{3(9+1)}{1+3} \right \rfloor \\ &&&= \left \lfloor \frac{30}{4} \right \rfloor \\ &&&= 7 \\ \\ && G(9,2,3) &= \left \lfloor \frac{3(9+1)}{2+3} \right \rfloor \\ &&&= \left \lfloor \frac{30}{5} \right \rfloor \\ &&&= 6 \end{align*}
2. \(\,\) \begin{align*} && G(2k, a, a) &= \left \lfloor \frac{a(2k+1)}{a+a} \right \rfloor \\ && &= \left \lfloor \frac{2k+1}{2} \right \rfloor \\ &&&= k \\ \\ && G(2k-1, a, a) &= \left \lfloor \frac{a(2k-1+1)}{a+a} \right \rfloor \\ && &= \left \lfloor k\right \rfloor \\ &&&= k \\ \end{align*}
3. \(G(n,a,b)\) is decreasing in \(a\), therefore take \(a = 1\).
4. For fixed \(n\), we are looking at \(\frac{a(n+1)}{a+b}\) and we want this to be as large as possible. By considering \((n+1) - \frac{b(n+1)}{a+b}\) we can see this is increasing in \(b\) and the largest value possible is \(n\). This is achieved when \begin{align*} && \frac{b(n+1)}{a+b} & \geq n \\ \Leftrightarrow && bn + b &\geq na + bn \\ \Leftrightarrow && b& \geq na \end{align*}

---

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:

1. Notice that \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \text{Evaluate at }x = 1: && 2^n &= \sum_{i=0}^n \binom{n}{i} \end{align*}
2. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\ \text{Evaluate at }x = 1: && n2^{n-1} &= \sum_{i=1}^n i\binom{n}{i} \end{align*}
3. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \Rightarrow && \int_0^1(1+x)^n \d x &= \int_0^1 \sum_{i=0}^n \binom{n}{i} x^i \d x \\ \Rightarrow && \frac{1}{n+1}(2^{n+1}-1) &= \sum_{i=0}^n \binom{n}{i}\int_0^1 x^i \d x\\ &&& = \sum_{i=0}^n \frac{1}{i+1}\binom{n}{i} \\ \end{align*}
4. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\ \times x: && nx(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i} \\ \frac{\d}{\d x}: && n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2} &= \sum_{i=1}^n i^2\binom{n}{i} x^{i-1} \\ \text{Evaluate at }x = 1: && \sum_{i=1}^n i^2\binom{n}{i} &= n(1+1)^{n-1}+n(n-1)x(1+1)^{n-2} \\ &&&= 2^{n-2} \left (n(n-1) + 2n \right) \\ &&&= n(n+1)2^{n-2} \end{align*}

---

Solution: There will be \(200\) marked vols out of \(N\), and we are finding \(11\) of them. There are \(\binom{200}{11}\) ways to chose the \(11\) marked voles and \(\binom{N - 200}{200-11}\) ways to choose the unmarked voles. The total number of ways to choose \(200\) voles is \(\binom{N}{200}\). Therefore the probability is \begin{align*} p_N &= \frac{\binom{200}{11} \cdot \binom{N - 200}{200-11}}{\binom{N}{200}} \\ &= \binom{200}{11} \cdot \frac{ \frac{(N-200)!}{(189)!(N - 389)!} }{\frac{N!}{(N-200)!(200)!}} \\ &= \binom{200}{11} \frac{200!}{189!} \frac{\big((N-200)!\big)^2}{N!(N-389)!} \end{align*} As required and \(k = \binom{200}{11} \frac{200!}{189!}\). We want to maximise \(\frac{(N-200)!^2}{N!(N-389)!}\), we will do this by comparing consecutive \(p_N\). \begin{align*} \frac{p_{N+1}}{p_N} &= \frac{\frac{(N+1-200)!^2}{(N+1)!(N+1-389)!}}{\frac{(N-200)!^2}{N!(N-389)!}} \\ &= \frac{(N-199)!^2 \cdot N! \cdot (N-389)!}{(N+1)!(N-388)!(N-200)!^2} \\ &= \frac{(N-199)^2 \cdot 1 \cdot 1}{(N+1) \cdot (N-388)\cdot 1} \\ \end{align*} \begin{align*} && \frac{p_{N+1}}{p_N} &> 1 \\ \Leftrightarrow && \frac{(N-199)^2 \cdot 1 \cdot 1}{(N+1) \cdot (N-388)\cdot 1} & > 1 \\ \Leftrightarrow && (N-199)^2 & > (N+1) \cdot (N-388) \\ \Leftrightarrow && N^2-2\cdot199N+199^2 & > N^2 - 387N -388 \\ \Leftrightarrow && -398N+199^2 & > - 387N -388 \\ \Leftrightarrow && 199^2+388 & > 11N\\ \Leftrightarrow && \frac{199^2+388}{11} & > N\\ \Leftrightarrow && 3635\frac{4}{11} & > N\\ \end{align*} Therefore \(p_N\) is increasing if \(N \leq 3635\), so we should take \(N = 3636\). \[ \P(\text{exactly } j \text{ marked voles}) = \frac{\binom{389}{j} \cdot \binom{3636 - 389}{200-j}}{\binom{3636}{200}}\] Since \begin{align*} && 1 &= \sum_{j=0}^{200} \P(\text{exactly } j \text{ marked voles}) \\ && &= \sum_{j=0}^{200} \frac{\binom{389}{j} \cdot \binom{3247}{200-j}}{\binom{3636}{200}} \\ \Leftrightarrow&& \binom{3636}{200} &= \sum_{j=0}^{200} \binom{389}{j} \cdot \binom{3247}{200-j} \end{align*}

---

Solution: To obtain the coefficient of \(x^n\) on the RHS we clearly have \(\displaystyle \binom{2n}n\). To obtain the coefficient of \(x^n\) on the LHS we can obtain \(x^s\) from the first bracket and \(x^{n-s}\) from the second bracket, ie \(\displaystyle \sum_{s=0}^n \binom{n}{s}\binom{n}{n-s} = \sum_{s=0}^n \binom{n}{s}\binom{n}{s} = \sum_{s=0}^n \binom{n}{s}^2\)

1. Consider \((1-x)^n(1+x)^n = (1-x^2)^n\), then the coefficient of \(x^n\) (if \(n\) is even) is for the RHS \(\displaystyle (-1)^{n/2} \binom{n}{n/2}\). For the LHS, we can obtain \(x^n\) via \(x^s\) and \(x^{n-s}\) which is \(\displaystyle \sum_{s=0}^n (-1)^s\binom{n}{s}\binom{n}{n-s} = \sum_{s=0}^n (-1)^s\binom{n}{s}^2\)
2. Notice that \begin{align*} && \sum_{t=1}^ n 2t { n \choose t}^2 &= n {2n\choose n} \\ \Leftrightarrow && \sum_{t=1}^ n 2t \frac{n}{t} { n-1 \choose t-1}\binom{n}{t} &= n \frac{2n}{n}{2n-1\choose n-1} \\ \Leftrightarrow && \sum_{t=1}^ n { n-1 \choose t-1}\binom{n}{t} &= {2n-1\choose n-1} \\ \Leftrightarrow && \sum_{t=1}^ n { n-1 \choose t-1}\binom{n}{n-t} &= {2n-1\choose n-1} \\ \end{align*} but this is exactly what we would obtain by considering the coefficient of \(x^{n-1}\) in \((1+x)^{n-1}(1+x)^n \equiv (1+x)^{2n-1}\)

---

Solution: If the highest mark is \(k\), then there are \(n-1\) remaining marks to give, and they have to be chosen from the numbers \(1, 2, \ldots, k-1\), ie in \(\binom{k-1}{n-1}\) ways. There are \(n\) numbers to be chosen from \(1, 2, \ldots, m\) in total, therefore \(\displaystyle \mathbb{P}(K=k) = \left.\binom{k-1}{n-1} \right/ \binom{m}{n}\) Since \(K\) can take any of the values \(n, \cdots, m\), we must have \begin{align*} && 1 &= \sum_{k=n}^m \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ \Rightarrow && \binom{m}{n} &= \sum_{k=n}^m \binom{k-1}{n-1} \\ \\ && \mathbb{E}(K) &= \sum_{k=n}^m k \cdot \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m k \cdot \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \frac{k}{n} \cdot \binom{k-1}{n-1} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \binom{k}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n+1}^{m+1} \binom{k-1}{n+1-1} \\ &&&= n\binom{m}{n}^{-1} \binom{m+1}{n+1} \\ &&&= n \cdot \frac{m+1}{n+1} \end{align*}

---

Solution: \begin{align*} && (1+t)^{n}(1+t)^{n}&=(1+t)^{2n} \\ [t^n]: &&\sum_{k=0}^n \underbrace{\binom{n}{k}}_{t^k\text{ from left bracket}} \underbrace{\binom{n}{n-k}}_{t^{n-k}\text{ from right bracket}} &= \binom{2n}{n} \end{align*}

From each point, we can get to the diagonal ahead of us, so each move only takes us one diagonal closer together. Therefore we can only meet on the diagonal. The number of routes we can meet at is \begin{align*} && R &= \sum_{k=0}^n \underbrace{\binom{n}{k}}_{\text{I go up } k}\underbrace{\binom{n}{n-k}}_{\text{she goes down }n-k} \\ &&&= \binom{2n}{n} \end{align*} Therefore the probability is \(\displaystyle \frac1{2^{2n}} \binom{2n}n\). If I leave \(2k\) minutes late, then we will be attempting meet on a diagonal which is \(2k\) closer to me. The probability this occurs is \begin{align*} && \frac{1}{2^{2n}}\sum_{j=0}^{n-k}\binom{n-k}{j}\binom{n+k}{n-j} &= \frac{1}{2^{2n}}\binom{2n}{n} \end{align*} (by considering the coefficient of \(t^n\) in \((1+t)^{n+k}(1+t)^{n-k} =(1+t)^{2n}\)) This probability is unchanged, because you can consider the two paths as one path by one random person, conditional on them meeting and the delay doesn't change anything. If \(n = 1\) and I leave late, the only way we meet is if we end up walking towards each other down the same street (not at an intersection). This means I need to walk towards the intersection she reaches after the first minute \(\frac12\) and she needs to walk towards me \(\frac12\) so we have probability \(\frac14\)

---

Solution: \begin{align*} f(x) & =nx-\binom{n}{2}\frac{x^{2}}{2}+\binom{n}{3}\frac{x^{3}}{3}-\cdots+(-1)^{r+1}\binom{n}{r}\frac{x^{r}}{r}+\cdots+(-1)^{n+1}\frac{x^{n}}{n} \\ f'(x) &= n - \binom{n}{2} x + \binom{n}{3}x^2 - \cdots (-1)^{r+1} \binom{n}{r} + \cdots + (-1)^{n+1} x^{n-1} \\ &= \frac{1-(1-x)^n}{x} \end{align*} Therefore, since \(\displaystyle f(x) = \int_0^xf'(t)\,dt\) \begin{align*} f(x) &= \int_0^x \frac{1 - (1-t)^n}{t} \, dt \\ &= \int_{1}^{1-x} \frac{1-y^n}{1-y} (-1)\, dy \tag{Let \(y = 1-t, \frac{dy}{dt} = -1\)} \\ &= \boxed{\int_{1-x}^1 \frac{1-y^n}{1-y} dy} \\ &= \int_{1-x}^1 \l 1 + y + y^2 + \cdots + y^{n-1} \r \, dy \\ &= \left [ y + \frac{y^2}{2} + \frac{y^3}{3} + \cdots + \frac{y^n}{n} \right]_{1-x}^1 \\ \end{align*} So when \(x = 1, 1-x = 0\) so we exactly have the sum required.

---

Solution:

1. The left hand side counts the number of red tokens we have taken. The right hand side counts the number of red tokens we have taken at each point, across all points. Therefore these must be the same.
2. \(\E[X_i] = \mathbb{P}(i\text{th token is red}) = \frac{m}{M}\) (since there is nothing special about the \(i\)th token.
3. Therefore \(\E[X] = \E[X_1 + \cdots + X_n] = n\E[X_i] = \frac{nm}{M}\)
4. \(\mathbb{P}(X=k) = \binom{m}{k}\binom{M-m}{n-k}/\binom{M}{n}\) since this is the number of ways we can choose \(k\) of the \(m\) red objects, \(n-k\) of the \(M-m\) non-red objects divided by the total number of ways we can choose our \(n\) tokens.
5. \(\,\) \begin{align*} && \frac{mn}{M} &= \E[X] \\ &&&= \sum_{k=1}^n k \mathbb{P}(X=k) \\ &&&= \sum_{k=1}^n k \binom{m}{k}\binom{M-m}{n-k}/\binom{M}{n} \\ \Rightarrow && \sum_{k=1}^n k \binom{m}{k}\binom{M-m}{n-k} &= m \frac{n}{M} \binom{M}{n} = m \binom{M-1}{n-1} \end{align*}

This question is a nice example of how to find the mean of the hypergeometric distribution

---

Solution: After \(5\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 1 \text { - go positive every time}\\ 4 & 0 \\ 3 & \binom{5}{1} \text { - go positive every time but 1} \\ 2 &0 \\ \hline & 6 \end{array} Therefore there are \(\frac{6}{2^5} = \frac{3}{16}\) ways to get to \(\{2,3,4,5\}\) After \(6\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 0 \\ 4 & \binom{6}{1} \text { - go positive every time but 1}\\ 3 & 0 \\ 2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline & 21 \end{array} Therefore there are \(\frac{21}{2^6} = \frac{21}{64}\) ways to get to \(\{2,3,4,5\}\) After \(2k\) steps we can reach \(2\) or \(4\). To get to \(2\) we must take \(k+1\) positive steps and \(k-1\) negative steps, ie \(\binom{2k}{k-1}\). To get to \(4\) we must take \(k+2\) positive steps and \(k-2\) negative steps, ie \(\binom{2k}{k-2}\) Therefore there are \(\binom{2k+1}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k}} \binom{2k+1}{k-1}\) After \(2k+1\) steps we can reach \(3\) or \(5\). To get to \(3\) we must take \(k+2\) positive steps and \(k-1\) negative steps, ie \(\binom{2k+1}{k-1}\). To get to \(5\) we must take \(k+3\) positive steps and \(k-2\) negative steps, ie \(\binom{2k+1}{k-2}\) Therefore there are \(\binom{2k+2}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}\) To find the maximum of \(P(s)\) notice that \begin{align*} && \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\ &&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\ &&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1 \end{align*} So we should only look at the even terms. \begin{align*} && \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\ &&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\ &&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\ &&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\ \Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\ \Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\ \Leftrightarrow && 3 &\geq k \\ \end{align*} Therefore the maximum is when \(s = 2\cdot 3\) or \(s = 2\cdot 4\) which we computed earlier to be \(\frac{21}{64}\)