Problems

Filters
Clear Filters

8 problems found

2025 Paper 3 Q2
D: 1500.0 B: 1500.0
modulus function sequences recurrence relation curve sketching periodic sequences iterated functions fixed points piecewise linear

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. 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\).
    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\).

Solution:

    1. TikZ diagram
    2. If \(a = 1\) then \(u_1 = f(a) = 7-2 = 5\), \(u_2 = f(5) = -3\), \(u_3 = f(-3) = 7-6 = 1\). Therefore it must be the case that \(f(f(f(x))) = x\) for \(x = 1, 5, -3\). Similarly, if \(a = -\tfrac79\) then \(u_1 = f(-\tfrac79) = \tfrac{49}{9}\), \(u_2 = f(\tfrac{49}{9}) = -\tfrac{35}{9}\) and \(u_3 = f(-\tfrac{35}{9}) = -\tfrac79\). Therefore we must also have roots \(x = -\tfrac79, \tfrac{49}{9}, -\tfrac{35}9\). We also have the roots \(x = -7, \tfrac73\) from the first part so we have found all \(8\) roots.
    3. We need \(f(f(f(x))) = 1\) but \(f(f(x)) \neq -3, f(x) \neq 5, x \neq 1\). Suppose \(f(y) = 1 \Rightarrow 7-2|y| = 1 \Rightarrow y = \pm 3\). So \(y = 3\), ie \(f(f(x)) = 3\). Suppose \(f(z) = 3 \Rightarrow 7-2|z| = 3 \Rightarrow z = \pm 2\). Finally we need \(f(x) = \pm 2\), so say \(7-2|x| = 2 \Rightarrow x = \tfrac52\), so we have the sequence \(\tfrac52, 2, 3, 1, 5, -3, 1, \cdots\)as required.

View
2019 Paper 2 Q5
D: 1500.0 B: 1500.0
sequences recurrence relation fixed points quadratic period 2 proof inequality proof by contradiction

The sequence \(u_0, u_1, \ldots\) is said to be a constant sequence if \(u_n = u_{n+1}\) for \(n = 0, 1, 2, \ldots\). The sequence is said to be a sequence of period 2 if \(u_n = u_{n+2}\) for \(n = 0, 1, 2, \ldots\) and the sequence is not constant.

  1. A sequence of real numbers is defined by \(u_0 = a\) and \(u_{n+1} = f(u_n)\) for \(n = 0, 1, 2, \ldots\), where $$f(x) = p + (x - p)x,$$ and \(p\) is a given real number. Find the values of \(a\) for which the sequence is constant. Show that the sequence has period 2 for some value of \(a\) if and only if \(p > 3\) or \(p < -1\).
  2. A sequence of real numbers is defined by \(u_0 = a\) and \(u_{n+1} = f(u_n)\) for \(n = 0, 1, 2, \ldots\), where $$f(x) = q + (x - p)x,$$ and \(p\) and \(q\) are given real numbers. Show that there is no value of \(a\) for which the sequence is constant if and only if \(f(x) > x\) for all \(x\). Deduce that, if there is no value of \(a\) for which the sequence is constant, then there is no value of \(a\) for which the sequence has period 2. Is it true that, if there is no value of \(a\) for which the sequence has period 2, then there is no value of \(a\) for which the sequence is constant?

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.

View
2016 Paper 2 Q12
D: 1600.0 B: 1503.2
probability principle of inclusion-exclusion derangements combinatorics proof fixed points permutations

Starting with the result \(\P(A\cup B) = \P(A)+P(B) - \P(A\cap B)\), prove that \[ \P(A\cup B\cup C) = \P(A)+\P(B)+\P(C) - \P(A\cap B) - \P(B\cap C) - \P(C \cap A) + \P(A\cap B\cap C) \,. \] Write down, without proof, the corresponding result for four events \(A\), \(B\), \(C\) and \(D\). A pack of \(n\) cards, numbered \(1, 2, \ldots, n\), is shuffled and laid out in a row. The result of the shuffle is that each card is equally likely to be in any position in the row. Let \(E_i\) be the event that the card bearing the number \(i\) is in the \(i\)th position in the row. Write down the following probabilities:

  1. \(\P(E_i)\);
  2. \(\P(E_i\cap E_j)\), where \(i\ne j\);
  3. \(\P(E_i\cap E_j\cap E_k)\), where \(i\ne j\), \(j\ne k\) and \(k\ne i\).
