Problems

Filters
Clear Filters

70 problems found

2015 Paper 3 Q2
D: 1700.0 B: 1529.7
proof sequences inequality counterexample eventually dominates exponential vs polynomial logical reasoning

If \(s_1\), \(s_2\), \(s_3\), \(\ldots\) and \(t_1\), \(t_2\), \(t_3\), \(\ldots\) are sequences of positive numbers, we write \[ (s_n)\le (t_n) \] to mean

"there exists a positive integer \(m\) such that \(s_n \le t_n\) whenever \(n\ge m\)".
Determine whether each of the following statements is true or false. In the case of a true statement, you should give a proof which includes an explicit determination of an appropriate \(m\); in the case of a false statement, you should give a counterexample.
  1. \((1000n) \le (n^2)\,\).
  2. If it is not the case that \((s_n)\le (t_n)\), then it is the case that \((t_n)\le (s_n)\,\).
  3. If \((s_n)\le (t_n)\) and \((t_n) \le (u_n)\), then \((s_n)\le (u_n)\,\).
  4. \((n^2)\le (2^n)\,\).

Solution:

  1. If \(m = 1000\), then \(n \geq m \Rightarrow n^2 \geq 1000n \Rightarrow (1000n) \leq (n^2)\)
  2. This is false. Let \(s_i = 1,2,1,2,\cdots\) and \(t_i = 2,1,2,1,\cdots\).
  3. Suppose that for \(n \geq m_1, s_n \le t_n\) and for \(n \geq m_2, s_t \le u_n\), then for \(n \geq m = \max(m_1, m_2), s_n \leq t_n \leq u_n \Rightarrow s_n \leq u_n \Rightarrow (s_n) \leq (u_n)\)
  4. Let \(m = 6\), then if \(n \geq m, 2^n \geq 1 + n + \frac{n(n-1)}{2} + \frac{n(n-1)}{2} + n + 1 = n^2 + n + 2 \geq n^2\), so \((2^n) \geq (n^2)\)

View
2014 Paper 1 Q6
D: 1500.0 B: 1474.3
trigonometry recurrence relation proof by induction double angle formula substitution sequences sin² quadratic recurrence

  1. The sequence of numbers \(u_0, u_1, \ldots \) is given by \(u_0=u\) and, for \(n\ge 0\), \begin{equation} u_{n+1} =4u_n(1- u_n)\,. \tag{\(*\)} \end{equation} In the case \(u= \sin^2\theta\) for some given angle \(\theta\), write down and simplify expressions for \(u_1\) and \(u_2\) in terms of \(\theta\). Conjecture an expression for \(u_n\) and prove your conjecture.
  2. The sequence of numbers \(v_0, v_1, \ldots\) is given by $v_0= v \text{ and, for }n\ge 0$, \[ v_{n+1} = -pv_n^2 +qv_n +r\,, \] where \(p\), \(q\) and \(r\) are given numbers, with \(p\ne0\). Show that a substitution of the form \(v_n =\alpha u_n +\beta\), where \(\alpha\) and \(\beta\) are suitably chosen, results in the sequence \((*)\) provided that \[ 4pr = 8 +2q -q^2 \,. \] Hence obtain the sequence satisfying \(v_0=1\) and, for \(n\ge0\), \(v_{n+1} = -v_n^2 +2 v_n +2 \,\).

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

View
2014 Paper 3 Q8
D: 1700.0 B: 1516.0
sequences series convergence inequality harmonic series bounding sums decreasing function geometric grouping divergence decimal representation

The numbers \(f(r)\) satisfy \(f(r)>f(r+1)\) for $r=1, 2, \dots\(. Show that, for any non-negative integer \)n$, \[ k^n(k-1) \, f(k^{n+1}) \le \sum_{r=k^n}^{k^{n+1}-1}f(r) \le k^n(k-1)\, f(k^n)\, \] where \(k\) is an integer greater than 1.

  1. By taking \(f(r) = 1/r\), show that \[ \frac{N+1}2 \le \sum_{r=1}^{2^{N+1}-1} \frac1r \le N+1 \,. \] Deduce that the sum \(\displaystyle \sum_{r=1}^\infty \frac1r\) does not converge.
  2. By taking \(f(r)= 1/r^3\), show that \[ \sum_{r=1}^\infty \frac1 {r^3} \le 1 \tfrac 13 \,. \]
  3. Let \(S(n)\) be the set of positive integers less than \(n\) which do not have a \(2\) in their decimal representation and let \(\sigma(n)\) be the sum of the reciprocals of the numbers in \(S(n)\), so for example \(\sigma(5) = 1+\frac13+\frac14\). Show that \(S(1000)\) contains \(9^3-1\) distinct numbers. Show that \(\sigma (n) < 80\) for all \(n\).

