Problems

Solution:

1. If \(f(a) = a\) then the sequence is constant, ie \(a = p+a^2-pa \Rightarrow 0 = (a-p)(a-1)\). Therefore \(a = 1, p\) If there sequence has period \(2\) then there must be a solution to \(f(f(x)) = x\), ie \begin{align*} && x &= p+(f(x)-p)f(x) \\ &&&= p+(p+(x-p)x-p)(p+(x-p)x) \\ &&&= p + (x-p)x(p+(x-p)x) \\ &&&= p+(x^2-px)(x^2-px+p) \\ \Rightarrow && 0 &= x^4-2px^3+(p+p^2)x^2-(p^2+1)x+p \\ &&&= (x-1)(x-p)(x^2-(p-1)x+1) \end{align*} The first two roots (\(x = 1, p\)) are constant sequences, so we need the second quadratic to have a root, ie \((p-1)^2-4 \geq 0 \Rightarrow p \geq 3 , p \leq -1\). We also need this root not to be \(1\) or \(p\), ie \(1-(p-1)+1 = 3-p \neq 0\) and \(p^2-(p-1)p + 1 = 1+p \neq 0\) so \(p \neq -1, 3\). Therefore \(p > 3\) or \(p < -1\).
2. There exists a constant sequence iff there is a solution to \(f(x) = x\), ie \begin{align*} && x &= f(x) \\ &&&= q + (x-p)x \\ \Leftrightarrow && 0 &= x^2-(p+1)x + q \tag{has a solution} \\ \end{align*} But if it doesn't have a solution, clearly the RHS is always larger, and if it does have a solution then there is some point where the inequality doesn't hold. Suppose \(f(x) > x\) for all \(x\) then \(f(f(x)) > f(x) > x\) therefore there is no value where \(f(f(x)) = x\) which is required for any sequence of period 2. No, consider \(p = q = 0\) so \(f(x) = x^2\) then there cannot be a period \(2\) sequence by the first part, but also clearly \(u_n = 1\) is a valid constant sequence.

Solution:

1. \(\,\) \begin{align*} && A_1 &= \frac12 \\ && B_1 &= \frac14 \\ && C_1 &= 0 \\ && D_1 &= \frac14 \end{align*} \begin{align*} && A_2 &= \frac12 \cdot \frac12 + 2 \cdot \frac14 \cdot \frac14 = \frac38 \\ && B_2 &= \frac14 \cdot \frac12 + \frac12 \cdot \frac14 = \frac14 \\ && C_2 &=2 \cdot \frac14 \cdot \frac14 =\frac18 \\ && D_2 &= B_2 = \frac14 \end{align*}
2. \begin{align*} && A_{n+1} &= \frac12 A_n+ \frac14(B_n + D_n) \\ && B_{n+1} &= \frac12 B_n+ \frac14(A_n + C_n) \\ && C_{n+1} &= \frac12 C_n+ \frac14(D_n +B_n) \\ && D_{n+1} &= \frac12 D_n+ \frac14(C_n +A_n) \\ \\ \Rightarrow && B_{n+1}+D_{n+1} &= \frac12 (B_n+D_n) + \frac12(A_n+C_n) \\ &&&= \frac12 \\ \Rightarrow && B_{n+1}&=D_{n+1} = \frac14 \\ \\ && C_{n+1} &= \frac12C_n + \frac14 \cdot \frac12 \\ &&&= \frac12 C_n + \frac18\\ &&&= \frac12 C_{n-1} + \frac1{8} + \frac1{16} \\ &&&= \frac1{8} + \frac{1}{16} + \cdots + \frac{1}{8 \cdot 2^{n-1}} \\ &&&= \frac18 \left (1 + \frac12 + \cdots + \frac1{2^{n-1}} \right) \\ &&&= \frac18\left ( \frac{1-\frac1{2^n}}{1-\frac12} \right) \\ &&&= \frac18 \left (2 - \frac{1}{2^{n-1}} \right) \\ &&&= \frac14 - \frac{1}{2^{n-1}} \\ \Rightarrow && A_n &= \frac14 + \frac1{2^{n-1}} \end{align*}

Solution:

1. \begin{align*} \frac{\d y_n}{\d x} &= \frac{\d}{\d x} \l (-1)^n e^{x^2} \frac{\d^n}{\d x^{n}} \l e^{-x^2}\r \r \\ &= (-1)^n 2xe^{x^2} \frac{\d^n}{\d x^{n}} \l e^{-x^2}\r + (-1)^n e^{x^2} \frac{\d^{n+1}}{\d x^{n+1}} \l e^{-x^2}\r \\ &= 2xy_n - (-1)^{n+1} e^{x^2} \frac{\d^{n+1}}{\d x^{n+1}} \l e^{-x^2}\r \\ &= 2xy_n - y_{n+1} \end{align*}
2. \(y_0 = 1\), \(y_1 = (-1) e^{x^2} \cdot (-2x) \cdot e^{-x^2} = 2x\), \(y_2 = e^{x^2} \frac{\d^2}{\d x^2} \l e^{-x^2}\r = e^{x^2} \frac{\d }{\d x}\l -2xe^{-x^2} \r = e^{x^2} \l -2e^{-x^2}+4x^2e^{-x^2}\r = 4x^2-2\). Therefore \(2xy_1 - 2y_0 = 2x \cdot 2x - 2\cdot1 = 4x^2-2 = y_2\) so our statement is true for \(n=1\). Assume the statement is true for \(n=k\), then \begin{align*} && y_{k+1} &= 2xy_k - 2ky_{k-1} \\ \frac{\d }{\d x}: && \frac{\d y_{k+1}}{\d x} &= 2\frac{\d}{\d x}\l xy_k \r - 2k\frac{\d y_{k-1}}{\d x} \\ \Rightarrow && 2xy_{k+1}-y_{k+2} &= 2y_k+2x \l 2xy_k-y_{k+1}\r - 2k \l 2xy_{k-1}-y_k \r \\ \Rightarrow && y_{k+2} &=2y_k+ 4x \cdot y_{k+1}-(4x^2+2k)y_k+2x \cdot 2k y_{k-1} \\ &&&= 4x \cdot y_{k+1}-(4x^2+2(k+1))y_k+2x \l2xy_k - y_{k+1} \r \\ &&&= 2x \cdot y_{k+1} -2(k+1)y_k \end{align*} Therefore since our statement is true for \(n=1\) and if it is true for \(n=k\) it is true for \(n=k=1\), therefore by the principle of mathematical induction it is true for all \(n \geq 1\). Since \(2x = \frac{y_{n+1}+2ny_{n-1}}{y_n}\) for all \(n\), we must have \begin{align*} && \frac{y_{n+1}+2ny_{n-1}}{y_n} &= \frac{y_{n+2}+2(n+1)y_{n}}{y_{n+1}} \\ \Leftrightarrow && y_{n+1}^2+2ny_{n-1}y_{n+1} &= y_ny_{n+2}+2ny_n^2+2y_n^2 \\ \Leftrightarrow && y_{n+1}^2-y_ny_{n+2} &= 2n(y_n^2-y_{n-1}y_{n+1})+2y_n^2 \end{align*}
3. Consider the functions \(f_n(x) = y_{n}^2-y_{n-1}y_{n+1}\) then clearly \(f_{n+1} = 2nf_{n} + 2y_n^2 \geq f_{n}\) so to prove \(f_n(x) > 0\) for \(n \geq 1\) it suffices to prove it for \(n = 1\). But \(f_1 = y_1^2 - y_0y_{2} = (2x)^2-(4x^2-2) = 2 > 0\) so we are done.

Solution:

1. Just before collision \(n-1\): Velocity of \(P\) is \(u_{n-2}\) Velocity of \(Q\) is \(-v_{n-2}\) \begin{align*} COM: && mu_{n-2}+km(-v_{n-2}) &= mu_{n-1}+kmv_{n-1} \\ \Rightarrow && u_{n-2}-kv_{n-2} &= u_{n-1}+kv_{n-1} \\ NEL: && v_{n-1}-u_{n-1} &= -e((-v_{n-2})-u_{n-2}) \\ \Rightarrow && v_{n-1}-u_{n-1} &= e(v_{n-2}+u_{n-2}) \end{align*} \begin{align*} &&kv_{n-1} &= u_{n-2} - kv_{n-2}-u_{n-1} \\ &&kv_{n-1}&= ku_{n-1}+kev_{n-2}+keu_{n-2} \\ \Rightarrow && kv_{n-2}(1+e) &= u_{n-2}(1-ke)-u_{n-1}(1+k) \\ \Rightarrow && kv_{n-1}(1+e) &= u_{n-1}(1-ke)-u_{n}(1+k) \\ && k(1+e)v_{n-1}-k(1+e)u_{n-1} &= k(1+e)e(v_{n-2}+u_{n-2}) \\ \Rightarrow && u_{n-1}(1-ke)-u_{n}(1+k)-k(1+e)u_{n-1} &= e(u_{n-2}(1-ke)-u_{n-1}(1+k))+k(1+e)eu_{n-2} \\ \Rightarrow && 0 &= (1+k)u_n + ((ke-1)+k(1+e)-e(1+k))u_{n-1} \\ &&& \quad \quad + (e(1-ke)+k(1+e)e)u_{n-2} \\ \Rightarrow && 0 &= (1+k)u_n- (1-k)(1+e)u_{n-1} +e(1+k)u_{n-2} \end{align*}
2. \(u_0 = A + B\) \begin{align*} &&& \begin{cases}u_0 - kv_0 &= kv_1 + u_1 \\ \frac12 (u_0+v_0) &= v_1 - u_1 \\ \end{cases} \\ \Rightarrow && (1+k)u_1 &= u_0 - kv_0 - \frac{k}{2}(u_0 + v_0) \\ \Rightarrow && u_1 &= \frac{1}{k+1} \l u_0 (1-\frac{k}{2}) - \frac32 k v_0 \r \\ &&&= \frac{67}{70} u_0 - \frac{3}{70} v_0 \end{align*} Therefore \(A+B = u_0, \frac{49A+50B}{70} = \frac{67}{70} u_0 - \frac{3}{70} v_0\) \begin{align*} && A+B &= u_0 \\ && 49A+50B &= 67u_0 - 3v_0 \\ \Rightarrow && 50u_0 - A &= 67u_0 - 3v_0 \\ \Rightarrow && A &= -17u_0 + 3v_0 \\ && B &= 18u_0 - 3v_0 \end{align*} If \(0 < 6u_0 < v_0\), then \(B < 0\) and as \(n \to \infty\) we will find that \(\l \frac57 \r^n\) dominates \(\l \frac7{10} \r^n\) and so our velocity will be negative and the particle will change direction

Solution: Claim \(a_n^2+2a_nb_n - b_n^2 = 1\) for all \(n \geq 1\) Proof: (By induction) Base case: (\(n = 1\)). When \(n = 1\) we have \(a_1^2 + 2a_1 b_1-b_1^2 = 1^2+2\cdot1\cdot2-2^2 = 1\) as required. (Inductive step). Now we assume our result is true for some \(n =k\), ie \(a_k^2+2a_kb_k - b_k^2 = 1\), now consider \(n = k+1\) \begin{align*} && a_{k+1}^2+2a_{k+1}b_{k+1} - b_{k+1}^2 &= (a_k+2b_k)^2+2(a_k+2b_k)(2a_k+5b_k) - (2a_k+5b_k)^2 \\ &&&= a_k^2+4a_kb_k+4b_k^2 +4a_k^2+18a_kb_k+20b_k^2 - 4a_k^2-20a_kb_k-25b_k^2 \\ &&&= (1+4-4)a_k^2+(4+18-20)a_kb_k +(4+20-25)b_k^2 \\ &&&= a_k^2+2a_kb_k -b_k^2 = 1 \end{align*} Therefore since our statement is true for \(n = 1\) and when it is true for \(n=k\) it is true for \(n=k+1\) by the POMI it is true for \(n \geq 1\)

1. Notice that \(b_{n+1} \geq 5 b_n\) and therefore \(b_n \geq 5^{n-1} b_1 = 2\cdot 5^{n-1}\), so \begin{align*} && 1 &= a_n^2+2a_nb_n - b_n^2\\ \Rightarrow && \frac1{b_n^2} &= c_n^2 + 2c_n - 1 \\ \to && 0 &= c_n^2 + 2c_n - 1 \quad \text{ as } n\to \infty \\ \end{align*} This has roots \(c = -1 \pm \sqrt{2}\), and since \(c_n > 0\) it must tend to the positive value, ie \(c_n \to \sqrt{2}-1\)
2. Notice that \(c_n^2 + 2c_n - 1 > 0\) so either \(c_n > \sqrt{2}-1\) or \(c_n < -1-\sqrt{2}\), but again, since \(c_n > 0\) we must have \(c_n > \sqrt{2}-1\). Therefore \(\sqrt{2} < c_n + 1\) and \(1+c_n > \sqrt{2} \Rightarrow \frac{1}{1+c_n} < \frac{\sqrt{2}}2 \Rightarrow \frac{2}{1+c_n} < \sqrt{2}\) \begin{array}{c|c|c} n & a_n & b_n \\ \hline 1 & 1 & 2 \\ 2 & 5 & 12 \\ 3 & 29 & 70 \end{array} Therefore \(c_3 = \frac{29}{70}\) and so \(\frac{2}{1 + \frac{29}{70}} = \frac{140}{99} < \sqrt{2} < \frac{29}{70} + 1 = \frac{99}{70}\)

