Problems

Let \(f(x) = 7 - 2|x|\). A sequence \(u_0, u_1, u_2, \ldots\) is defined by \(u_0 = a\) and \(u_n = f(u_{n-1})\) for \(n > 0\).

1. 1. Sketch, on the same axes, the graphs with equations \(y = f(x)\) and \(y = f(f(x))\).
   2. Find all solutions of the equation \(f(f(x)) = x\).
   3. Find the values of \(a\) for which the sequence \(u_0, u_1, u_2, \ldots\) has period 2.
   4. Show that, if \(a = \frac{28}{5}\), then the sequence \(u_2, u_3, u_4, \ldots\) has period 2, but neither \(u_0\) or \(u_1\) is equal to either of \(u_2\) or \(u_3\).
2. 1. Sketch, on the same axes, the graphs with equations \(y = f(x)\) and \(y = f(f(f(x)))\).
   2. Consider the sequence \(u_0, u_1, u_2, \ldots\) in the cases \(a = 1\) and \(a = -\tfrac79\). Hence find all the solutions of the equation \(f(f(f(x))) = x\).
   3. Find a value of \(a\) such that the sequence \(u_3, u_4, u_5, \ldots\) has period 3, but where none of \(u_0, u_1\) or \(u_2\) is equal to any of \(u_3, u_4\) or \(u_5\).

1. Show that, for any functions \(f\) and \(g\), and for any \(m \geq 0\), $$\sum_{r=1}^{m+1} f(r)\sum_{s=r-1}^m g(s) = \sum_{s=0}^m g(s)\sum_{r=1}^{s+1} f(r)$$
2. The random variables \(X_0, X_1, X_2, \ldots\) are defined as follows:
   • \(X_0\) takes the value \(0\) with probability \(1\);
   • \(X_{n+1}\) takes the values \(0, 1, \ldots, X_n + 1\) with equal probability, for \(n = 0, 1, \ldots\)
   1. Write down \(E(X_1)\). Find \(P(X_2 = 0)\) and \(P(X_2 = 1)\) and show that \(P(X_2 = 2) = \frac{1}{6}\). Hence calculate \(E(X_2)\).
   2. For \(n \geq 1\), show that $$P(X_n = 0) = \sum_{s=0}^{n-1} \frac{P(X_{n-1} = s)}{s+2}$$ and find a similar expression for \(P(X_n = r)\), for \(r = 1, 2, \ldots, n\).
   3. Hence show that \(E(X_n) = \frac{1}{2}(1 + E(X_{n-1}))\). Find an expression for \(E(X_n)\) in terms of \(n\), for \(n = 1, 2, \ldots\)

In this question, you need not consider issues of convergence.

1. The sequence \(T_n\), for \(n = 0, 1, 2, \ldots\), is defined by \(T_0 = 1\) and, for \(n \geqslant 1\), by \[ T_n = \frac{2n-1}{2n}\,T_{n-1}. \] Prove by induction that \[ T_n = \frac{1}{2^{2n}}\binom{2n}{n}, \] for \(n = 0, 1, 2, \ldots\). [Note that \(\dbinom{0}{0} = 1\).]
2. Show that in the binomial series for \((1-x)^{-\frac{1}{2}}\), \[ (1-x)^{-\frac{1}{2}} = \sum_{r=0}^{\infty} a_r x^r, \] successive coefficients are related by \[ a_r = \frac{2r-1}{2r}\,a_{r-1} \] for \(r = 1, 2, \ldots\)\,. Hence prove that \(a_r = T_r\) for all \(r = 0, 1, 2, \ldots\)\,.
3. Let \(b_r\) be the coefficient of \(x^r\) in the binomial series for \((1-x)^{-\frac{3}{2}}\), so that \[ (1-x)^{-\frac{3}{2}} = \sum_{r=0}^{\infty} b_r x^r. \] By considering \(\dfrac{b_r}{a_r}\), find an expression involving a binomial coefficient for \(b_r\), for \(r = 0, 1, 2, \ldots\)\,.
4. By considering the product of the binomial series for \((1-x)^{-\frac{1}{2}}\) and \((1-x)^{-1}\), prove that \[ \frac{(2n+1)}{2^{2n}}\binom{2n}{n} = \sum_{r=0}^{n} \frac{1}{2^{2r}}\binom{2r}{r}, \] for \(n = 1, 2, \ldots\)\,.