Solution: \begin{align*} && \sum_{r=k^n}^{k^{n+1}-1} f(r) &\leq \sum_{r=k^n}^{k^{n+1}-1} f(k^{n}) \\ &&&= (k^{n+1}-k^n)f(k^n) \\ &&&= k^n(k-1)f(k^n) \\ \\ && \sum_{r=k^n}^{k^{n+1}-1} f(r) &\geq \sum_{r=k^n}^{k^{n+1}-1} f(k^{n+1}) \\ &&&= (k^{n+1}-k^n)f(k^{n+1}) \\ &&&= k^n(k-1)f(k^{n+1}) \\ \end{align*}

  1. Notice that if \(f(r) = 1/r\) then \(f(r) > f(r+1)\) so we can apply our lemma, ie \begin{align*} &&&2^N(2-1) \frac{1}{2^{N+1}} &\leq & \sum_{r=2^N}^{2^{N+1}-1} \frac1r &\leq&\quad 2^N(2-1) \frac{1}{2^{N}} \\ \Leftrightarrow &&& \frac12 &\leq & \sum_{r=2^N}^{2^{N+1}-1} \frac1r &\leq&\quad 1 \\ \Rightarrow &&& \frac12+\frac12+\cdots+\frac12 &\leq & \underbrace{\sum_{r=2^0}^{2^{0+1}-1} \frac1r+\sum_{r=2^1}^{2^{1+1}-1} \frac1r+\cdots+\sum_{r=2^N}^{2^{N+1}-1} \frac1r}_{N+1 \text{ terms}} &\leq&\quad 1 +1+\cdots+1\\ \Rightarrow &&& \frac{N+1}{2} &\leq & \underbrace{\sum_{r=1}^{2^{N+1}-1} \frac1r}_{N+1 \text{ terms}} &\leq&\quad N+1 \end{align*} Therefore the sum \(\displaystyle \sum_{r=1}^{2^{N+1}-1} \frac1r\) is always greater than \(N+1\) and in particular we can find an upper limit such that it is always bigger than any value, ie it diverges.
  2. If \(f(r) = 1/r^3\) then we have \begin{align*} && \sum_{r=2^N}^{2^{N+1}-1} \frac1{r^3} &\leq 2^N(2-1) \frac{1}{2^{3N}} \\ &&&= \frac{1}{4^N} \\ \Rightarrow && \sum_{r=2^0}^{2^{0+1}-1} \frac1{r^3} +\sum_{r=2^1}^{2^{1+1}-1} \frac1{r^3} +\sum_{r=2^N}^{2^{N+1}-1} \frac1{r^3} &\leq 1 + \frac14 + \cdots + \frac1{4^N} \\ \Rightarrow && \sum_{r=1}^{\infty} \frac1{r^3} &\leq 1 + \frac14 + \cdots \\ &&&= \frac{1}{1-\frac14} = \frac43 = 1\tfrac13 \end{align*}
  3. To count the number of numbers less than \(1000\) without a \(2\) in their decimal representation we can count the number of \(3\) digit numbers (where \(0\) is an acceptable leading digit) which don't contain a \(2\) and remove \(0\). There are \(9\) choices for each digit, so \(9^3-1\). Notice this is true for \(10^N\) for any \(N\), ie \(S(10^N) = 9^N-1\). Notice also that we can now write: \begin{align*} && \sum_{r=10^N }^{10^{N+1}-1} \frac{1}{r} \mathbb{1}_{r \in S} & < \frac{1}{10^{N+1}}\#\{\text{number not containing a }2\} \\ &&&= \frac{1}{10^{N+1}}((9^{N+1}-1)-(9^N-1)) \\ &&&= \frac{9^N}{10^N}(9-1) \\ &&&= 8 \cdot \left (\frac9{10} \right)^N \\ \\ \Rightarrow && \sum_{r=1}^{\infty} \frac{1}{r} \mathbb{1}_{r \in S} &< 8\left ( 1 + \frac9{10} + \cdots \right) \\ &&&= 8 \frac{1}{1-\frac{9}{10}} = 80 \end{align*}

View
2013 Paper 1 Q3
D: 1500.0 B: 1500.0
vectors binary operation associativity geometric proof sequences convex combination line segment division algebraic manipulation

For any two points \(X\) and \(Y\), with position vectors \(\bf x\) and \(\bf y\) respectively, \(X*Y\) is defined to be the point with position vector \(\lambda {\bf x}+ (1-\lambda){\bf y}\), where \(\lambda\) is a fixed number.

  1. If \(X\) and \(Y\) are distinct, show that \(X*Y\) and \(Y*X\) are distinct unless \(\lambda\) takes a certain value (which you should state).
  2. Under what conditions are \((X*Y)*Z\) and \(X*(Y*Z)\,\) distinct?
  3. Show that, for any points \(X\), \(Y\) and \(Z\), \[ (X*Y)*Z = (X*Z)*(Y*Z)\, \] and obtain the corresponding result for \(X*(Y*Z)\).
  4. The points \(P_1\), \(P_2\), \(\ldots\) are defined by \( P_1 = X*Y\) and, for \(n \ge2\), \(P_n= P_{n-1}*Y\,.\) Given that \(X\) and \(Y\) are distinct and that \(0<\lambda<1\), find the ratio in which \(P_n\) divides the line segment \(XY\).