Hence show that the probability that at least one card is in the same position as the number it bears is \[ 1 - \frac 1 {2!} + \frac 1{3!} - \cdots + (-1)^{n+1} \frac 1 {n!}\,. \] Find the probability that exactly one card is in the same position as the number it bears

Solution: \begin{align*} && \mathbb{P}(A \cup B \cup C) &= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cup B) \cap C) \tag{applying with \(A\cup B\) and \(C\)} \\ &&&= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \tag{applying with \(A\) and \(B\)}\\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \left ( \mathbb{P}(A \cap C) +\mathbb{P}(B \cap C) - \mathbb{P}( (A \cap C) \cap (B \cap C) )\right) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) +\mathbb{P}(C)- \mathbb{P}(A\cap B)- \mathbb{P}(A \cap C) -\mathbb{P}(B \cap C)+\mathbb{P}( A \cap B \cap C) \end{align*} \[ \mathbb{P}(A_1 \cup A_2 \cup A_3 \cup A_4) = \sum_i \mathbb{P}(A_i) - \sum_{i \neq j} \mathbb{P}(A_i \cap A_j) + \sum_{i \neq j \neq j} \mathbb{P}(A_i \cap A_j \cap A_k) - \mathbb{P}(A_1 \cap A_2 \cap A_3 \cap A_4) \]

  1. \(\mathbb{P}(E_i) = \frac{1}{n}\)
  2. \(\mathbb{P}(E_i \cap E_j) = \frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}\)
  3. \(\mathbb{P})(E_i \cap E_j \cap E_k) = \frac{1}{n(n-1)(n-2)}\)
First notice that the probability that \(k\) (or more) cards are in the correct place is \(\frac{(n-k)!}{n!}\) (place the other \(n-k\) cards in any order. We are interested in: \begin{align*} \mathbb{P} \left ( \bigcup_{i=1}^n E_i \right) &= \sum_{i} \mathbb{P}(E_i) - \sum_{i \neq j} \mathbb{P}(E_i \cap E_j) + \sum_{i \neq j \neq k} \mathbb{P}(E_i \cap E_j \cap E_k) - \cdots \\ &= \sum_i \frac1n - \sum_{i\neq j} \frac{1}{n(n-1)} + \sum_{i \neq j \neq k} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \sum_{i_1 \neq i_2 \neq \cdots \neq i_k} \frac{(n-k)!}{n!} + \cdots\\ &= 1 - \binom{n}{2} \frac{1}{n(n-1)} + \binom{n}{3} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \binom{n}{k} \frac{(n-k)}{n!} + \cdots \\ &= 1 - \frac12 + \frac1{3!} - \cdots + (-1)^{k+1} \frac{n!}{k!(n-k)!} \frac{(n-k)!}{n!} + \cdots \\ &= 1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n+1} \frac{1}{n!} \end{align*} The probability exactly one card is in the right place is the probability none of the other \(n-1\) are in the right place, which is: \(\frac1n \left (1 - \left (1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n} \frac{1}{(n-1)!} \right) \right)\) but there are also \(n\) cards we can choose to be the card in the right place, hence \(\frac{1}{2!} - \frac{1}{3!} + \cdots +(-1)^n \frac{1}{(n-1)!}\)

View
2008 Paper 2 Q1
D: 1600.0 B: 1500.7
sequences recurrence relation complex numbers fixed points periodic sequences simultaneous equations quadratic equations