1. The sequence \(x_n\) for \(n = 0, 1, 2, \ldots\) is defined by \(x_0 = 1\) and by \[x_{n+1} = \frac{x_n + 2}{x_n + 1}\] for \(n \geqslant 0\).
   1. Explain briefly why \(x_n \geqslant 1\) for all \(n\).
   2. Show that \(x_{n+1}^2 - 2\) and \(x_n^2 - 2\) have opposite sign, and that \[\left|x_{n+1}^2 - 2\right| \leqslant \tfrac{1}{4}\left|x_n^2 - 2\right|\,.\]
   3. Show that \[2 - 10^{-6} \leqslant x_{10}^2 \leqslant 2\,.\]
2. The sequence \(y_n\) for \(n = 0, 1, 2, \ldots\) is defined by \(y_0 = 1\) and by \[y_{n+1} = \frac{y_n^2 + 2}{2y_n}\] for \(n \geqslant 0\).
   1. Show that, for \(n \geqslant 0\), \[y_{n+1} - \sqrt{2} = \frac{(y_n - \sqrt{2})^2}{2y_n}\] and deduce that \(y_n \geqslant 1\) for \(n \geqslant 0\).
   2. Show that \[y_n - \sqrt{2} \leqslant 2\left(\frac{\sqrt{2}-1}{2}\right)^{2^n}\] for \(n \geqslant 1\).
   3. Using the fact that \[\sqrt{2} - 1 < \tfrac{1}{2}\,,\] or otherwise, show that \[\sqrt{2} \leqslant y_{10} \leqslant \sqrt{2} + 10^{-600}\,.\]

The sequence \(F_n\), for \(n = 0, 1, 2, \ldots\), is defined by \(F_0 = 0\), \(F_1 = 1\) and by \(F_{n+2} = F_{n+1} + F_n\) for \(n \geqslant 0\). Prove by induction that, for all positive integers \(n\), \[\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \mathbf{Q}^n,\] where the matrix \(\mathbf{Q}\) is given by \[\mathbf{Q} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.\]

1. By considering the matrix \(\mathbf{Q}^n\), show that \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) for all positive integers \(n\).
2. By considering the matrix \(\mathbf{Q}^{m+n}\), show that \(F_{m+n} = F_{m+1}F_n + F_m F_{n-1}\) for all positive integers \(m\) and \(n\).
3. Show that \(\mathbf{Q}^2 = \mathbf{I} + \mathbf{Q}\). In the following parts, you may use without proof the Binomial Theorem for matrices: \[(\mathbf{I} + \mathbf{A})^n = \sum_{k=0}^{n} \binom{n}{k} \mathbf{A}^k.\]
   1. Show that, for all positive integers \(n\), \[F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_k\,.\]
   2. Show that, for all positive integers \(n\), \[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} 2^k F_k\] and also that \[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} F_{n+k}\,.\]
   3. Show that, for all positive integers \(n\), \[\sum_{k=0}^{n} (-1)^{n+k} \binom{n}{k} F_{n+k} = 0\,.\]

A sequence \(u_n\), where \(n = 1, 2, \ldots\), is said to have \emph{degree} \(d\) if \(u_n\), as a function of \(n\), is a polynomial of degree \(d\).

1. Show that, in any sequence \(u_n\) \((n = 1, 2, \ldots)\) that satisfies \(u_{n+1} = \frac{1}{2}(u_{n+2} + u_n)\) for all \(n \geqslant 1\), there is a constant difference between successive terms. Deduce that any sequence \(u_n\) for which \(u_{n+1} = \frac{1}{2}(u_{n+2} + u_n)\), for all \(n \geqslant 1\), has degree at most 1.
2. The sequence \(v_n\) \((n = 1, 2, \ldots)\) satisfies \(v_{n+1} = \frac{1}{2}(v_{n+2} + v_n) - p\) for all \(n \geqslant 1\), where \(p\) is a non-zero constant. By writing \(v_n = t_n + pn^2\), show that the sequence \(v_n\) has degree 2. Given that \(v_1 = v_2 = 0\), find \(v_n\) in terms of \(n\) and \(p\).
3. The sequence \(w_n\) \((n = 1, 2, \ldots)\) satisfies \(w_{n+1} = \frac{1}{2}(w_{n+2} + w_n) - an - b\) for all \(n \geqslant 1\), where \(a\) and \(b\) are constants with \(a \neq 0\). Show that the sequence \(w_n\) has degree 3. Given that \(w_1 = w_2 = 0\), find \(w_n\) in terms of \(n\), \(a\) and \(b\).