Solution:

  1. Suppose \(X*Y = Y*X\), then \begin{align*} && X * Y &= \lambda \mathbf{x} + (1-\lambda) \mathbf{y} \\ && Y * X &= \lambda \mathbf{y} + (1-\lambda) \mathbf{x}\\ \Rightarrow && 0 &= (2\lambda - 1)(\mathbf{x} -\mathbf{y}) \end{align*} Therefore, either \(\mathbf{x} = \mathbf{y}\) or \(\lambda = \frac12\). Since we assumed \(X,Y\) were distinct, \(\mathbf{x} \neq \mathbf{y}\) and so \(X*Y\) and \(Y*X\) are distinct unless \(\lambda = \frac12\)
  2. Suppose \((X*Y)*Z = X*(Y*Z)\) \begin{align*} &&(X*Y)*Z &= (\lambda \mathbf{x} + (1-\lambda) \mathbf{y}) * \mathbf{z} \\ &&&= (\lambda^2 \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda)\mathbf{z}\\ &&X*(Y*Z) &=\mathbf{x}* (\lambda \mathbf{y} + (1-\lambda) \mathbf{z}) \\ &&&= (\lambda \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda)^2\mathbf{z}\\ \Rightarrow && 0 &= (\lambda^2 - \lambda)\mathbf{x} + ((1-\lambda) - (1-\lambda)^2)\mathbf{z} \\ &&&=(1-\lambda)(-\lambda \mathbf{x} +\lambda \mathbf{z}) \\ &&&= \lambda(1-\lambda)(\mathbf{z}-\mathbf{x}) \end{align*} Therefore they are distinct unless \(\lambda = 1, 0\) or \(\mathbf{x} = \mathbf{z}\).
  3. Claim: \((X*Y)*Z = (X*Z)*(Y*Z)\) Proof: \begin{align*} && (X*Y)*Z &= (\lambda \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda)^2\mathbf{z} \\ && (X*Z)*(Y*Z) &= (\lambda \mathbf{x} + (1-\lambda)\mathbf{z}) * (\lambda \mathbf{y} + (1-\lambda)\mathbf{z}) \\ &&&= \lambda(\lambda \mathbf{x} + (1-\lambda)\mathbf{z}) + (1-\lambda)(\lambda \mathbf{y} + (1-\lambda)\mathbf{z}) \\ &&&= \lambda^2 \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda) \mathbf{z} \end{align*} Claim: \(X*(Y*Z) = (X*Y)*(X*Z)\) Proof: \begin{align*} X*(Y*Z) &= \lambda \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda)^2\mathbf{z} \\ (X*Y)*(X*Z) &= (\lambda \mathbf{x} + (1-\lambda)\mathbf{y})*(\lambda \mathbf{x} + (1-\lambda)\mathbf{z}) \\ &= \lambda (\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) + (1-\lambda)(\lambda \mathbf{x} + (1-\lambda)\mathbf{z}) \\ &= \lambda \mathbf{x} + \lambda(1-\lambda)\mathbf{y} + (1-\lambda)^2\mathbf{z} \end{align*}
  4. \(P_1 = X*Y\) divides the line segment into the ratio \(\lambda:(1-\lambda)\). \(P_n\) divides the line segment \(P_{n-1}Y\) into the ratio \(\lambda:(1-\lambda)\), therefore it divides the line segment \(XY\) in the ratio \(\lambda^n : 1- \lambda^n\) Alternatively, \begin{align*} P_1 &= \lambda \mathbf{x} + (1-\lambda)\mathbf{y} \\ P_2 &= (\lambda \mathbf{x} + (1-\lambda)\mathbf{y} )*\mathbf{y} \\ &= \lambda^2 \mathbf{x} + (1-\lambda^2) \mathbf{y} \end{align*} Suppose \(P_k = \lambda^k\mathbf{x} + (1-\lambda^k)\mathbf{y}\) then \begin{align*}P_{k+1} &= (\lambda^k\mathbf{x} + (1-\lambda^k)\mathbf{y}) * \mathbf{y} \\ &= \lambda^{k+1}\mathbf{x} + \lambda(1-\lambda^k)\mathbf{y} + (1-\lambda)\mathbf{y}\\ & = \lambda^{k+1}\mathbf{x} + (1-\lambda^{k+1})\mathbf{y}\end{align*}

View
2013 Paper 2 Q6
D: 1600.0 B: 1485.5
sequences recurrence relation convergence bounded and monotone proof by induction golden ratio subsequences fixed point

In this question, the following theorem may be used. Let \(u_1\), \(u_2\), \(\ldots\) be a sequence of (real) numbers. If the sequence is bounded above (that is, \(u_n\le b\) for all \(n\), where \(b\) is some fixed number) and increasing (that is, \(u_n \ge u_{n-1}\) for all \(n\)), then the sequence tends to a limit (that is, converges). The sequence \(u_1\), \(u_2\), \(\ldots\) is defined by \(u_1=1\) and \[ u_{n+1} = 1+\frac 1{u_n} \ \ \ \ \ \ \ \ \ \ (n\ge1)\,. \tag{\(*\)} \]

  1. Show that, for \(n\ge3\), \[ u_{n+2}-u_n = \frac{u_{n} - u_{n-2}}{(1+u_n)(1+u_{n-2})} . \]
  2. Prove, by induction or otherwise, that \(1\le u_n \le 2\) for all \(n\).
  3. Show that the sequence \(u_1\), \(u_3\), \(u_5\), \(\ldots\) tends to a limit, and that the sequence \(u_2\), \(u_4\), \(u_6\), \(\ldots\) tends to a limit. Find these limits and deduce that the sequence \(u_1\), \(u_2\), \(u_3\), \(\ldots\,\) tends to a limit. Would this conclusion change if the sequence were defined by \((*)\) and \(u_1=3\)?

Solution:

  1. \(\,\) \begin{align*} && u_{n+2} - u_n &= 1 + \frac{1}{u_{n+1}} - \left (1 + \frac{1}{u_{n-1}} \right) \\ &&&= \frac{1}{1 + \frac1{u_n}} - \frac{1}{1 + \frac{1}{u_{n-2}}} \\ &&&= \frac{u_n}{u_n+1} - \frac{u_{n-2}}{1+u_{n-2}} \\ &&&= \frac{u_n(1+u_{n-2}) - u_{n-2}(1+u_n)}{(1+u_n)(1+u_{n-2})} \\ &&&= \frac{u_n - u_{n-2}}{(1+u_n)(1+u_{n-2})} \end{align*}
  2. Claim: \(u_n \in [1,2]\) Proof: (By induction). Note that \(u_1 = 1, u_2 = 2\) so our claim is true for the first few terms. Note that if \(u_n \in [1,2]\), \(\frac{1}{u_n} \in [\tfrac12, 1]\) and \(1+\frac{1}{u_{n}} \in [\tfrac32,2] \subset [1,2]\). Therefore \(u_{n+1} \in [1,2]\). Therefore since \(u_1 \in [1,2]\) and \(u_n \in [1,2] \Rightarrow u_{n+1} \in [1,2]\) \(u_n \in [1,2]\) for all \(n \ge 1\)
  3. First notice that \(u_3 = \frac32 > u_1\) and therefore by the recursion we found in the first part, \(u_{2n+1}-u_{2n-1} > 0\) so \(u_{2k+1}\) is increasing and bounded, and so by our theorem converges to a limit. Suppose this limit is \(L\), then we must have \(L = 1 + \frac1{L} \Rightarrow L^2 - L - 1 = 0 \Rightarrow L = \frac{1+\sqrt5}{2}\) since it must be in \([1,2]\). Similarly, not that \(u_4 = \frac{5}{3} < u_2\) and so \(u_{2k+2} - u_{2k} < 0\) and \(-u_{2k}\) is increasing and bounded above. Therefore it tends to a limit (and so does \(u_{2k}\)). By the same reasoning as before, it's the same limit, \(\frac{1+\sqrt5}{2}\) and therefore the sequence converges. If \(u_1 = 3, u_2 = \frac43 \in [1,2]\) so we have our sequence being bounded and all the same logic will follow through.