Solution: The \(1\)st slice of bread can only be the first slice in a sandwich or a slice of toast. Therefore \(s_1 = 0\) \begin{align*} && t_r &= \underbrace{s_{r-1}}_{r-1\text{th is the end of a sandwich}} \cdot \underbrace{p}_{\text{and we make toast}} + \underbrace{t_{r-1}}_{r-1\text{th is toast}} \cdot \underbrace{p}_{\text{and we make toast}} \\ &&&= (s_{r-1}+t_{r-1})p \\ \\ && s_r &= 1-\mathbb{P}(\text{previous slice is not the first of a sandwich}) \\ &&&= 1-(s_{r-1} + t_{r-1}) \\ \\ \Rightarrow && s_r &= 1 - \frac{t_r}{p} \\ \Rightarrow && t_r &= p - ps_r \\ \Rightarrow && s_r &= 1 - s_{r-1} - (p-ps_{r-1}) \\ &&&= 1 -p -(1-p)s_{r-1} \\ &&&= q(1-s_{r-1}) \end{align*} Therefore since \(s_r + qs_{r-1} = q\) we should look for a solution of the form \(s_r = A(-q)^r + B\). The particular solution will have \((1+q)B = q \Rightarrow B = \frac{q}{1+q}\), the initial condition will have \(s_1 = \frac{q}{1+q} +A(-q) = 0 \Rightarrow q = \frac{1}{1+q}\), so we must have \begin{align*} && s_r &= \frac{q+(-q)^r}{1+q}\\ \Rightarrow && t_r &= p(1-s_r) \\ &&&= p \frac{1+q-q-(-q)^r}{1+q} \\ &&&= \frac{(1-q)(1-(-q)^r)}{1+q} \\ && s_n &= 1-\frac{q+(-q)^{n-1}}{1+q} - \frac{p(1-(-q)^{n-1})}{1+q} \\ &&&= 1-\frac{1+(1-p)(-q)^{n-1}}{1+q}\\ &&&= 1-\frac{1-(-q)^n}{1+q}\\ &&&= \frac{q+(-q)^n}{1+q}\\ && t_n &=1-s_n \\ &&&=\frac{1-(-q)^n}{1+q} \end{align*}

Solution:

1. \(\,\) \begin{align*} && I_n &= \int_0^1 x^n \arctan x \d x \\ &&&= \left [ \frac{x^{n+1}}{n+1} \arctan x\right]_0^1 - \int_0^1 \frac{x^{n+1}}{n+1} \frac{1}{1+x^2} \d x \\ &&&= \frac{1}{n+1} \frac{\pi}{4} - \frac{1}{n+1} \int_0^1 \frac{x^{n+1}}{1+x^2}\d x \\ \Rightarrow && (n+1)I_n &= \frac{\pi}{4} - \int_0^1 \frac{x^{n+1}}{1+x^2}\d x \\ && I_0 &= \frac{\pi}{4} - \int_0^1 \frac{x}{1+x^2} \d x \\ &&&= \frac{\pi}{4} - \left [\frac12 \ln(1+x^2) \right]_0^1 \\ &&&= \frac{\pi}{4} - \frac12 \ln 2 \end{align*}
2. \(\,\) \begin{align*} && (n+3)I_{n+2} + (n+1)I_n &=\left ( \frac{\pi}{4} - \int_0^1 \frac{x^{n+3}}{1+x^2} \d x \right)+ \left (\frac{\pi}{4} - \int_0^1 \frac{x^{n+1}}{1+x^2} \d x \right) \\ &&&=\frac{\pi}{2}+ \int_0^1 \frac{x^{n+1}+x^{n+3}}{1+x^2} \d x \\ &&&=\frac{\pi}{2}+ \int_0^1 x^{n+1} \d x \\ &&&= \frac{\pi}{2} + \frac{1}{n+2} \\ && 3I_2 + I_0 &= \frac{\pi}{2} + \frac{1}{2} \\ \Rightarrow && 3I_2 &=\frac{\pi}{4} + \frac12 \ln 2 + \frac12 \\ && 5I_4 + 3I_2 &= \frac{\pi}{2} + \frac14 \\ \Rightarrow && 5I_4 &= \frac{\pi}{2} + \frac14 - \left ( \frac{\pi}{4} + \frac12 \ln 2 + \frac12\right) \\ &&&= \frac{\pi}4-\frac12 \ln 2-\frac14 \\ \Rightarrow && I_4 &= \frac15 \left (\frac{\pi}4-\frac12 \ln 2-\frac14 \right) \\ &&&= \frac1{20} \left (\pi - 2\ln 2 -1 \right) \end{align*}
3. Claim: \[ (4n+1) I_{4n} =\frac{\pi}4-\frac12 \ln 2 - \frac12 \sum_{r=1}^{2n} (-1)^r \frac 1 {r} \,, \] Proof: Base case we have just shown above Assume true for \(n = k\), consider \(n = k+1\), then \begin{align*} && (4(k+1)+1) I_{4(k+1)} &= \frac{\pi}{2} + \frac{1}{4(k+1)} - (4k+3)I_{4k+2} \\ &&&= \frac{\pi}{2} + \frac{1}{4(k+1)} - \left (\frac{\pi}{2} + \frac{1}{2(2k+1)} - (4k+1)I_{4k} \right)\\ &&&= (4k+1)I_{4k} - \frac12 \left ( \frac{1}{2k+2} - \frac{1}{2k+1}\right) \\ &&&= \frac{\pi}4-\frac12 \ln 2 - \frac12 \sum_{r=1}^{2k} (-1)^r \frac 1 {r} - \frac12 \left ( \frac{1}{2k+2} - \frac{1}{2k+1}\right)\\ &&&= \frac{\pi}4-\frac12 \ln 2 - \frac12 \sum_{r=1}^{2(k+1)} (-1)^r \frac 1 {r} \\ \end{align*} as required.