The Fibonacci numbers are defined by \(F_0 = 0\), \(F_1 = 1\) and, for \(n \geqslant 0\), \(F_{n+2} = F_{n+1} + F_n\).

1. Prove that \(F_r \leqslant 2^{r-n} F_n\) for all \(n \geqslant 1\) and all \(r \geqslant n\).
2. Let \(S_n = \displaystyle\sum_{r=1}^{n} \frac{F_r}{10^r}\). Show that \[\sum_{r=1}^{n} \frac{F_{r+1}}{10^{r-1}} - \sum_{r=1}^{n} \frac{F_r}{10^{r-1}} - \sum_{r=1}^{n} \frac{F_{r-1}}{10^{r-1}} = 89S_n - 10F_1 - F_0 + \frac{F_n}{10^n} + \frac{F_{n+1}}{10^{n-1}}\,.\]
3. Show that \(\displaystyle\sum_{r=1}^{\infty} \frac{F_r}{10^r} = \frac{10}{89}\) and that \(\displaystyle\sum_{r=7}^{\infty} \frac{F_r}{10^r} < 2 \times 10^{-6}\). Hence find, with justification, the first six digits after the decimal point in the decimal expansion of \(\dfrac{1}{89}\).
4. Find, with justification, a number of the form \(\dfrac{r}{s}\) with \(r\) and \(s\) both positive integers less than \(10000\) whose decimal expansion starts \[0.0001010203050813213455\ldots\,.\]

1. Show that, for \(n = 2, 3, 4, \ldots\), \[ \frac{d^2}{dt^2}\bigl[t^n(1-t)^n\bigr] = n\,t^{n-2}(1-t)^{n-2}\bigl[(n-1) - 2(2n-1)t(1-t)\bigr]. \]
2. The sequence \(T_0, T_1, \ldots\) is defined by \[ T_n = \int_0^1 \frac{t^n(1-t)^n}{n!}\,e^t\,dt. \] Show that, for \(n \geqslant 2\), \[ T_n = T_{n-2} - 2(2n-1)T_{n-1}. \]
3. Evaluate \(T_0\) and \(T_1\) and deduce that, for \(n \geqslant 0\), \(T_n\) can be written in the form \[ T_n = a_n + b_n e, \] where \(a_n\) and \(b_n\) are integers (which you should not attempt to evaluate).
4. Show that \(0 < T_n < \dfrac{e}{n!}\) for \(n \geqslant 0\). Given that \(b_n\) is non-zero for all~\(n\), deduce that \(\dfrac{-a_n}{b_n}\) tends to \(e\) as \(n\) tends to infinity.

A train has \(n\) seats, where \(n \geqslant 2\). For a particular journey, all \(n\) seats have been sold, and each of the \(n\) passengers has been allocated a seat. The passengers arrive one at a time and are labelled \(T_1, \ldots, T_n\) according to the order in which they arrive: \(T_1\) arrives first and \(T_n\) arrives last. The seat allocated to \(T_r\) (\(r = 1, \ldots, n\)) is labelled \(S_r\). Passenger \(T_1\) ignores their allocation and decides to choose a seat at random (each of the \(n\) seats being equally likely). However, for each \(r \geqslant 2\), passenger \(T_r\) sits in \(S_r\) if it is available or, if \(S_r\) is not available, chooses from the available seats at random.