View
2013 Paper 2 Q13
D: 1600.0 B: 1516.0
probability geometric distribution biased coin runs inequality sequences combinatorial probability

A biased coin has probability \(p\) of showing a head and probability \(q\) of showing a tail, where \(p\ne0\), \(q\ne0\) and \(p\ne q\). When the coin is tossed repeatedly, runs occur. A straight run of length \(n\) is a sequence of \(n\) consecutive heads or \(n\) consecutive tails. An alternating run of length \(n\) is a sequence of length \(n\) alternating between heads and tails. An alternating run can start with either a head or a tail. Let \(S\) be the length of the longest straight run beginning with the first toss and let \(A\) be the length of the longest alternating run beginning with the first toss.

  1. Explain why \(\P(A=1)=p^2+q^2\) and find \(\P(S=1)\). Show that \(\P(S=1)<\P(A=1)\).
  2. Show that \(\P(S=2)= \P(A=2)\) and determine the relationship between \(\P(S=3)\) and \( \P(A=3)\).
  3. Show that, for \(n>1\), \(\P(S=2n)>\P(A=2n)\) and determine the corresponding relationship between \(\P(S=2n+1)\) and \(\P(A=2n+1)\). [You are advised not to use \(p+q=1\) in this part.]

Solution:

  1. The only way \(A = 1\) is if we get \(HH\) or \(TT\) which has probability \(p^2+q^2\). The only way we get \(S=1\) is if we have \(HT\) to \(TH\), ie \(2pq\). Since \((p-q)^2 = p^2 + q^2 - 2pq >0\) we must have \(\mathbb{P}(A=1) > \mathbb{P}(S=1)\).
  2. \(\,\) \begin{align*} \mathbb{P}(S=2) &= p^2q + q^2p \\ \mathbb{P}(A=2) &= pq^2 + qp^2 = \mathbb{P}(S=2) \\ \\ \mathbb{P}(S=3) &= p^3q + q^3p = pq(p^2+q^2) \\ \mathbb{P}(A=3) &= pqp^2 + qpq^2 = pq(p^2+q^2) = \mathbb{P}(S=3) \end{align*}
  3. For \(n > 1\) we must have \begin{align*} && \mathbb{P}(S = 2n) &= p^{2n}q + q^{2n}p \\ && \mathbb{P}(A=2n) &= (pq)^{n}q + (qp)^{n}p \\ &&&= p^nq^{n+1} + q^np^{n+1} \\ && \mathbb{P}(S = 2n) &> \mathbb{P}(A = 2n) \\ \Leftrightarrow && p^{2n}q + q^{2n}p & > p^nq^{n+1} + q^np^{n+1}\\ \Leftrightarrow && 0 & < p^{2n}q+q^{2n}p - p^nq^{n+1} -q^np^{n+1}\\ &&&= (p^n-q^n)(qp^n - pq^n) \end{align*} which is clearly true. \begin{align*} && \mathbb{P}(S=2n+1) &= p^{2n+1}q + q^{2n+1}p \\ && \mathbb{P}(A=2n+1) &= (pq)^{n}p^2 + (qp)^{n}q^2 \\ &&&= p^{n+2}q^n + q^{n+2}p^n \end{align*} The same factoring logic shows that \(\mathbb{P}(S = 2n+1) > \mathbb{P}(A=2n+1)\)

View
2012 Paper 1 Q7
D: 1500.0 B: 1500.0
sequences recurrence relation periodic sequences algebraic manipulation factorisation simultaneous equations linear recurrence

A sequence of numbers \(t_0\), \(t_1\), \(t_2\), \(\ldots\,\) satisfies \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ t_{n+2} = p t_{n+1}+qt_{n} \ \ \ \ \ \ \ \ \ \ (n\ge0), \] where \(p\) and \(q\) are real. Throughout this question, \(x\), \(y\) and \(z\) are non-zero real numbers.

  1. Show that, if \(t_n=x\) for all values of \(n\), then \(p+q=1\) and \(x\) can be any (non-zero) real number.
  2. Show that, if \(t_{2n} = x\) and \(t_{2n+1}=y\) for all values of \(n\), then \(q\pm p=1\). Deduce that either \(x=y\) or \(x=-y\), unless \(p\) and \(q\) take certain values that you should identify.
  3. Show that, if \(t_{3n} = x\), \(t_{3n+1}=y\) and \(t_{3n+2}=z\) for all values of \(n\), then \[ p^3+q^3 +3pq-1=0\,. \] Deduce that either \(p+q=1\) or \((p-q)^2 +(p+1)^2+(q+1)^2=0\). Hence show that either \(x=y=z\) or \(x+y+z=0\).