A sequence of points \((x_1,y_1)\), \((x_2,y_2)\), \(\ldots\) in the cartesian plane is generated by first choosing \((x_1,y_1)\) then applying the rule, for \(n=1\), \(2\), \(\ldots\), \[ (x_{n+1}, y_{n+1}) = (x_n^2-y_n^2 +a, \; 2x_ny_n+b+2)\,, \] where \(a\) and \(b\) are given real constants.

  1. In the case \(a=1\) and \(b=-1\), find the values of \((x_1,y_1)\) for which the sequence is constant.
  2. Given that \((x_1,y_1) = (-1,1)\), find the values of \(a\) and \(b\) for which the sequence has period 2.

View
2006 Paper 2 Q1
D: 1600.0 B: 1485.5
sequences recurrence relation convergence periodic sequence quadratic equation fixed points proof by induction inequality

The sequence of real numbers \(u_1\), \(u_2\), \(u_3\), \(\ldots\) is defined by \begin{equation*} u_1=2 \,, \qquad\text{and} \qquad u_{n+1} = k - \frac{36}{u_n} \quad \text{for } n\ge1, \tag{\(*\)} \end{equation*} where \(k\) is a constant.

  1. Determine the values of \(k\) for which the sequence \((*)\) is: (a) constant; (b) periodic with period 2; (c) periodic with period 4.
  2. In the case \(k=37\), show that \(u_n\ge 2\) for all \(n\). Given that in this case the sequence \((*)\) converges to a limit \(\ell\), find the value of \(\ell\).

View
2004 Paper 1 Q8
D: 1500.0 B: 1547.8
sequences recurrence relation convergence proof by induction inequality strictly increasing quadratic recurrence fixed points

A sequence \(t_0\), \(t_1\), \(t_2\), \(...\) is said to be strictly increasing if \(t_{n+1} > t_n\) for all \(n\ge{0}\,\).

  1. The terms of the sequence \(x_0\,\), \(x_1\,\), \(x_2\,\), \(\ldots\) satisfy $$ \ds x_{n+1}=\frac{x_n^2 +6}{5} $$ for \(n\ge{0}\,\). Prove that if \(x_0 > 3\) then the sequence is strictly increasing.
  2. The terms of the sequence \(y_0\,\), \(y_1\,\), \(y_2\,\), \(\ldots\) satisfy $$ \ds y_{n+1}= 5-\frac 6 {y_n} $$ for \(n\ge{0}\,\). Prove that if \(2 < y_0 < 3\) then the sequence is strictly increasing but that \(y_n<3\) for all \(n\,\).

Solution:

  1. Suppose \(x_n> 3\) then \begin{align*} && x_{n+1} &= \frac{x_n^2+9-3}{5} \\ &&& \geq \frac{2\sqrt{x_n^2 \cdot 9} - 3}{5} \\ &&&= \frac{6x_n -3}{5} = x_n + \frac{x_n-3}{5} \\ &&&> x_n > 3 \end{align*} Therefore if \(x_i > 3 \Rightarrow x_{i+1} > x_i\) and \(x_{i+1} > 3\) so by induction \(x_n\) strictly increasing for all \(n\).
  2. Suppose \(2 < y_n < 3\) then \begin{align*} && y_{n+1} &= 5 - \frac6{y_n} \\ &&&< 5 - \frac63 = 3 \\ \\ && y_{n+1} &= 5 - \frac4{y_n} - \frac{2}{y_n} \\ \\ &&&= y_n + 5 - \frac{2}{y_n} - \left ( y_n + \frac4{y_n} \right) \\ &&&\geq y_n + 5 - \frac{2}{y_n} - 2\sqrt{y_n \frac{4}{y_n}} \\ &&&= y_n + 1 - \frac{2}{y_n} \\ &&&> y_n \end{align*} Therefore if \(y_n \in (2,3)\) we have \(y_{n+1} \in ( y_n, 3)\) and so \(y_n\) is strictly increasing and bounded.

View
2002 Paper 2 Q5
D: 1600.0 B: 1495.1
proof by induction recurrence relation sequences quadratic logistic map fixed points periodic orbits inequality