1. Let \(P_n\) be the probability that, in a train with \(n\) seats, \(T_n\) sits in \(S_n\). Write down the value of \(P_2\) and find the value of \(P_3\).
2. Explain why, for \(k = 2, 3, \ldots, n-1\), \[ \mathrm{P}\bigl(T_n \text{ sits in } S_n \mid T_1 \text{ sits in } S_k\bigr) = P_{n-k+1}, \] and deduce that, for \(n \geqslant 3\), \[ P_n = \frac{1}{n}\Biggl(1 + \sum_{r=2}^{n-1} P_r\Biggr). \]
3. Give the value of \(P_n\) in its simplest form and prove your result by induction.
4. Let \(Q_n\) be the probability that, in a train with \(n\) seats, \(T_{n-1}\) sits in \(S_{n-1}\). Determine \(Q_n\) for \(n \geqslant 2\).

1. A game for two players, \(A\) and \(B\), can be won by player \(A\), with probability \(p_A\), won by player \(B\), with probability \(p_B\), where \(0 < p_A + p_B < 1\), or drawn. A match consists of a series of games and is won by the first player to win a game. Show that the probability that \(A\) wins the match is \[ \frac{p_A}{p_A + p_B}. \]
2. A second game for two players, \(A\) and \(B\), can be won by player \(A\), with probability~\(p\), or won by player \(B\), with probability \(q = 1 - p\). A match consists of a series of games and is won by the first player to have won two more games than the other. Show that the match is won after an even number of games, and that the probability that \(A\) wins the match is \[ \frac{p^2}{p^2 + q^2}. \]
3. A third game, for only one player, consists of a series of rounds. The player starts the game with one token, wins the game if they have four tokens at the end of a round and loses the game if they have no tokens at the end of a round. There are two versions of the game. In the cautious version, in each round where the player has any tokens, the player wins one token with probability \(p\) and loses one token with probability \(q = 1 - p\). In the bold version, in each round where the player has any tokens, the player's tokens are doubled in number with probability \(p\) and all lost with probability \(q = 1 - p\). In each of the two versions of the game, find the probability that the player wins. Hence show that the player is more likely to win in the cautious version if \(1 > p > \tfrac{1}{2}\) and more likely to win in the bold version if \(0 < p < \tfrac{1}{2}\).

1. Let \(\displaystyle I_n = \int_0^{\beta} (\sec x + \tan x)^n \, dx\), where \(n\) is a non-negative integer and \(0 < \beta < \dfrac{\pi}{2}\). For \(n \geqslant 1\), show that \[ \tfrac{1}{2}(I_{n+1} + I_{n-1}) = \frac{1}{n}\bigl[(\sec\beta + \tan\beta)^n - 1\bigr]. \] Show also that \[ I_n < \frac{1}{n}\bigl[(\sec\beta + \tan\beta)^n - 1\bigr]. \]
2. Let \(\displaystyle J_n = \int_0^{\beta} (\sec x \cos\beta + \tan x)^n \, dx\), where \(n\) is a non-negative integer and \(0 < \beta < \dfrac{\pi}{2}\). For \(n \geqslant 1\), show that \[ J_n < \frac{1}{n}\bigl[(1 + \tan\beta)^n - \cos^n\beta\bigr]. \]

A sequence \(x_1, x_2, \ldots\) of real numbers is defined by \(x_{n+1} = x_n^2 - 2\) for \(n \geqslant 1\) and \(x_1 = a\).

1. Show that if \(a > 2\) then \(x_n \geqslant 2 + 4^{n-1}(a-2)\).
2. Show also that \(x_n \to \infty\) as \(n \to \infty\) if and only if \(|a| > 2\).
3. When \(a > 2\), a second sequence \(y_1, y_2, \ldots\) is defined by \[ y_n = \frac{Ax_1 x_2 \cdots x_n}{x_{n+1}}, \] where \(A\) is a positive constant and \(n \geqslant 1\). Prove that, for a certain value of \(a\), with \(a > 2\), which you should find in terms of \(A\), \[ y_n = \frac{\sqrt{x_{n+1}^2 - 4}}{x_{n+1}} \] for all \(n \geqslant 1\). Determine whether, for this value of \(a\), the second sequence converges.