Solution:

  1. Suppose \(t_n = x\) for all \(n\), then we must have \begin{align*} && x &= p x + q x \\ \Leftrightarrow && 1 &= p+q \end{align*} and this clearly works for any value of \(x\).
  2. Suppose \(t_{2n} = x, t_{2n+1} = y\) for all \(n\), then \begin{align*} && x &= py + q x \\ && y &= px + q y \\ \Rightarrow && 0 &= py + (q-1) x \\ && 0 &= px + (q-1) y \\ \Rightarrow && p &= (q-1) \frac{x}{y} = (q-1) \frac{y}{x} \\ \Rightarrow && \frac{y}{x} = \pm 1 & \text{ or } q = 1, p = 0 \\ \Rightarrow && y = \pm x & \text{ or } (p,q) = (0,1) \\ \end{align*}
  3. Suppose \(t_{3n} = x\), \(t_{3n+1}=y\) and \(t_{3n+2}=z\) , so \begin{align*} && x &= pz + qy \\ && y & = px + qz \\ && z &= py + qx \\ \\ && z &= p(px+qz) + q(pz + qy) \\ &&&= p^2x + 2pqz + q^2 y \\ &&&= p^2(pz+qy) + 2pqz + q^2(px+qz) \\ &&&= p^3 z + p^2qy + 2pqz + q^2p x + q^3 z \\ &&&= (p^3+q^3+2pq)z + pq(py+qx) \\ &&&= (p^3 + q^3 + 2pq)z + pq z \\ &&&= (p^3 + q^3 + 3pq)z \\ \Rightarrow && 0 &= p^3 + q^3 + 3pq- 1 \\ &&&= (p+q-1)(p^2+q^2+1+p+q-pq) \\ &&&= \tfrac12(p+q-1)((p-q)^2+(p+1)^2+(q+1)^2) \end{align*} Therefore \(p+q = 1\) or \((p-q)^2+(p+1)^2+(q+1)^2 = 0 \Rightarrow p = q = -1\). If \(p+q = 1\), then \(z = py + (1-p)x\) and \(x = p(py+(1-p)x) + (1-p)y \Rightarrow (1-p+p^2)x = (1-p+p^2)y \Rightarrow x = y \Rightarrow x= y = z\). If \(p = q = -1\) then adding all the equations we get \(x + y + z = -2(x+y+z) \Rightarrow x + y + z = 0\)
Note that what is actually going on here is that solutions must be of the form \(t_n = \lambda^n\) so the only way to be constant is for \(\lambda = 1\) to be a root, the only way for it to be \(2\)-periodic is for \(\lambda = -1\) to be a root, and the only way for it to be \(3\)-periodic is for \(\lambda = 1, \omega, \omega^2\) to be the roots (although we see this via the classic \(x^3 + y^3 + z^3 - 3xyz = (x+y+z)(x + \omega y + \omega^2 z)(x+\omega^2 y +\omega z)\) which is because of the real constraint in the question.

View
2012 Paper 2 Q8
D: 1600.0 B: 1485.7
sequences recurrence relation inequality strictly increasing sequence algebraic manipulation second order recurrence quadratic recurrence

The positive numbers \(\alpha\), \(\beta\) and \(q\) satisfy \(\beta-\alpha >q\). Show that \[ \frac{\alpha^2+\beta^2 -q^2}{\alpha\beta}-2> 0\,. \] The sequence \(u_0\), \(u_1\), \(\ldots\) is defined by \(u_0=\alpha\), \(u_1=\beta\) and \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ u_{n+1} = \frac {u_{n}^2 -q^2}{u_{n-1}} \ \ \ \ \ \ \ \ \ \ \ (n\ge1), \] where \(\alpha\), \(\beta\) and \(q\) are given positive numbers (and \(\alpha\) and \(\beta\) are such that no term in the sequence is zero). Prove that \(u_n(u_n+u_{n+2}) = u_{n+1}(u_{n-1}+u_{n+1})\,\). Prove also that \[ u_{n+1} -pu_n + u_{n-1}=0 \] for some number \(p\) which you should express in terms of \(\alpha\), \(\beta\) and \(q\). Hence, or otherwise, show that if \(\beta> \alpha+q\), the sequence is strictly increasing (that is, \(u_{n+1}-u_n > 0\) for all \(n\)). Comment on the case \(\beta =\alpha +q\).