Solution: \begin{align*} x_{n+2} &= \frac{ax_{n+1}-1}{x_{n+1}+b} \\ &= \frac{a \frac{ax_n - 1}{x_n+b}-1}{\frac{ax_n - 1}{x_n+b}+b} \\ &= \frac{a(ax_n-1)-(x_n+b)}{ax_n-1+b(x_n+b)} \\ &= \frac{(a^2-1)x_n-(a+b)}{(a+b)x_n+b^2-1} \end{align*}

1. If \(x_{n+2} = x_n\) then \begin{align*} && x_n &= \frac{(a^2-1)x_n-(a+b)}{(a+b)x_n+b^2-1} \\ \Rightarrow && 0 &=(a+b)x_n^2+(b^2-a^2)x_n+(a+b) \\ &&&= (a+b)(x_n^2+(a-b)x_n + 1) \end{align*} If \(x_{n+1} = x_n\) then \(x_n^2+(a-b)x_n + 1\) and since our sequence has period \(2\) rather than \(1\) it must be the case this is non-zero. Therefore \(a+b =0\).
2. \begin{align*} x_{n+4} &= \frac{(a^2-1)x_{n+2}-(a+b)}{(a+b)x_{n+2}+b^2-1} \\ &= \frac{(a^2-1)\frac{(a^2-1)x_{n}-(a+b)}{(a+b)x_{n}+b^2-1} -(a+b)}{(a+b)\frac{(a^2-1)x_{n}-(a+b)}{(a+b)x_{n}+b^2-1} +b^2-1} \\ &= \frac{((a^2-1)^2-(a+b)^2)x_n -(a^2+b^2-2)(a+b)}{(a^2+b^2-2)(a+b)x_n + (b^2-1)^2-(a+b)^2} \end{align*} If \(x_{n+4} = x_n\) then \begin{align*} x_n &=\frac{((a^2-1)^2-(a+b)^2)x_n -(a^2+b^2-2)(a+b)}{(a^2+b^2-2)(a+b)x_n + (b^2-1)^2-(a+b)^2} \\ 0 &= (a^2+b^2-2)(a+b)x_n^2 + \l (b^2-1)^2-(a^2-1)^2 \r x_n+(a^2+b^2-2)(a+b) \\ &= (a^2+b^2-2)(a+b)x_n^2+(b^2-a^2)(a^2+b^2-2)x_n + (a^2+b^2-2)(a+b) \\ &= (a^2+b^2-2)(a+b)(x_n^2+(b-a)x_n + 1) \end{align*} Since we do not want \(x_n\) to be periodic with period \(1\) we must have the quadratic in \(x_n\) \(\neq 0\). If \(a+b = 0\) then \(x_n\) is periodic with period \(2\) since \(x_{n+2} = \frac{(a^2-1)x_n}{((-a)^2-1)} = x_n\). Therefore it is necessary that \(a^2+b^2-2 = 0\). If \(a^2+b^2-2= 0\) then \begin{align*} x_{n+4} &= \frac{((a^2-1)^2-(a+b)^2)x_n}{(b^2-1)^2-(a+b)^2} \\ &=\frac{((a^2-1)^2-(a+b)^2)x_n}{((2-a^2)-1)^2-(a+b)^2} \\ &=\frac{((a^2-1)^2-(a+b)^2)x_n}{((1-a^2)^2-(a+b)^2} \\ &= x_n \end{align*} Therefore it is sufficient too. So our conditions are \(a+b \neq 0, \, \, x_n^2+(a-b)x_n + 1 \neq 0\) and \(a^2+b^2-2 = 0\)

Solution:

1. \(\,\) \begin{align*} && x(1-x)^{-2} &= x \left (1 + (-2)(-x) + \frac{(-2)(-3)}{2!}x^2 + \cdots + \frac{(-2)(-3)\cdots(-2-(k-1))}{k!} (-x)^k + \cdots \right) \\ &&&= x(1 + 2x + 3x^2 + \cdots + \frac{(-2)(-3)\cdots(-(k+1))}{k!}(-1)^k x^k + \cdots ) \\ &&&= x+2x^2 + 3x^3 + \cdots + (k+1)x^{k+1} + \cdots \\ \Rightarrow && u_n &= n \end{align*} \begin{align*} && x(1-x)^{-3} &= x \left (1 + 3x + 6x^2 + \cdots + \frac{(-3)(-4)\cdots(-k-2)}{k!}(-x)^k + \cdots \right) \\ &&&= x \left (1 + 3x + 6x^2 + \cdots + \frac{(k+2)(k+1)}{2}x^k + \cdots \right) \\ &&&= x + 3x^2 + 6x^3 + \cdots + \binom{k+2}{2}x^{k+1} + \cdots \\ && u_n &= \binom{n+1}{2} = \frac{n^2+n}{2} \\ \\ \Rightarrow && 2x(1-x)^{-3} - x(1-x)^{-2} &= (1-x)^{-3}(2x-x(1-x)) \\ &&&= (1-x)^{-3}(x+x^2) \end{align*}
2. • \(u_n = ku_{n-1} \Rightarrow u_nx^n = ku_{n-1}x^n\) so \begin{align*} && \sum_{n=1}^\infty u_n x^n &= \sum_{n=1}^\infty k u_{n-1}x^n \\ && \sum_{n=0}^\infty u_n x^n - a &= x\sum_{n=0}^\infty k u_{n}x^n \\ \Rightarrow && f(x)-a &= kx f(x) \\ \Rightarrow && f(x) &= a + kxf(x) \\ \Rightarrow && f(x) &= \frac{a}{1-kx} \end{align*}
   • Suppose \(\displaystyle f(x) = \sum_{n=0}^\infty u_n x^n\) so \begin{align*} && x^n u_n &= x^n u_{n-1} + x^n u_{n-2} \\ \Rightarrow && \sum_{n=2}^\infty x^n u_n &= \sum_{n=2}^\infty x^n u_{n-1} + \sum_{n=2}^\infty x^n u_{n-2} \\ && \sum_{n=0}^\infty x^n u_n - u_0 - u_1 x &= \left ( \sum_{n=0}^\infty x^{n+1} u_{n} -xu_0 \right) + \sum_{n=0}^\infty x^{n+2} u_{n} \\ && f(x) - x &= xf(x) +x^2f(x) \\ \Rightarrow && f(x) &= \frac{x}{1-x-x^2} \end{align*}

Solution:

1. The only way \(A\) can win is if the sequence starts HH, if it does not start like this, then the only way HHT can appear is after a sequence of THH...H, but then THH has already appeared and \(B\) has won. Therefore the probability is \(\frac14\)
2. If HH appears before TT then either \(A\) or \(B\) will win. If HH appears first, then \(A\) has a \(\frac14\) probability of winning. So \(A\): \(\frac18\), \(B:\), \(\frac38\), \(C:\), \(\frac18\), \(D: \frac38\)
3. If the first two tosses are TT then \(C\) will win. If the first two tosses are HT, then either the next toss is T and \(C\) wins, or the next toss is H, and it's as if we started TH. ie \(p = \frac12 + \frac12 q\). If the first two tosses are TH, then either the next toss is H and \(C\) losses or the next toss is T and it's like starting HT. So \(q = \frac12 p\). Therefore \(p = \frac12 + \frac14p \Rightarrow p = \frac13\) If the first two tosses are HH, then eventually a T appears, and it's the same as starting HT. Therefore the probability \(C\) wins is: \(\frac14 + \frac14 \cdot \frac13 + \frac14 \cdot \frac16 + \frac14 \cdot \frac13 = \frac{11}{24}\)

Solution: \begin{align*} I_n - I_{n+1} &= \int_0^\infty \frac 1 {(1+u^2)^n}\, \d u - \int_0^\infty \frac 1 {(1+u^2)^{n+1}}\, \d u \\ &= \int_0^\infty \l \frac 1 {(1+u^2)^n}- \frac 1 {(1+u^2)^{n+1}} \r\, \d u \\ &= \int_0^\infty \frac {u^2} {(1+u^2)^{n+1}} \, \d u \\ &= \left [ u \frac{u}{(1+u^2)^{n+1}} \right]_0^{\infty} - \frac{-1}{2n}\int_0^{\infty} \frac{1}{(1+u^2)^n} \d u \tag{\(IBP: u = u, v' = \frac{u}{(1+u^2)^{n+1}}\)}\\ &= \frac{1}{2n} I_n \end{align*} \(\displaystyle I_1 = \int_0^{\infty} \frac{1}{1+u^2} \d u = \left [ \tan^{-1} u \right]_0^\infty = \frac{\pi}{2}\) as expected. We also have, \(I_{n+1} = \frac{2n(2n-1)}{2n \cdot 2n} I_n \), by rearranging the recurrence relation. Therefore, when we multiply out the top we will have \(2n!\) and the bottom we will have two factors of \(n!\) and two factors of \(2^n\) combined with the original \(\frac{\pi}{2}\) we get \[ I_{n+1} = \frac{(2n)! \pi}{2^{2n+1} (n!)^2} \] \begin{align*} J = \int_0^\infty f\big( (x- x^{-1})^2\big ) \, \d x &= \int_{u = \infty}^{u = 0} f((u^{-1}-u)^2)(-u^{-2} )\d u \tag{\(u = x^{-1}, \d u = -x^{-2} \d x\)} \\ &= \int^{u = \infty}_{u = 0} f((u^{-1}-u)^2)u^{-2} \d u \\ &= \int^{\infty}_{0} u^{-2}f((u-u^{-1})^2) \d u \\ \end{align*} Therefore adding the two forms for \(J\) we have \begin{align*} 2 J &= \int_0^\infty f\big( (x- x^{-1})^2\big ) \, \d x + \int_0^\infty x^{-2} f\big( (x- x^{-1})^2\big ) \, \d x \\ &= \int_0^\infty (1+x^{-2}) f\big( (x- x^{-1})^2\big ) \, \d x \end{align*} And letting \(u = x - x^{-1}\), we have \(\d u = (1 + x^{-2}) \d x\), and \(u\) runs from \(-\infty\) to \(\infty\) so we have: \begin{align*} \int_0^\infty (1+x^{-2}) f\big( (x- x^{-1})^2\big ) \, \d x &= \int_{-\infty}^\infty f(u^2) \, \d u \\ &=2 \int_{0}^\infty f(u^2) \, \d u \end{align*} Since both of these are \(2J\) we have the result we are after. Finally, \begin{align*} \int_0^\infty \frac {x^{2n-2}}{(x^4-x^2+1)^n} \, \d x &= \int_0^{\infty} \frac{x^{2n-2}}{x^{2n}(x^2-1+x^{-2})^n} \d x \\ &= \int_0^{\infty} \frac{x^{-2}}{((x-x^{-1})^2+1)^n} \d x \\ &= \int_0^{\infty} \frac{1}{(x^2+1)^n} \d x \tag{Where \(f(x) = (1+x^2)^{-n}\) in \(J\) integral} \\ &= I_n = \frac{(2n-2)! \pi}{2^{2n-1} ((n-1)!)^2} \end{align*}

Solution:

1. Suppose \(u_0 = u = \sin^2 \theta\) then \begin{align*} && u_1 &= 4 u_0 (1-u_0) \\ &&&= 4 \sin^2 \theta ( 1- \sin^2 \theta) \\ &&&= 4 \sin^2 \theta \cos^2 \theta \\ &&&= (2 \sin \theta \cos \theta)^2 \\ &&&= (\sin 2 \theta)^2 = \sin^2 2 \theta \\ \\ && u_2 & = 4u_1 (1-u_1) \\ &&&= 4 \sin^2 2\theta \cos^2 2 \theta \\ &&&= \sin^2 4 \theta \end{align*} Claim: \(u_n = \sin^2 2^n \theta\). Proof: (By Induction) Base case is clear, suppose it's true for \(n=k\), then \begin{align*} && u_{k+1} &= 4u_k(1-u_k) \\ &&&= 4 \sin^2 2^k \theta(1-\sin^2 2^k \theta) \\ &&&= (2 \sin 2^k \theta \cos 2^k \theta)^2 \\ &&&= (\sin 2^{k+1} \theta)^2 \\ &&&= \sin^2 2^{k+1} \theta \end{align*} Therefore since it is true for \(n = 1\) and if it's true for \(n = k\) it is true for \(n=k+1\) it must be true for all \(k\).
2. Suppose \(v_n = \alpha u_n + \beta\) then \begin{align*} && (\alpha u_{n+1}+\beta) &= -p(\alpha u_n + \beta)^2 + q(\alpha u_n + \beta) + r \\ &&&= -p\alpha^2u_n^2+\alpha(q-2p\beta) u_n -p \beta^2 +q \beta+r \\ \Rightarrow && u_{n+1} &= u_n(q-2p\beta -p \alpha u_n) -(p\beta^2-(q-1)\beta-r) \end{align*} So if \(\alpha = \frac{4}{p}\) and \(q-2p\beta = 4\) ie \(\beta = \frac{q-4}{2p}\) then we also need the constant term to vanish, ie \begin{align*} 0 &&&= p\beta^2-(q-1)\beta+r \\ &&&= p \left (\frac{q-4}{2p} \right)^2 - (q-1) \frac{q-4}{2p} - r \\ \Rightarrow && 0 &= p(q-4)^2 -(q-1)(q-4)2p - 4p^2r \\ \Rightarrow && 0 &= (q-4)^2-2(q-1)(q-4)-4pr \\ &&&= q^2-8q+16-2q^2+10q-8-4pr \\ \Rightarrow && 4pr &= -q^2+2q+8 \end{align*} Suppose \(v_{n+1} = -v_n^2 + 2v_n +2\) then since \(4\cdot 1 \cdot 2 = 8\) and \(8 + 4 -4 = 8\) we can apply our method. \(v_n = 4u_n + \frac{-2}{2} = 4u_n -1 = 4\sin^2 (2^{n-1} \pi)-1\)

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: \begin{align*} \text{W.E.P.}: && \text{change in energy} &= \text{work done on particle} \\ \Rightarrow && \underbrace{\frac12mv^2}_{\text{speed before hitting barrier}} - \underbrace{\frac12mu^2}_{\text{speed leaving first barrier}} &= \underbrace{\left( -\mu mg \right)}_{F} \cdot \underbrace{d}_{d} \\ \Rightarrow && v^2 &= v_i^2-2\mu gd \end{align*} Newton's experimental law tells us that the speed leaving the barrier will be \(r\) times the speed approaching, ie \begin{align*} && v_{i+1} &= rv \\ \Rightarrow && v_{i+1}^2 &= r^2 v^2 \\ &&&= r^2v_i^2 - 2r^2\mu gd \\ \Rightarrow && v_{i+1}^2 - r^2v_i^2 &= - 2r^2\mu gd \end{align*} It must be the case that after \(n+1\) collisions the speed is zero, ie \(v_{n+1}^2 = 0\). Not that we can consider \(w_i = \frac{v_i^2}{2\mu gd}\) and we have the recurrence: \begin{align*} && w_{i+1} &=r^2w_i -r^2 \\ \end{align*} Looking at this we have a linear recurrence with a constant term, so let's try \(w_i = C\), then \begin{align*} && C &= r^2 C - r^2 \\ \Rightarrow && C &= \frac{-r^2}{1-r^2} \\ \end{align*} So \(w_i = Ar^{2i} - \frac{r^2}{1-r^2}\). \(w_0 = k \Rightarrow A = k+\frac{r^2}{1-r^2}\) Therefore \(w_n = \left (k+\frac{r^2}{1-r^2} \right)r^{2n} - \frac{r^2}{1-r^2}\) Suppose \(w_n = 0\) then, \begin{align*} && 0 &= \left (k+\frac{r^2}{1-r^2} \right)r^{2n} - \frac{r^2}{1-r^2} \\ \Rightarrow && r^{2n} &= \frac{r^2}{1-r^2} \frac{1}{k+\frac{r^2}{1-r^2}} \\ &&&= \frac{r^2}{k(1-r^2)+r^2} \\ \Rightarrow && 2n \ln r &= 2\ln r - \ln[k(1-r^2)+r^2] \\ \Rightarrow && n &= 1 - \frac1{2\ln r} \ln[k(1-r^2)+r^2)] \end{align*} If \(r = e^{-1}\) then \(\ln r = -1\) \begin{align*} && n &= 1 + \frac12 \ln [k(1-e^{-2}) + e^{-2}] \\ &&&= 1 + \frac12 \ln [e^{-2}(k(e^2-1)+1)] \\ &&&= 1 + \frac12 \ln e^{-2} + \frac12 \ln [1+k(e^2-1)] \\ &&&= \frac12 \ln [1+k(e^2-1)] \end{align*} If \(r = 1\) the recurrence becomes: \(w_{i+1} = w_i - 1\), so \(w_i = k-n\), so we have \(k\) collisions.