A sequence \(u_1, u_2, \ldots, u_n\) of positive real numbers is said to be unimodal if there is a value \(k\) such that \[u_1 \leqslant u_2 \leqslant \ldots \leqslant u_k\] and \[u_k \geqslant u_{k+1} \geqslant \ldots \geqslant u_n.\] So the sequences \(1, 2, 3, 2, 1\);\ \(1, 2, 3, 4, 5\);\ \(1, 1, 3, 3, 2\) and \(2, 2, 2, 2, 2\) are all unimodal, but \(1, 2, 1, 3, 1\) is not. A sequence \(u_1, u_2, \ldots, u_n\) of positive real numbers is said to have property \(L\) if \(u_{r-1}u_{r+1} \leqslant u_r^2\) for all \(r\) with \(2 \leqslant r \leqslant n-1\).

1. Show that, in any sequence of positive real numbers with property \(L\), \[u_{r-1} \geqslant u_r \implies u_r \geqslant u_{r+1}.\] Prove that any sequence of positive real numbers with property \(L\) is unimodal.
2. A sequence \(u_1, u_2, \ldots, u_n\) of real numbers satisfies \(u_r = 2\alpha u_{r-1} - \alpha^2 u_{r-2}\) for \(3 \leqslant r \leqslant n\), where \(\alpha\) is a positive real constant. Prove that, for \(2 \leqslant r \leqslant n\), \[u_r - \alpha u_{r-1} = \alpha^{r-2}(u_2 - \alpha u_1)\] and, for \(2 \leqslant r \leqslant n-1\), \[u_r^2 - u_{r-1}u_{r+1} = (u_r - \alpha u_{r-1})^2.\] Hence show that the sequence consists of positive terms and is unimodal, provided \(u_2 > \alpha u_1 > 0\). In the case \(u_1 = 1\) and \(u_2 = 2\), prove by induction that \(u_r = (2-r)\alpha^{r-1} + 2(r-1)\alpha^{r-2}\). Let \(\alpha = 1 - \dfrac{1}{N}\), where \(N\) is an integer with \(2 \leqslant N \leqslant n\). In the case \(u_1 = 1\) and \(u_2 = 2\), prove that \(u_r\) is largest when \(r = N\).

A coin is tossed repeatedly. The probability that a head appears is \(p\) and the probability that a tail appears is \(q = 1 - p\).

1. A and B play a game. The game ends if two successive heads appear, in which case A wins, or if two successive tails appear, in which case B wins. Show that the probability that the game never ends is \(0\). Given that the first toss is a head, show that the probability that A wins is \(\dfrac{p}{1 - pq}\). Find and simplify an expression for the probability that A wins.
2. A and B play another game. The game ends if three successive heads appear, in which case A wins, or if three successive tails appear, in which case B wins. Show that \[\mathrm{P}(\text{A wins} \mid \text{the first toss is a head}) = p^2 + (q + pq)\,\mathrm{P}(\text{A wins} \mid \text{the first toss is a tail})\] and give a similar result for \(\mathrm{P}(\text{A wins} \mid \text{the first toss is a tail})\). Show that \[\mathrm{P}(\text{A wins}) = \frac{p^2(1-q^3)}{1-(1-p^2)(1-q^2)}.\]
3. A and B play a third game. The game ends if \(a\) successive heads appear, in which case A wins, or if \(b\) successive tails appear, in which case B wins, where \(a\) and \(b\) are integers greater than \(1\). Find the probability that A wins this game. Verify that your result agrees with part (i) when \(a = b = 2\).

For non-negative integers \(a\) and \(b\), let \[ \mathrm{I}(a,b) = \int_0^{\frac{\pi}{2}} \cos^a x \cos bx \; \mathrm{d}x. \]

1. Show that for positive integers \(a\) and \(b\), \[ \mathrm{I}(a,b) = \frac{a}{a+b} \, \mathrm{I}(a-1, b-1). \]
2. Prove by induction on \(n\) that for non-negative integers \(n\) and \(m\), \[ \int_0^{\frac{\pi}{2}} \cos^n x \cos(n+2m+1)x \; \mathrm{d}x = (-1)^m \frac{2^n \, n! \, (2m)! \, (n+m)!}{m! \, (2n+2m+1)!}. \]