Solution: \begin{align*} && \beta - \alpha &> q \\ \Rightarrow &&(\beta - \alpha)^2 &> q^2 \\ \Rightarrow && \beta^2 +\alpha^2 - 2\beta \alpha &> q^2 \\ \Rightarrow && \alpha^2+\beta^2-q^2 -2 \beta \alpha &> 0 \\ \Rightarrow && \frac{\alpha^2+\beta^2-q^2}{\alpha\beta} - 2 &> 0 \end{align*} \begin{align*} && u_n(u_n+u_{n+2}) &= u_n \cdot \left (u_n + \frac {u_{n+1}^2 -q^2}{u_{n}}\right) \\ &&&= u_n^2 + u_{n+1}^2-q^2 \\ &&&= u_n^2 + u_{n+1}^2 - (u_n^2-u_{n-1}u_{n+1}) \\ &&&= u_{n+1}^2 + u_{n+1}u_{n-1} \\ &&&= u_{n+1}(u_{n-1}+u_{n+1}) \\ \\ && u_{n+1}-pu_n+u_{n-1} &= -pu_n+\frac{u_{n}(u_{n-2}+u_n)}{u_{n-1}} \\ &&&= \frac{u_n(u_{n}-pu_{n-1}+u_{n-2})}{u_{n-1}} \end{align*} Therefore if \(u_2 -pu_1 + u_0 = 0\) it is always zero, ie if \begin{align*} && u_2 &= p\beta - \alpha \\ && u_2 &= \frac{\beta^2-q^2}{\alpha} \\ \Rightarrow && \frac{\beta^2-q^2}{\alpha} &= p\beta - \alpha \\ \Rightarrow && p &= \frac{\alpha^2+\beta^2-q^2}{\alpha\beta} \end{align*} If \(\beta > \alpha + q\) we must have that \(p > 2\), and so \(u_{n+1}-u_n = (p-1)u_n - u_{n-1} > u_n-u_{n-1} > 0\), therefore the sequence is strictly increasing. If \(\beta = \alpha + q\) the sequence follows \(u_{n+1} - 2u_n + u_{n-1} =0\) and so \(u_{n+1}-u_n = u_n - u_{n-1}\) for all \(n\) (which is still increasing - it's an arithmetic progression with common difference \(\beta - \alpha\)).

View
2012 Paper 3 Q2
D: 1700.0 B: 1516.0
sequences infinite product telescoping logarithmic series partial fractions geometric series convergence proof by induction

In this question, \(\vert x \vert <1\) and you may ignore issues of convergence.

  1. Simplify \[ (1-x)(1+x)(1+x^2)(1+x^4) \cdots (1+x^{2^n})\,, \] where \(n\) is a positive integer, and deduce that \[ \frac1{1-x} = (1+x)(1+x^2)(1+x^4) \cdots (1+x^{2^n}) + \frac {x^{2^{n+1}}}{1-x}\,. \] Deduce further that \[ \ln(1-x) = - \sum_{r=0}^\infty \ln \left (1+ x ^{2^r}\right) \,, \] and hence that \[ \frac1 {1-x} = \frac 1 {1+x} + \frac {2x}{1+x^2} + \frac {4x^3}{1+x^4} +\cdots\,. \]
  2. Show that \[ \frac{1+2x}{1+x+x^2} = \frac{1-2x}{1-x+x^2} + \frac{2x-4x^3}{1-x^2+x^4} + \frac {4x^3-8x^7}{1-x^4+x^8} + \cdots\,. \]

Solution:

  1. \begin{align*} (1-x)&(1+x)(1+x^2)(1+x^4) \cdots (1+x^{2^n}) \\ &= (1-x^2)(1+x^2)(1+x^4) \cdots (1+x^{2^n}) \\ &= (1-x^4)(1+x^4) \cdots (1+x^{2^n}) \\ &= 1-x^{2^{n+1}} \\ \end{align*} Therefore, \begin{align*} && \frac{1}{1-x} - \frac{x^{2^{n+1}}}{1-x} &= (1+x)(1+x^2)\cdots(1+x^{2^n}) \\ \Rightarrow && \frac{1}{1-x} &=(1+x)(1+x^2)\cdots(1+x^{2^n})+ \frac{x^{2^{n+1}}}{1-x} \\ \Rightarrow && -\ln (1-x) &= \sum_{r=0}^{\infty} \ln (1+x^{2^r}) \\ \Rightarrow && \ln(1-x) &= - \sum_{r=0}^{\infty} \ln (1+x^{2^r}) \\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && \frac{1}{1-x} &= \sum_{r=0}^{\infty} \frac{2^r x^{2^r-1}}{1+x^{2^r}} \\ &&&= \frac{1}{1+x} + \frac{2x}{1+x^2} + \frac{4x^3}{1+x^4} + \cdots \end{align*}
  2. Consider \begin{align*}(1+x+x^2)&(1-x+x^2)(1-x^2+x^4)\cdots(1-x^{2^n}+x^{2^{n+1}}) \\ &= (1+x^2 + x^4)(1-x^2+x^4) \cdots (1-x^{2^n}+x^{2^{n+1}}) \\ &= (1-x^{2^{n+1}}+x^{2^{n+2}}) \\ \end{align*} Therefore, \begin{align*} && \frac{1}{1+x+x^2} &= (1-x+x^2)(1-x^2+x^4)\cdots(1-x^{2^n}+x^{2^{n+1}}) + \frac{x^{2^{n+1}}}{1+x+x^2} -\frac{x^{2^{n+2}}}{1+x+x^2} \\ \Rightarrow && -\ln(1+x+x^2) &= \sum_{r=0}^\infty \ln (1 - x^{2^r}+x^{2^{r+1}}) \\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && -\frac{1+2x}{1+x+x^2} &= \sum_{r=0}^{\infty} \frac{ -2^r x^{2^r-1}+2^{r+1}x^{2^{r+1}-1}}{1 - x^{2^r}+x^{2^{r+1}}} \\ &&&= \frac{-1+2x}{1-x+x^2}+\frac{-2x+4x^3}{1-x^2+x^4} + \frac{-4x^3+8x^7}{1-x^4+x^8} + \cdots \end{align*} Which is the desired result when we multiply both sides by \(-1\)

View
2012 Paper 3 Q8
D: 1700.0 B: 1500.0
sequences recurrence relation Fibonacci sequence proof by induction arctan telescoping series trigonometric identity

The sequence \(F_0\), \(F_1\), \(F_2\), \(\ldots\,\) is defined by \(F_0=0\), \(F_1=1\) and, for \(n\ge0\), \[ F_{n+2} = F_{n+1} + F_n \,. \]

  1. Show that \(F_0F_3-F_1F_2 = F_2F_5- F_3F_4\,\).
  2. Find the values of \(F_nF_{n+3} - F_{n+1}F_{n+2}\) in the two cases that arise.
  3. Prove that, for \(r=1\), \(2\), \(3\), \(\ldots\,\), \[ \arctan \left( \frac 1{F_{2r}}\right) =\arctan \left( \frac 1{F_{2r+1}}\right)+ \arctan \left( \frac 1{F_{2r+2}}\right) \] and hence evaluate the following sum (which you may assume converges): \[ \sum_{r=1}^\infty \arctan \left( \frac 1{F_{2r+1}}\right) \,. \]

View
2011 Paper 2 Q7
D: 1600.0 B: 1500.0
sequences geometric sequences summation algebraic manipulation surds recurrence relation telescoping quadratic identities

The two sequences \(a_0\), \(a_1\), \(a_2\), \(\ldots\) and \(b_0\), \(b_1\), \(b_2\), \(\ldots\) have general terms \[ a_n = \lambda^n +\mu^n \text { \ \ \ and \ \ \ } b_n = \lambda^n - \mu^n\,, \] respectively, where \(\lambda = 1+\sqrt2\) and \(\mu= 1-\sqrt2\,\).

  1. Show that $\displaystyle \sum_{r=0}^nb_r = -\sqrt2 + \frac 1 {\sqrt2} \,a_{\low n+1}\,$, and give a corresponding result for \(\displaystyle \sum_{r=0}^na_r\,\).
  2. Show that, if \(n\) is odd, $$\sum_{m=0}^{2n}\left( \sum_{r=0}^m a_{\low r}\right) = \tfrac12 b_{n+1}^2\,,$$ and give a corresponding result when \(n\) is even.
  3. Show that, if \(n\) is even, $$\left(\sum_{r=0}^na_r\right)^{\!2} -\sum_{r=0}^n a_{\low 2r+1} =2\,,$$ and give a corresponding result when \(n\) is odd.

View
2010 Paper 2 Q3
D: 1600.0 B: 1500.0
sequences Fibonacci sequence recurrence relation golden ratio simultaneous equations geometric series infinite series

The first four terms of a sequence are given by \(F_0=0\), \(F_1=1\), \(F_2=1\) and \(F_3=2\). The general term is given by \[ F_n= a\lambda^n+b\mu^n\,, \tag{\(*\)} \] where \(a\), \(b\), \(\lambda\) and \(\mu\) are independent of \(n\), and \(a\) is positive.

  1. Show that \(\lambda^2 +\lambda\mu+ \mu^2 = 2\), and find the values of \(\lambda\), \(\mu\), \(a\) and \(b\).
  2. Use \((*)\) to evaluate \(F_6\).
  3. Evaluate \(\displaystyle \sum_{n=0}^\infty \frac{F_n}{2^{n+1}}\,.\)

Solution:

  1. \(\,\) \begin{align*} && 0 &= a+b \tag{1}\\ && 1 &= a\lambda -a\mu \tag{2} \\ && 1 &= a\lambda^2 -a\mu^2 \tag{3} \\ && 2 &= a\lambda^3 - a\mu^3 \tag{4} \\ (4) \div (2): && 2 & = \lambda^2+\lambda \mu + \mu^2 \\ (3) \div (2): && 1 &= \lambda + \mu \\ \Rightarrow && 2 &= \lambda^2 + \lambda(1-\lambda) + (1-\lambda)^2 \\ &&&= \lambda^2-\lambda+1\\ \Rightarrow && \lambda, \mu &= \frac{1 \pm \sqrt{5}}{2} \\ \Rightarrow && a &= \frac{1}{\lambda - \mu} = \frac{1}{\sqrt{5}} \\ \Rightarrow && b &= -\frac{1}{\sqrt{5}} \end{align*} (NB: This is Binet's formula)
  2. \(\,\) \begin{align*} F_6 &= \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 +\sqrt{5}}{2} \right)^6- \left ( \frac{1 -\sqrt{5}}{2} \right)^6 \right) \\ &= \frac{1}{2^6 \sqrt{5}} \left ( (1+\sqrt{5})^6-(1-\sqrt{5})^6 \right) \\ &= \frac{1}{2^5 \cdot \sqrt{5}} \left (6 \sqrt{5} +\binom{6}{3} (\sqrt{5})^3+\binom{6}{5}(\sqrt{5})^5 \right)\\ &= \frac{1}{2^5} \left (6 +20\cdot 5+6\cdot 5^2 \right)\\ &= \frac{1}{2^5} 256 = 2^3 = 8 \end{align*} (way more painful than just computing it by adding terms!)
  3. \(\,\) \begin{align*} && \sum_{n=0}^{\infty} \frac{F_n}{2^{n+1}} &= \sum_{n=0}^{\infty} \frac{a\lambda^n + b\mu^n}{2^{n+1}} \\ &&&= \frac12 \left ( \frac{a}{1-\frac{\lambda}2} + \frac{b}{1-\frac{\mu}2} \right) \\ &&&= \frac12 \left ( \frac{2a}{2-\lambda} + \frac{2b}{2-\mu}\right) \\ &&&= \frac{2a}{4-2\lambda} + \frac{2b}{4-2\mu}\\ &&&= \frac{2a}{4-(1+\sqrt{5})} - \frac{2a}{4-(1-\sqrt{5})} \\ &&&= \frac{2}{3\sqrt{5}-5} - \frac{2}{3\sqrt{5}+5} \\ &&&= \frac{6\sqrt{5}+10-6\sqrt{5}+10}{45-25} \\ &&&= 1 \end{align*}

