22 problems found
By considering the expansions in powers of \(x\) of both sides of the identity $$ {(1+x)^n}{(1+x)^n}\equiv{(1+x)^{2n}}, $$ show that $$ \sum_{s=0}^n {n\choose s}^2 = {2n\choose n}, $$ where \(\displaystyle {n\choose s}= \frac{n!}{s!\,(n-s)!}\). By considering similar identities, or otherwise, show also that:
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\)
The random variable \(X\) is uniformly distributed on \([0,1]\). A new random variable \(Y\) is defined by the rule \[ Y=\begin{cases} 1/4 & \mbox{ if }X\leqslant1/4,\\ X & \mbox{ if }1/4\leqslant X\leqslant3/4\\ 3/4 & \mbox{ if }X\geqslant3/4. \end{cases} \] Find \({\mathrm E}(Y^{n})\) for all integers \(n\geqslant 1\). Show that \({\mathrm E}(Y)={\mathrm E}(X)\) and that \[{\mathrm E}(X^{2})-{\mathrm E}(Y^{2})=\frac{1}{24}.\] By using the fact that \(4^{n}=(3+1)^{n}\), or otherwise, show that \({\mathrm E}(X^{n}) > {\mathrm E}(Y^{n})\) for \(n\geqslant 2\). Suppose that \(Y_{1}\), \(Y_{2}\), \dots are independent random variables each having the same distribution as \(Y\). Find, to a good approximation, \(K\) such that \[{\rm P}(Y_{1}+Y_{2}+\cdots+Y_{240000} < K)=3/4.\]
Solution: \begin{align*} && \E[Y^n] &= \frac14 \cdot \frac1{4^n} + \frac14 \cdot \frac{3^n}{4^n} + \frac12 \int_{1/4}^{3/4}2 y^n \d y \\ &&&= \frac{3^n+1}{4^{n+1}} + \left [ \frac{y^{n+1}}{n+1} \right]_{1/4}^{3/4} \\ &&&= \frac{3^n+1}{4^{n+1}} + \frac{3^{n+1}-1}{(n+1)4^{n+1}} \end{align*} \begin{align*} && \E[Y] &= \frac{3+1}{16} + \frac{9-1}{2 \cdot 16} \\ &&&= \frac{1}{4} + \frac{1}{4} = \frac12 = \E[X] \end{align*} \begin{align*} && \E[X^2] &= \int_0^1 x^2 \d x = \frac13 \\ && \E[Y^2] &= \frac{9+1}{64} + \frac{27-1}{3 \cdot 64} = \frac{56}{3 \cdot 64} = \frac{7}{24} \\ \Rightarrow && \E[X^2] - \E[Y^2] &= \frac13 - \frac{7}{24} = \frac{1}{24} \end{align*} \begin{align*} && \E[X^n] &= \frac{1}{n+1} \\ && \E[Y^n] &= \frac{1}{n+1} \frac{1}{4^{n+1}}\left ( (n+1)(3^n+1)+3^{n+1}-1 \right) \\ &&&= \frac{1}{n+1} \frac{1}{4^{n+1}}\left ( 3^{n+1} + (n+1)3^n +n \right) \\ \\ && (3+1)^{n+1} &= 3^{n+1} + (n+1)3^n + \cdots + (n+1) \cdot 3 + 1 \\ &&&> 3^{n+1} + (n+1)3^n + n + 1 \end{align*} if \(n \geq 2\) Notice that by the central limit theorem: \begin{align*} &&\frac{1}{240\,000} \sum_{i=1}^{240\,000} Y_i &\sim N \left ( \frac12, \frac{1}{24 \cdot 240\,000}\right) \\ \Rightarrow && \mathbb{P}\left (\frac{\frac{1}{240\,000} \sum_{i=1}^{240\,000} Y_i - \frac12}{\frac1{24} \frac{1}{100}} \leq \frac23 \right) &\approx 0.75 \\ \Rightarrow && \mathbb{P} \left ( \sum_i Y_i \leq 240\,000 \cdot \left ( \frac2{3} \frac1{2400}+\frac12 \right) \right ) & \approx 0.75 \\ \Rightarrow && K &= 120\,000 + 66 \\ &&&\approx 120\,066 \end{align*}
By applying de Moivre's theorem to \(\cos5\theta+\mathrm{i}\sin5\theta,\) expanding the result using the binomial theorem, and then equating imaginary parts, show that \[ \sin5\theta=\sin\theta\left(16\cos^{4}\theta-12\cos^{2}\theta+1\right). \] Use this identity to evaluate \(\cos^{2}\frac{1}{5}\pi\), and deduce that \(\cos\frac{1}{5}\pi=\frac{1}{4}(1+\sqrt{5}).\)
Solution: \begin{align*} && (\cos \theta + i \sin \theta)^n &= \cos n \theta + i \sin n \theta \\ n = 5: && \cos 5 \theta + i \sin 5 \theta &= (\cos \theta + i \sin \theta)^5 \\ \textrm{Im}: && \sin 5 \theta &= \binom{5}{1}\cos^4 \theta \sin \theta + \binom{5}{3} \cos^2 \theta (- \sin^3 \theta) + \binom{5}{5} \sin^5 \theta \\ &&&= \sin \theta (5\cos^4 \theta-10\cos^2 \theta \sin^2 \theta+\sin^4 \theta) \\ &&&= \sin \theta (5\cos^4 \theta-10\cos^2 \theta (1-\cos^2 \theta)+(1-\cos^2 \theta)^2) \\ &&&= \sin \theta((5+10+1)\cos^4 \theta +(-10-2)\cos^2 \theta + 1) \\ &&&= \sin \theta(16\cos^4 \theta -12\cos^2 \theta + 1) \\ \end{align*} Suppose \(\theta= \frac{\pi}{5}\), then \(\sin 5 \theta = 0, \sin \theta \neq 0\), therefore if \(c = \cos \theta\) we must have \begin{align*} && 0 &= 16c^4-12c^2+1 \\ \Rightarrow && c^2 &= \frac{3 \pm \sqrt{5}}{8} \\ &&&= \frac{6\pm 2\sqrt{5}}{16} \\ &&&= \frac{(1 \pm \sqrt{5})^2}{16} \\ \Rightarrow && c &= \pm \frac{1 \pm \sqrt{5}}{4} \end{align*} Since \(c > 0\) we either have \(\cos \frac15 \pi = \frac{1+\sqrt{5}}4\) or \(\cos \frac15 \pi = \frac{\sqrt{5}-1}4\), however \(\sqrt{5}-1 < 1.5\) and so \(\frac{\sqrt{5}-1}{4} < \frac12 = \cos \frac13 \pi\) we must have \(\cos \frac15 \pi = \frac{1+\sqrt{5}}4\)
By considering the coefficient of \(x^{n}\) in the identity \((1-x)^{n}(1+x)^{n}=(1-x^{2})^{n},\) or otherwise, simplify \[ \binom{n}{0}^{2}-\binom{n}{1}^{2}+\binom{n}{2}^{2}-\binom{n}{3}^{2}+\cdots+(-1)^{n}\binom{n}{n}^{2} \] in the cases (i) when \(n\) is even, (ii) when \(n\) is odd.
Solution: The coefficient of \(x^n\) on the LHS is \begin{align*} && (1-x^2)^n &= (1-x)^n(1+x)^n \\ [x^n]: && \begin{cases} (-1)^{\lfloor \frac{n}2 \rfloor}\binom{n}{\lfloor \frac{n}2 \rfloor} &\text{if } n\text{ even} \\ 0 & \text{otherwise} \end{cases} &= \sum_{i=0}^n \underbrace{(-1)^i\binom{n}{i}}_{\text{take }(-x)^i\text{ from first bracket}} \cdot \underbrace{\binom{n}{n-i}}_{\text{take }x^{n-i}\text{ from second bracket}} \\ &&&= \sum_{i=0}^n (-1)^i\binom{n}{i}\binom{n}{i} \\ &&&= \sum_{i=0}^n (-1)^i\binom{n}{i}^2\\ \end{align*}
Let \(\omega=\mathrm{e}^{2\pi\mathrm{i}/3}.\) Show that \(1+\omega+\omega^{2}=0\) and calculate the modulus and argument of \(1+\omega^{2}.\) Let \(n\) be a positive integer. By evaluating \((1+\omega^{r})^{n}\) in two ways, taking \(r=1,2\) and \(3\), or otherwise, prove that \[ \binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots+\binom{n}{k}=\frac{1}{3}\left(2^{n}+2\cos\left(\frac{n\pi}{3}\right)\right), \] where \(k\) is the largest multiple of \(3\) less than or equal to \(n\). Without using a calculator, evaluate \[ \binom{25}{0}+\binom{25}{3}+\cdots+\binom{25}{24} \] and \[ \binom{24}{2}+\binom{24}{5}+\cdots+\binom{24}{23}\,. \] {[}\(2^{25}=33554432.\){]}
Solution: Since \(\omega^3 = 1\) and \(\omega \neq 1\) we must have that \((\omega-1)(1 + \omega + \omega^2) = 0\) but by dividing by \(\omega - 1\) we obtain the desired result. \(1+\omega^2 = -\omega\) so \(|1 + \omega^2| = |-\omega| = 1\) and \(\arg ( 1 + \omega^2) = \arg(-\omega) = \pi - \frac{2\pi}{3} = \frac{\pi}{3}\) \begin{align*} && (1 + 1)^n &= \sum_{k=0}^n \binom{n}{k}\\ && (1+ \omega)^n &= \sum_{k=0}^n \binom{n}{k} \omega^{k} \\ && (1+ \omega^2)^n &= \sum_{k=0}^n \binom{n}{k} \omega^{2k} \\ \Rightarrow && 2^n+(-\omega^2)^n + (-\omega)^n &= \sum_{k=0, k \equiv 0 \pmod{3}}^n (1+1+1)\binom{n}{k} + \sum_{k=0, k \equiv 1 \pmod{3}}^n (1 + \omega + \omega^2) \binom{n}{k} + \sum_{k=0, k \equiv 2 \pmod{3}}^n (1 + \omega^2 + \omega) \binom{n}{k} \\ \Rightarrow && 2^n +((-\omega)^n)^{-1}+(-\omega)^n &= \sum_{k=0, k \equiv 0 \pmod{3}}^n \binom{n}{k} \end{align*} \(2^n +((-\omega)^n)^{-1}+(-\omega)^n = 2^n + 2 \textrm{Re}(-\omega^n) = 2^n + 2 \cos \frac{n\pi}{3}\) Therefore our answer follows. \begin{align*} \binom{25}{0}+\binom{25}{3}+\cdots+\binom{25}{24} &= \frac13 \l 2^{25} + 2\cos (\frac{25 \pi}{3}) \r \\ &= \frac13 \l 2^{25} + 2 \cos \frac{\pi}{3} \r \\ &= \frac13 \l 2^{25} + 1 \r \\ &= \frac13 \l (4096 \cdot 4096 \cdot 2) + 1 \r \\ &= 11\,184\,811 \end{align*} Notice that \(S_2 = \binom{24}{2} + \cdots +\binom{24}{23} = \binom{24}{1} + \cdots + \binom{24}{22} = S_1\) and \(S_0 = \binom{24}0 + \cdots + \binom{24}{21} = \frac13 \l 2^{24} + 2 \r\) Therefore since \(S_0 + 2 \cdot S_2 = 2^{24}\) we must have \begin{align*} S_2 &= \frac12 \l 2^{24} - \frac13 \l 2^{24} + 2 \r \r \\ &= \frac13 \l 2^{24} - 1 \r \\ &= \frac13 \l 16777216- 1 \r \\ &= \frac13 \cdot 16777215 \\ &= 5\,592\,405 \end{align*}
Given that \(\sin\beta\neq0,\) sum the series \[ \cos\alpha+\cos(\alpha+2\beta)+\cdots+\cos(\alpha+2r\beta)+\cdots+\cos(\alpha+2n\beta) \] and \[ \cos\alpha+\binom{n}{1}\cos(\alpha+2\beta)+\cdots+\binom{n}{r}\cos(\alpha+2r\beta)+\cdots+\cos(\alpha+2n\beta). \] Given that \(\sin\theta\neq0,\) prove that \[ 1+\cos\theta\sec\theta+\cos2\theta\sec^{2}\theta+\cdots+\cos r\theta\sec^{r}\theta+\cdots+\cos n\theta\sec^{n}\theta=\frac{\sin(n+1)\theta\sec^{n}\theta}{\sin\theta}. \]
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*}
Write down the binomial expansion of \((1+x)^{n}\), where \(n\) is a positive integer.
Solution: \[ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k \]