77 problems found
The \(n\)th Fermat number, \(F_n\), is defined by \[ F_n = 2^{2^n} +1\, , \ \ \ \ \ \ \ n=0, \ 1, \ 2, \ \ldots \ , \] where \(\ds 2^{2^n}\) means \(2\) raised to the power \(2^n\,\). Calculate \(F_0\), \(F_1\), \(F_2\) and \(F_3\,\). Show that, for \(k=1\), \(k=2\) and \(k=3\,\), $$ F_0F_1 \ldots F_{k-1} = F_k-2 \;. \tag{*} $$ Prove, by induction, or otherwise, that \((*)\) holds for all \(k\ge1\). Deduce that no two Fermat numbers have a common factor greater than \(1\). Hence show that there are infinitely many prime numbers.
Solution: \begin{align*} && F_0 &= 2^{2^0}+1 \\ &&&= 2^1+1 = 3\\ && F_1 &= 2^{2^1}+1 \\ &&&= 2^2+1 = 5 \\ && F_2 &= 2^{2^2}+1 \\ &&&= 2^4+1 \\ &&&= 17 \\ &&F_3 &= 2^{2^3}+1 \\ &&&= 2^8+1 \\ &&&= 257 \\ \\ && \text{empty product} &= 1\\ && F_1 - 2 &= 3-2 = 1\\ \Rightarrow&& 1 &= F_1-2\\ && F_0 &=3 \\ && F_2-2 &= 3 \\ \Rightarrow && F_0 &= F_2 - 2\\ && F_0F_1 &= 3 \cdot 5 = 15 \\ && F_3-2 &= 17-2 = 15 \\ \Rightarrow && F_0F_1 &= F_3-2 \end{align*} \begin{align*} && F_0 F_1 \cdots F_{k-1} &= \prod_{i=0}^{k-1} \left ( 2^{2^{i}}+1\right) \\ &&&= \sum_{l = \text{sum of }2^i} 2^l \\ &&&= \sum_{l=0}^{2^{k}-1}2^l \\ &&&= 2^{2^k}-1 \\ &&&= F_k-2 \end{align*} Suppose \(p \mid F_a, F_b\) with \(b > a\), then \(p \mid 2=F_b - F_0\cdots F_a \cdots F_{b-1}\) therefore \(p = 1, 2\), but \(2 \nmid F_a\) for any \(a\). Therefore any number dividing two Fermat numbers is \(1\), ie they are all coprime. Consider the smallest prime dividing \(F_n\) for each \(n\). Clearly these are all different since each \(F_n\) is coprime from all the others. Clearly there are infinitely many of time (since there are infinitely many \(F_n\)). Therefore there are infinitely many primes.
The numbers \(x_n\), where \(n=0\), \(1\), \(2\), \(\ldots\) , satisfy \[ x_{n+1} = kx_n(1-x_n) \;. \]
Solution:
Prove that \(\displaystyle \arctan a + \arctan b = \arctan \l {a + b \over 1-ab} \r\,\) when \(0 < a < 1\) and \(0 < b < 1\,\). Prove by induction that, for \(n \ge 1\,\), \[ \sum_{r = 1}^n \arctan \l {1 \over r^2 + r + 1} \r = \arctan \l {n \over n+2} \r \] and hence find \[ \sum_{r = 1}^\infty \arctan \l {1 \over r^2 + r + 1} \r\,. \] Hence prove that \[ \sum_{r = 1}^\infty \arctan \l {1 \over r^2 - r + 1} \r = {\pi \over 2}\,. \]
Solution: \begin{align*} && \arctan a &\in (0, \tfrac{\pi}{4}) \\ && \arctan b &\in (0, \tfrac{\pi}{4}) \\ \Rightarrow && \arctan a+\arctan b &\in (0, \tfrac{\pi}{2}) \\ && \tan \left ( \arctan a+\arctan b \right) &= \frac{\tan \arctan a + \tan \arctan b}{1 - \tan \arctan a \tan \arctan b} \\ &&&= \frac{a+b}{1-ab} \in (0, \infty) \\ \Rightarrow && \arctan \left ( \frac{a+b}{1-ab} \right) &\in (0, \tfrac{\pi}{2}) \\ \Rightarrow && \arctan a + \arctan b &= \arctan \left ( \frac{a+b}{1-ab} \right) \end{align*} Claim: \(\displaystyle \sum_{r = 1}^n \arctan \l {1 \over r^2 + r + 1} \r = \arctan \l {n \over n+2} \r\) Proof: (By Induction): Base case (\(n=1\)): \begin{align*} && LHS &= \sum_{r=1}^1 \arctan \left ( \frac{1}{r^2+r+1} \right) \\ &&&= \arctan \left ( \frac{1}{3} \right) \\ && RHS &= \arctan \left ( \frac{1}{1+2} \right)\\ &&&= \arctan \left ( \frac{1}{3} \right) = LHS \end{align*} Inductive step, suppose true for \(n = k\), ie \begin{align*} && \sum_{r = 1}^k \arctan \l {1 \over r^2 + r + 1} \r &= \arctan \l {k \over k+2} \r \\ \Rightarrow && \sum_{r = 1}^{k+1} \arctan \l {1 \over r^2 + r + 1} \r &= \sum_{r = 1}^k \arctan \l {1 \over r^2 + r + 1} \r+ \arctan \left ( \frac{1}{(k+1)^2+(k+1)+1} \right) \\ &&&= \arctan \l {k \over k+2} \r+\arctan \left ( \frac{1}{(k+1)^2+(k+1)+1} \right) \\ &&&= \arctan \left ( \frac{{k \over k+2}+\frac{1}{(k+1)^2+(k+1)+1} }{1-\frac{k}{k+2}\frac{1}{(k+1)^2+(k+1)+1} } \right) \\ &&&= \arctan \left ( \frac{k((k+1)^2+k+1+k)+(k+2) }{(k+2)((k+1)^2+(k+1)+1)-k} \right) \\ &&&= \arctan \left ( \frac{k^3+3k^2+4k+2 }{k^3+5k^2+8k+6} \right) \\ &&&= \arctan \left ( \frac{(k+1)(k^2+2k+2) }{(k+3)(k^2+2k+2)} \right) \\ &&&= \arctan \left ( \frac{k+1 }{(k+1)+2} \right) \\ \end{align*} Therefore it is true for \(n = k+1\), therefore it is true for all \(n \geq 1\) by the principle of mathematical induction. \begin{align*} && S &= \lim_{n \to \infty} \sum_{r = 1}^n \arctan \l {1 \over r^2 + r + 1} \r \\ &&&= \lim_{n \to \infty} \arctan \l \frac{n}{n+2} \r \\ &&&= \lim_{n \to \infty} \arctan \l \frac{1}{1+2/n} \r \\ &&&=\arctan\l \lim_{n \to \infty} \frac{1}{1+2/n} \r \\ &&&= \frac{\pi}{4} \end{align*} \begin{align*} && \sum_{r = 1}^\infty \arctan \l {1 \over r^2 - r + 1} \r &= \sum_{r = 0}^\infty \arctan \left( \frac{1}{ (r+1)^2 - (r+1) + 1} \right) \\ &&&= \sum_{r = 0}^\infty \arctan \left( \frac{1}{ r^2+r+1} \right) \\ &&&= \arctan \l \frac{1}{0^2+0+1} \r + \frac{\pi}{4} \\ &&&= \frac{\pi}{2} \end{align*}
The function \(\f\) satisfies \(\f(x+1)= \f(x)\) and \(\f(x)>0\) for all \(x\).
Solution:
Given that \(y = \ln ( x + \sqrt{x^2 + 1})\), show that \( \displaystyle \frac{\d y}{\d x} = \frac1 {\sqrt{x^2 + 1} }\;\). Prove by induction that, for \(n \ge 0\,\), \[ \l x^2 + 1 \r y^{\l n + 2 \r} + \l 2n + 1 \r x y^{\l n + 1 \r} + n^2 y^{\l n \r} = 0\;, \] where \(\displaystyle y^{(n)} = \frac{\d^n y}{\d x^n}\) and \(y^{(0)} =y\,\). Using this result in the case \(x = 0\,\), or otherwise, show that the Maclaurin series for \(y\) begins \[ x - {x^3 \over 6} +{3 x^5 \over 40} \] and find the next non-zero term.
Solution: \begin{align*} && y & = \ln ( x + \sqrt{x^2+1}) \\ \Rightarrow && \frac{\d y}{\d x} &= \frac{1}{x+\sqrt{x^2+1}} \cdot \frac{\d }{\d x} \left ( x + \sqrt{x^2+1} \right) \\ &&&= \frac{1}{x+\sqrt{x^2+1}} \left (1 + \frac12 \frac{2x}{\sqrt{x^2+1}} \right) \\ &&&= \frac{1}{x+\sqrt{x^2+1}} \left ( \frac{\sqrt{x^2+1} + x}{\sqrt{x^2+1}}\right) \\ &&&= \frac{1}{\sqrt{x^2+1}} \end{align*} Note that \(\displaystyle y^{(2)} = - \frac12 \frac{2x}{(x^2+1)^{3/2}} = - \frac{x}{(x^2+1)^{3/2}}\), and in particular \((x^2+1)y^{(2)} + xy^{(1)} = 0\). Now applying Leibnitz formula: \begin{align*} 0 &= \left ( (x^2+1)y^{(2)} + xy^{(1)} \right )^{(n)} \\ &= \left ( (x^2+1)y^{(2)}\right )^{(n)} + \left (xy^{(1)} \right )^{(n)} \\ &= (x^2+1)y^{(n+2)} +n2xy^{(n+1)} + \binom{n}{2}2y^{(n)} + xy^{(n+1)} + n y^{(n)} \\ &= (x^2+1)y^{(n+2)} + (2n+1)xy^{(n+1)} + (n^2-n+n)y^{(n)} \\ &= (x^2+1)y^{(n+2)} + (2n+1)xy^{(n+1)} + n^2y^{(n)} \end{align*} as required. When \(x = 0\): \begin{align*} && y(0) &= \ln(0 + \sqrt{0^2+1}) \\ &&&= \ln 1 = 0 \\ && y'(0) &= \frac{1}{\sqrt{0^2+1}} = 1 \\ && y^{(n+2)} &= -n^2 y^{(n)} \\ && y^{(2k)} &= 0 \\ && y^{(3)} &= -1 \\ && y^{(5)} &= 3^2 \\ && y^{(7)} &= - 5^2 \cdot 3^2 \\ \end{align*} Therefore the Maclaurin series about \(x = 0\) is \begin{align*} y &= x - \frac{1}{3!} x^3 + \frac{3^2}{5!} x^5 - \frac{3^2 \cdot 5^2}{7!} x^7 + \cdots \\ &= x - \frac{1}{6} x^3 + \frac{3}{1 \cdot 2 \cdot 4 \cdot 5} x^5 - \frac{5}{1 \cdot 2 \cdot 4 \cdot 2 \cdot 7} x^7 + \cdots \\ &= x - \frac{1}{6}x^3 + \frac{3}{40} x^5 - \frac{5}{56} x^7 + \cdots \end{align*}
Prove that \[ (\cos\theta +\mathrm{i}\sin\theta) (\cos\phi +\mathrm{i}\sin\phi) = \cos(\theta+\phi) +\mathrm{i}\sin(\theta+\phi) \] and that, for every positive integer \(n\), $$ {(\cos {\theta} + \mathrm{i}\sin {\theta})}^n = \cos{n{\theta}} + \mathrm{i}\sin{n{\theta}}. $$ By considering \((5-\mathrm{i})^2(1+\mathrm{i})\), or otherwise, prove that \[ \arctan\left(\frac{7}{17}\right)+2\arctan\left(\frac{1}{5}\right)=\frac{\pi}{4}\,. \] Prove also that \[ 3\arctan\left(\frac{1}{4}\right)+\arctan\left(\frac{1}{20}\right)+\arctan\left(\frac{1}{1985}\right)=\frac{\pi}{4}\,. \] [Note that \(\arctan\theta\) is another notation for \(\tan^{-1}\theta\).]
Solution: \begin{align*} && LHS &= (\cos\theta +\mathrm{i}\sin\theta) (\cos\phi +\mathrm{i}\sin\phi) \\ &&&= \cos \theta \cos \phi - \sin \theta \sin \phi + \mathrm{i}(\sin \theta \cos \phi + \cos \theta \sin \phi) \\ &&&= \cos (\theta + \phi) + \mathrm{i} \sin (\theta + \phi) \\ &&&= RHS \end{align*} Therefore we can see \((\cos \theta + i \sin \theta)^n = \cos n\theta + i \sin n \theta\). \begin{align*} && (5-i)^2(1+i) &= (24-10i)(1+i) \\ &&&= (24+10) + i(24-10) \\ &&&= 34+14i \\ \Rightarrow && 2\arg(5-i) +\arg(1+i) &= \arg(34+14i) \\ \Rightarrow && 2\arctan\left (-\frac{1}{5} \right) + \frac{\pi}{4} &= \arctan \left ( \frac{7}{17} \right) \\ \Rightarrow && 2\arctan\left (\frac{1}{5} \right) +\arctan \left ( \frac{7}{17} \right) &= \frac{\pi}{4} \\ \end{align*} Consider \((1+i)(4-i)^3(20-i)\) \begin{align*} && (1+i)(4-i)^3(20-i) &= (21+19i)(52-47i) \\ &&&= 1985+i \\ \Rightarrow && \frac{\pi}{4} - 3 \arctan \left ( \frac{1}{4} \right) -\arctan \left ( \frac{1}{20} \right) &= \arctan \left ( \frac{1}{1985} \right) \end{align*}
The sequence \(a_n\) is defined by \(a_0 = 1\) , \(a_1 = 1\) , and $$ a_n = {1 + a_{n - 1}^2 \over a_{n - 2} } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( n \ge 2 ) . $$ Prove by induction that $$ a_n = 3 a_{n - 1} - a_{n - 2} \ \ \ \ \ \ \ \ \ \ \ ( n \ge2 ) . $$ Hence show that $$ a_n = {\alpha^{2 n - 1} + \alpha^{- ( 2 n - 1 )} \over \sqrt 5} \ \ \ \ \ \ (n\ge1), $$ where \(\displaystyle{\alpha = {1 + \sqrt 5 \over 2}}\).
Let $$ {\rm S}_n(x)=\mathrm{e}^{x^3}{{\d^n}\over{\d x^n}}{(\mathrm{e}^{-x^3})}.$$ Show that \({\rm S}_2(x)=9x^4-6x\) and find \({\rm S}_3(x)\). Prove by induction on \(n\) that \({\rm S}_n(x)\) is a polynomial. By means of your induction argument, determine the order of this polynomial and the coefficient of the highest power of \(x\). Show also that if \(\displaystyle \frac{\d S_n}{\d x}=0\) for some value \(a\) of \(x\), then \(S_n(a)S_{n+1}(a)\le0\).
Solution: \begin{align*} && S_2(x) &= e^{x^3} \frac{d^2}{\d x^2} \left [e^{-x^3} \right] \\ &&&= e^{x^3} \frac{d}{\d x} \left [e^{-x^3}(-3x^2) \right] \\ &&&= e^{x^3} \left [e^{-x^3}(9x^4-6x) \right] \\ &&&=9x^4-6x \\ \\ && S_3(x) &= e^{x^3} \frac{\d^3}{\d x^3} \left [ e^{-x^3} \right]\\ &&&= e^{x^3} \frac{\d}{\d x} \left [ e^{-x^3}(9x^4-6x) \right ] \\ &&&= e^{x^3} e^{-x^3}\left [ (-3x^2)(9x^4-6x)+(36x^3-6) \right ] \\ &&&= -27x^6 +54x^3-6 \end{align*} Claim: \(S_n\) is a polynomial of degree \(2n\) with leading coefficient \((-3)^n\). Proof: Clearly this is true for \(n = 1, 2, 3\) by demonstration. Suppose it is true for some \(n = k\), then \begin{align*} && S_k(x) &= e^{x^2} \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] \\ && (-3)^kx^{2k} +\cdots &= e^{x^3} \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] \\ \Rightarrow && \frac{\d^k}{\d x^k} \left [ e^{x^3}\right] &= e^{-x^3} \left ( (-3)^kx^{2k} +\cdots\right) \\ \Rightarrow && \frac{\d^k}{\d x^k}\left [ e^{x^3}\right] &= e^{-x^3} (-3x^2)\left ( (-3)^kx^{2k} +\cdots\right) + e^{-x^3} S_k'(x) \\ &&&= e^{-x^3} \left (\underbrace{ (-3)^{k+1}x^{2k+2} + \cdots + S_k'(x)}_{\deg =2k+2}\right) \\ \Rightarrow && S_{k+1}(x) &= (-3)^{k+1}x^{2k+2} + \cdots + S_k'(x) \end{align*} And therefore \(S_{k+1}\) is a polynomial degree \(2(k+1)\) with leading coefficient \((-3)^{k+1}\) so by induction it's true for all \(n\). If \(S'_n(a) = 0\) then \(S_{n+1}(a) = (-3a^2)S_n(a) + S_n'(a) \Rightarrow S_{n+1}(a)S_n(a) = -3 (aS_n(a))^2 \leq 0\)
The sequence \(u_0\), \(u_1\), \(u_2\), ... is defined by $$ u_0=1,\hspace{0.2in} u_1=1, \quad u_{n+1}=u_n+u_{n-1} \hspace{0.2in}{\rm for}\hspace{0.1in}n \ge 1\,. $$ Prove that $$ u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n ) \,. $$ Using induction, or otherwise, prove the following result: \[ u_{2n} = u^2_n + u^2_{n-1} \quad \mbox{ and }\quad u_{2n+1} = u^2_{n+1} - u^2_{n-1} \] for any positive integer \(n\).
Solution: Claim: \(u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )\) Proof: (By Induction). (Base Case): \(n = 1\) \begin{align*} && LHS &= u_{n+2}^2 + u_{n-1}^2 \\ &&&= u_3^2 + u_0^2 \\ &&&= 3^2 + 1^2 = 10\\ && RHS &= 2(u_{n+1}^2+u_n^2) \\ &&&= 2(2^2 + 1^2) \\ &&&= 10 \end{align*} Therefore the base case is true. (Inductive hypothesis) Suppose \(u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )\) is true for some \(n = k\), ie \(u^2_{k+2} + u^2_{k-1} = 2( u^2_{k+1} + u^2_k )\), the consider \(n = k+1\) \begin{align*} && LHS &= u_{k+1+2}^2 + u_{k+1-1}^2 \\ &&&= (u_{k+1}+u_{k+2})^2+u_k^2 \\ &&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}u_{k+2} \\ &&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}(u_{k+1}+u_k) \\ &&&= u_{k+2}^2 + u_{k+1}^2+u_k^2+2u_{k+1}^2+2u_{k+1}u_k \\ &&&= u_{k+1}^2+2u_{k+1}^2+ u_{k+1}^2+u_k^2+2u_{k+1}u_k \\ &&&= u_{k+2}^2+2u_{k+1}^2+ (u_{k+1}+u_k)^2 \\ &&&= u_{k+2}^2+2u_{k+1}^2+ u_{k+2}^2 \\ &&&=2(u_{k+2}^2+u_{k+1}^2) \\ &&&= RHS \end{align*} Therefore it is true for \(n = k+1\). Therefore by the principle of mathematical induction it is true for all \(n \geq 1\) Claim: $ u_{2n} = u^2_n + u^2_{n-1} \quad \mbox{ and }\quad u_{2n+1} = u^2_{n+1} - u^2_{n-1} $ Proof: Notice that \(\begin{pmatrix}u_{n+1} \\ u_n \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix}1 \\1 \end{pmatrix}\), in particular \begin{align*} && \begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\ \Rightarrow && \begin{pmatrix}u_{2n}& u_{2n-1} \\ u_{2n-1} & u_{2n-2} \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{2n} \\ &&&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\ &&&=\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}\\ &&&= \begin{pmatrix}u_{n}^2+u_{n-1}^2& u_{n-1}(u_n+u_{n-2}) \\ u_{n-1}(u_n+u_{n-2}) & u_{n-1}^2+u_{n-2}^2 \end{pmatrix} \end{align*} Therefore \(u_{2n} = u_{n}^2+u_{n-1}^2\) and \(u_{2n+1} = u_n(u_{n+1}+u_{n-1}) =(u_{n+1}-u_{n-1})(u_{n+1}-u_{n-1}) = u_{n+1}^2-u_{n-1}^2\)
Let \(a_{1}=\cos x\) with \(0 < x < \pi/2\) and let \(b_{1}=1\). Given that \begin{eqnarray*} a_{n+1}&=&{\textstyle \frac{1}{2}}(a_{n}+b_{n}),\\[2mm] b_{n+1}&=&(a_{n+1}b_{n})^{1/2}, \end{eqnarray*} find \(a_{2}\) and \(b_{2}\) and show that \[a_{3}=\cos\frac{x}{2}\cos^{2}\frac{x}{4} \ \quad\mbox{and}\quad \ b_{3}=\cos\frac{x}{2}\cos\frac{x}{4}.\] Guess general expressions for \(a_{n}\) and \(b_{n}\) (for \(n\ge2\)) as products of cosines and verify that they satisfy the given equations.
Solution: \begin{array}{c|c|c} n & a_n & b_n \\ \hline 1 & \cos x & 1 \\ \hline 2 & \frac12(1 + \cos x) & \sqrt{a_2} \\ &=\frac12(1+2\cos^2 \frac{x}{2}-1)& \sqrt{a_2} \\ &= \cos^2 \frac{x}{2} & \cos \frac{x}{2} \\ \hline 3 & \frac12(\cos^2 \frac{x}{2}+\cos \frac{x}{2}) & \sqrt{a_3\cos \frac{x}{2}} \\ &= \cos \frac{x}{2} \cdot \frac12 (\cos \frac{x}{2}+1) & \sqrt{a_3\cos \frac{x}{2}} \\ &= \cos \frac{x}{2} \cos^2 \frac{x}{4} & \cos \frac{x}{2} \cos \frac{x}{4} \end{array} Claim: \(\displaystyle a_n = \cos \frac{x}{2^{n-1}}\prod_{k=1}^{n-1} \cos \frac{x}{2^k}\), \(\displaystyle b_n = \prod_{k=1}^{n-1} \cos \frac{x}{2^k}\) Claim: \(a_{n+1} = \frac12(a_n + b_n)\) Proof: \begin{align*} && \frac12(a_n + b_n) &= \frac12 \left ( \cos \frac{x}{2^{n-1}}\prod_{k=1}^{n-1} \cos \frac{x}{2^k} + \prod_{k=1}^{n-1} \cos \frac{x}{2^k} \right) \\ &&&= \prod_{k=1}^{n-1} \cos \frac{x}{2^k} \frac12\left (\cos \frac{x}{2^{n-1}} + 1 \right) \\ &&&= \left ( \prod_{k=1}^{n-1} \cos \frac{x}{2^k} \right) \cos^{2} \frac{x}{2^n} \\ &&&= \cos \frac{x}{2^n} \prod_{k=1}^{n} \cos \frac{x}{2^k} \\ &= a_{n+1} \end{align*} Claim: \(b_{n+1} = \sqrt{a_{n+1}b_n}\) Proof: \begin{align*} && \sqrt{a_{n+1}b_n} &= \sqrt{ \cos \frac{x}{2^n} \prod_{k=1}^{n} \cos \frac{x}{2^k} \cdot \prod_{k=1}^{n-1} \cos \frac{x}{2^k} }\\ &&&= \prod_{k=1}^{n-1} \cos \frac{x}{2^k} \sqrt{\cos ^2\frac{x}{2^{n}}} \\ &&&= \prod_{k=1}^{n} \cos \frac{x}{2^k} \\ &&&= b_{n+1} \end{align*}
Define the modulus of a complex number \(z\) and give the geometric interpretation of \(\vert\,z_1-z_2\,\vert\) for two complex numbers \(z_1\) and \(z_2\). On the basis of this interpretation establish the inequality $$\vert\,z_1+z_2\,\vert\le \vert\,z_1\,\vert+\vert\,z_2\,\vert.$$ Use this result to prove, by induction, the corresponding inequality for \(\vert\,z_1+\cdots+z_n\,\vert\). The complex numbers \(a_1,\,a_2,\,\ldots,\,a_n\) satisfy \(|a_i|\le 3\) (\(i=1, 2, \ldots , n\)). Prove that the equation $$a_1z+a_2z^2\cdots +a_nz^n=1$$ has no solution \(z\) with \(\vert\,z\,\vert\le 1/4\).
Solution: Suppose \(z = a+ib\), where \(a,b \in \mathbb{R}\) then the modulus of \(z\), \(|z| = \sqrt{a^2+b^2}\). Noting the similarity to the Pythagorean theorem, we can say that \(|z_1 - z_2|\) is the distance between \(z_1\) and \(z_2\) in the Argand diagram. \begin{align*} |z_1 + z_2| &= |(z_1 - 0) + (0 -z_2)| \\ &\underbrace{\leq}_{\text{the direct distance is shorter than going via }0} |z_1 - 0| + |0 - z_2| \\ &= |z_1| + |-z_2| \\ &= |z_1| + |z_2| \end{align*} Claim: \(\displaystyle \vert\,z_1+\cdots+z_n\,\vert \leq \sum_{i=1}^n |z_i|\) Proof: (By Induction) Base Case: \(n = 1, 2\) have been proven. Inductive step, suppose it is true for \(n = k\), then consider \(n = k+1\), ie \begin{align*} \vert\,z_1+\cdots+z_k+z_{k+1}\,\vert &\leq \vert\,z_1+\cdots+z_k\vert + \vert z_{k+1}\,\vert \\ &\underbrace{\leq}_{\text{inductive hypothesis}} \sum_{i=1}^k |z_i| + |z_{k+1}| \\ &= \sum_{i=1}^{k+1} |z_i| \end{align*} Therefore if our hypothesis is true for \(n = k\) it is true for \(n = k+1\), and so since it is true for \(n = 1\) it is true by the principle of mathematical induction for all integers \(n \geq 1\). Suppose \(|z| \leq 1/4\), then consider: \begin{align*} \vert a_1z+a_2z^2+\cdots +a_nz^n \vert &\leq \vert a_1 z\vert + \vert a_2z^2\vert + \cdots + \vert a_n z_n\ \vert \\ &= \vert a_1\vert\vert z\vert + \vert a_2\vert\vert z^2\vert + \cdots + \vert a_n\vert\vert z^n\ \vert \\ &\leq 3\left ( |z| + |z|^2 + \cdots + |z|^n \right) \\ &\leq 3 \left ( \frac{1}{4} + \frac1{4^2} + \cdots + \frac{1}{4^n} \right) \\ &< 3 \frac{1/4}{1-1/4} \\ &= 1 \end{align*} Therefore we cannot have equality and there are no solutions.
Suppose that $$3=\frac{2}{ x_1}=x_1+\frac{2}{ x_2} =x_2+\frac{2}{ x_3}=x_3+\frac{2}{ x_4}=\cdots.$$ Guess an expression, in terms of \(n\), for \(x_n\). Then, by induction or otherwise, prove the correctness of your guess.
Solution: \begin{align*} x_1 &= \frac{2}{3} \\ x_n &= \frac{2}{3-x_{n-1}} \\ x_2 &= \frac{2}{3 - \frac23} \\ &= \frac{6}7 \\ x_3 &= \frac{2}{3-\frac67} \\ &= \frac{14}{15} \\ x_4 &= \frac{2}{3 - \frac{14}{15}} \\ &= \frac{30}{31} \end{align*} Guess: \(x_n = \frac{2^{n+1}-2}{2^{n+1}-1}\). Proof: (By induction) (Base case): We have checked several initial cases. (Inductive step): Suppose our formula is true for \(n = k\), then consider: \begin{align*} x_{k+1} &= \frac{2}{3 - x_{k}} \\ &= \frac{2}{3 - \frac{2^{k+1}-2}{2^{k+1}-1}}\tag{assumption} \\ &= \frac{2\cdot(2^{k+1}-1)}{3 \cdot(2^{k+1}-1) - (2^{k+1}-2) } \\ &= \frac{2^{k+2}-2}{2\cdot 2^{k+1} - 3 + 2 } \\ &= \frac{2^{k+2}-2}{ 2^{k+2} - 1 } \\ \end{align*} Therefore, if our formula is true for \(n = k\) it is true for \(n = k+1\). Therefore by the principle of mathematical induction it is true for \(n \geq 1, n \in \mathbb{Z}\)
Let \(n\) be a positive integer.
Solution:
The Fibonacci numbers \(F_{n}\) are defined by the conditions \(F_{0}=0\), \(F_{1}=1\) and \[F_{n+1}=F_{n}+F_{n-1}\] for all \(n\geqslant 1\). Show that \(F_{2}=1\), \(F_{3}=2\), \(F_{4}=3\) and compute \(F_{5}\), \(F_{6}\) and~\(F_{7}\). Compute \(F_{n+1}F_{n-1}-F_{n}^{2}\) for a few values of \(n\); guess a general formula and prove it by induction, or otherwise. By induction on \(k\), or otherwise, show that \[F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\] for all positive integers \(n\) and \(k\).
I have \(n\) fence posts placed in a line and, as part of my spouse's birthday celebrations, I wish to paint them using three different colours red, white and blue in such a way that no adjacent fence posts have the same colours. (This allows the possibility of using fewer than three colours as well as exactly three.) Let \(r_{n}\) be the number of ways (possibly zero) that I can paint them if I paint the first and the last post red and let \(s_{n}\) be the number of ways that I can paint them if I paint the first post red but the last post either of the other two colours. Explain why \(r_{n+1}=s_{n}\) and find \(r_{n}+s_{n}.\) Hence find the value of \(r_{n+1}+r_{n}\) for all \(n\geqslant1.\) Prove, by induction, that \[ r_{n}=\frac{2^{n-1}+2(-1)^{n-1}}{3}. \] Find the number of ways of painting \(n\) fence posts (where \(n\geqslant3\)) placed in a circle using three different colours in such a way that no adjacent fence posts have the same colours.