View
2009 Paper 2 Q6
D: 1600.0 B: 1516.0
sequences Fibonacci sequence recurrence relation inequality summation series bounds geometric series comparison test

The Fibonacci sequence \(F_1\), \(F_2\), \(F_3\), \(\ldots\) is defined by \(F_1=1\), \(F_2= 1\) and \[ F_{n+1} = F_n+F_{n-1} \qquad\qquad (n\ge 2). \] Write down the values of \(F_3\), \(F_4\), \(\ldots\), \(F_{10}\). Let \(\displaystyle S=\sum_{i=1}^\infty \dfrac1 {F_i}\,\).

  1. Show that \(\displaystyle \frac 1{F_i} > \frac1{2F_{i-1}}\,\) for \(i\ge4\) and deduce that \(S > 3\,\). Show also that \(S < 3\frac23\,\).
  2. Show further that \(3.2 < S < 3.5\,\).

Solution: \begin{array}{c|r} n & F_n \\ \hline 1 & 1 \\ 2 & 1 \\ 3 & 2 \\ 4 & 3 \\ 5 & 5 \\ 6 & 8 \\ 7 & 13 \\ 8 & 21 \\ 9 & 34 \\ 10 & 55 \end{array} \begin{questionparts} \item Claim: \(\frac1{F_i} > \frac1{2F_{i-1}}\) for \(i \geq 4\). Proof: Since \(F_i = F_{i-1}+F_{i-2}\) and \(F_i > 1\) for \(i \geq 1\) we have \(F_i > F_{i-1}\) for \(i \geq 3\). In particular we have \(F_i = F_{i-1}+F_{i-2} < 2F_{i-1}\) for \(i -1 \geq 3\) or \(i \geq 4\). Therefore \(\frac{1}{F_i} > \frac1{2F_{i-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
2008 Paper 3 Q2
D: 1700.0 B: 1555.2
sequences summation binomial theorem recurrence relation proof by induction polynomial power sums

Let \(S_k(n) \equiv \sum\limits_{r=0}^n r^k\,\), where \(k\) is a positive integer, so that \[ S_1(n) \equiv \tfrac12 n(n+1) \text{ and } S_2(n) \equiv \tfrac16 n(n+1)(2n+1)\,. \]

  1. By considering \(\sum\limits_{r=0}^n \left[ (r+1)^k-r^k\right]\, \), show that \[ kS_{k-1}(n)=(n+1)^k -(n+1) - \binom{k}{2} S_{k-2}(n) - \binom {k}{3} S_{k-3}(n) - \cdots - \binom{k}{k-1} S_{1}(n) \;. \tag{\(*\)} \] Obtain simplified expressions for \(S_3(n)\) and \(S_4(n)\).
  2. Explain, using \((*)\), why \(S_k(n)\) is a polynomial of degree \(k+1\) in \(n\). Show that in this polynomial the constant term is zero and the sum of the coefficients is 1.

Solution:

  1. \begin{align*} &&(n+1)^k &= \sum_{r=0}^n \left [ (r+1)^k - r^k \right] \\ &&&= \sum_{r=0}^n \left [ \left ( \binom{k}{0}r^k+\binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) - r^k\right] \\ &&&= \sum_{r=0}^n \left ( \binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) \\ &&&=k \sum_{r=0}^n r^{k-1} + \binom{k}{2}\sum_{r=0}^nr^{k-2} + \cdots + \binom{k}{k} \sum_{r=0}^n 1 \\ &&&= kS_{k-1}(n) + \binom{k}2 S_{k-2}(n) + \cdots +\binom{k}{k-1}S_1(n) + (n+1) \\ \Rightarrow && k S_{k-1}(n) &= (n+1)^k -(n+1) -\binom{k}2 S_{k-2}(n) - \cdots -\binom{k}{k-1}S_1(n) \\ && 4S_3(n) &= (n+1)^4-(n+1) - \binom{4}{2} \frac{n(n+1)(2n+1)}{6} - \binom{4}{3} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ( (n+1)^3-1 - n(2n+1)-2n \right) \\ &&&= (n+1) \left ( n^3+3n^2+3n+1-1 - 2n^2-3n \right) \\ &&&= (n+1) \left ( n^3+n^2 \right) \\ &&&= n^2(n+1)^2 \\ \Rightarrow && S_3(n) &= \frac{n^2(n+1)^2}{4} \\ \\ &&5S_4(n) &=(n+1)^5-(n+1) - \binom{5}{2} \frac{n^2(n+1)^2}4 - \binom{5}{3} \frac{n(n+1)(2n+1)}{6} - \binom{5}{4} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ((n+1)^4 - 1-\frac{5n^2(n+1)}{2} - \frac{5n(2n+1)}{3} -\frac{5n}{2}\right)\\ &&&= \frac{n+1}{6} \left (6(n+1)^4-6-15n^2(n+1)-10n(2n+1)-15n \right) \\ &&&= \frac{n+1}{6} \left (6n^4+24n^3+36n^2+24n+6 -6-15n^3-15n^2-20n^2-10n-15n\right) \\ &&&= \frac{n+1}{6} \left (6n^4+9n^3+n^2-n\right) \\ &&&= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{6} \\ \Rightarrow && S_4(n) &= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{30} \end{align*}
  2. Proceeding by induction, since \(S_k(n)\) is a polynomial of degree \(k+1\) for small \(k\), we can see that \[ (k+1)S_k(n) = \underbrace{(n+1)^{k+1}}_{\text{poly deg }=k+1} - \underbrace{(n+1)}_{\text{poly deg}=1} - \underbrace{\binom{k+1}{2}S_{k-1}(n)}_{\text{poly deg}=k} - \underbrace{\cdots}_{\text{polys deg}< k} - \underbrace{\binom{k+1}{k} S_1(n)}_{\text{poly deg}=1}\] therefore \(S_k(n)\) is a polynomial of degree \(k+1\) (in fact with leading coefficient \(\frac{1}{k+1}\). Since \(S_k(0) = \sum_{r=0}^{0} r^k = 0\) there is no constant term, and since \(S_k(1) = \sum_{r=0}^1 r^k = 1\) the sum of the coefficients is \(1\)

View