The numbers \(x_n\), where \(n=0\), \(1\), \(2\), \(\ldots\) , satisfy \[ x_{n+1} = kx_n(1-x_n) \;. \]

  1. Prove that, if \(0 < k < 4\) and \(0 < x_0 < 1\), then \(0 < x_n < 1\) for all \(n\,\).
  2. Given that \(x_0=x_1=x_2 = \cdots =a\,\), with \(a\ne0\) and \(a\ne1\), find \(k\) in terms of \(a\,\).
  3. Given instead that \(x_0=x_2=x_4 = \cdots = a\,\), with \(a\ne0\) and \(a\ne1\), show that \(ab^3 -b^2 +(1-a)=0\), where \(b=k(1-a)\,\). Given, in addition, that \(x_1 \ne a\), find the possible values of \(k\) in terms of \(a\,\).

Solution:

  1. Consider \(f(x) = x(1-x) = x - x^2 = \tfrac14 - (x - \tfrac12)^2\) which is clearly in \((0,\tfrac14)\) when \(x \in (0,1)\), therefore if \(0 < k < 4\) then \(f(x) \in (0, 1)\) and so by induction \(x_n \in (0,1)\).
  2. Suppose \(a = g(a)\) then \(a = ka(1-a) \Rightarrow 1 = k(1-a) \Rightarrow k = \frac{1}{1-a}\) (since \(a \neq 0, 1\))
  3. If \(g(g(a)) = a\) then \begin{align*} && a &= kg(a)(1-g(a)) \\ &&&= k^2a(1-a)(1-ka(1-a)) \\ &&&= -k^3a^2(1-a)^2 + k^2a(1-a) \\ \Rightarrow && 1 &= -k^3a(1-a)^2 + k^2(1-a) \\ \Rightarrow && 1-a &= -k^3a(1-a)^3+k^2(1-a)^2 \\ \Rightarrow && 1-a &= -ab^3+b^2 \\ \Rightarrow && 0 &= ab^3-b^2+(1-a) \end{align*} Note that \begin{align*} && 0 &= ab^3-b^2+(1-a) \\ &&&= (b-1)(ab^2-(1-a)b - (1-a)) \end{align*} and since \(b \neq 1\) (otherwise \(x_2 =0\) which is a contradiction) we must have \(b = \frac{1-a \pm \sqrt{(1-a)^2+4a(1-a)}}{2a} = \frac{1-a\pm \sqrt{1+2a-3a^2}}{2a}\) and so \(k = \frac{b}{1-a} = \frac{1-a \pm \sqrt{1+2a-3a^2}}{2a(1-a)}\)

View
1996 Paper 3 Q8
D: 1700.0 B: 1516.0
simultaneous equations Möbius transformation inverse function composition of functions fixed points quadratic equation rational function domain and range

A transformation \(T\) of the real numbers is defined by \[ y=T(x)=\frac{ax-b}{cx-d}\,, \] where \(a,b,c\), \(d\) are real numbers such that \(ad\neq bc\). Find all numbers \(x\) such that \(T(x)=x.\) Show that the inverse operation, \(x=T^{-1}(y)\) expressing \(x\) in terms of \(y\) is of the same form as \(T\) and find corresponding numbers \(a',b',c'\),\(d'\). Let \(S_{r}\) denote the set of all real numbers excluding \(r\). Show that, if \(c\neq0,\) there is a value of \(r\) such that \(T\) is defined for all \(x\in S_{r}\) and find the image \(T(S_{r}).\) What is the corresponding result if \(c=0\)? If \(T_{1},\) given by numbers \(a_{1},b_{1},c_{1},d_{1},\) and \(T_{2},\) given by numbers \(a_{2},b_{2},c_{2},d_{2}\) are two such transformations, show that their composition \(T_{3},\) defined by \(T_{3}(x)=T_{2}(T_{1}(x)),\) is of the same form. Find necessary and sufficient conditions on the numbers \(a,b,c,d\) for \(T^{2}\), the composition of \(T\) with itself, to be the identity. Hence, or otherwise, find transformations \(T_{1},T_{2}\) and their composition \(T_{3}\) such that \(T_{1}^{2}\) and \(T_{2}^{2}\) are each the identity but \(T_{3}^{2}\) is not.

View