Problems

Filters
Clear Filters

3 problems found

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
2004 Paper 1 Q7
D: 1500.0 B: 1500.0
generalised binomial theorem recurrence relation power series partial fractions generating function geometric series linear recurrence

  1. The function \(\f(x)\) is defined for \(\vert x \vert < \frac15\) by \[ \f(x) = \sum_{n=0}^\infty a_n x^n\;, \] where \(a_0=2\), \(a_1=7\) and \(a_n =7a_{n-1} - 10a_{n-2}\) for \(n\ge{2}\,\). Simplify \(\f(x) - 7x\f(x) + 10x^2\f(x)\,\), and hence show that \(\displaystyle\f(x) = {1\over 1-2x} + {1 \over 1-5x} \;\). Hence show that \(a_n=2^n + 5^n\,\).
  2. The function \(\g(x)\) is defined for \(\vert x \vert < \frac13\) by \[ \g(x) = \sum_{n=0}^\infty b_n x^n \;, \] where \(b_0=5\,\), \(b_1 =10 \,\), \(b_2=40\,\), \(b_3=100\) and \(b_n = pb_{n-1} + qb_{n-2}\) for \(n\ge{2}\,\). Obtain an expression for \(\g(x)\) as the sum of two algebraic fractions and determine \(b_n\) in terms of \(n\).

Solution:

  1. \begin{align*} && f(x) -7xf(x)+10x^2f(x) &= \sum_{n=0}^\infty a_n x^n - 7x \sum_{n=0}^{\infty} a_n x^n + 10x^2 \sum_{n=0}^{\infty} a_nx^n \\ &&&= \sum_{n=2}^\infty (a_n-7a_{n-1}+10a_{n-2})x^n + a_0+a_1x-7a_0x \\ &&&= 0 + 2-7x \\ \\ \Rightarrow && f(x) &= \frac{2-7x}{1-7x+10x^2} \\ &&&= \frac{2-7x}{(1-5x)(1-2x)} \\ &&&= \frac{1}{1-2x} + \frac{1}{1-5x} \\ &&&= \sum_{n=0}^{\infty} (2^n + 5^n)x^n \end{align*} Therefore \(a_n = 2^n +5^n\)
  2. \(\,\) \begin{align*} && 40 &= 10p + 5 q \\ && 100 &= 40p+10q \\ && 10 &= 4p + q \\ \Rightarrow && (p,q) &= (1,6) \\ \\ && g(x) -xg(x)-6x^2g(x) &= 5+5x \\ \Rightarrow && g(x) &= \frac{5+5x}{1-x-6x^2} \\ &&&= \frac{5+5x}{(1-3x)(1+2x)} \\ &&&= \frac{4}{1-3x} + \frac{1}{1+2x} \\ &&&= \sum_{n=0}^{\infty} (4 \cdot 3^n + (-2)^n)x^n \\ \Rightarrow && b_n &= 4 \cdot 3^n + (-2)^n \end{align*}

View
1988 Paper 3 Q15
D: 1700.0 B: 1486.2
sequences recurrence relation probability expectation particular integral linear recurrence combinatorics

Each day, books returned to a library are placed on a shelf in order of arrival, and left there. When a book arrives for which there is no room on the shelf, that book and all books subsequently returned are put on a trolley. At the end of each day, the shelf and trolley are cleared. There are just two-sizes of book: thick, requiring two units of shelf space; and thin, requiring one unit. The probability that a returned book is thick is \(p\), and the probability that it is thin is \(q=1-p.\) Let \(M(n)\) be the expected number of books that will be put on the shelf, when the length of the shelf is \(n\) units and \(n\) is an integer, on the assumption that more books will be returned each day than can be placed on the shelf. Show, giving reasoning, that

  1. \(M(0)=0;\)
  2. \(M(1)=q;\)
  3. \(M(n)-qM(n-1)-pM(n-2)=1,\) for \(n\geqslant2.\)
Verify that a possible solution to these equations is \[ M(n)=A(-p)^{n}+B+Cn, \] where \(A,B\) and \(C\) are numbers independent of \(n\) which you should express in terms of \(p\).

Solution:

  1. \(M(0) = 0\) since if there's no space on the shelf, we wont be able to put any books on the shelf.
  2. If the shelf has length \(1\) it can only fit a thin book. For a thin book to be placed on the shelf, the very first book which comes to be placed must be thin. But this happens with probability \(q\). Therefore \(M(1) = q\).
  3. Suppose no books have been placed on the shelf, then with probability \(p\) a large book gets placed on the shelf, and the expected number of books to be placed on the shelf is equivalent to how many books will be placed on the shelf if the shelf only had \(n-2\) spaces. This is \(M(n-2)\). Similar if the book which arrives first is thin (with probability \(q\)) then there will be \(M(n-1)\) more books placed on the shelf in expectation. We've just added \(1\) more book, therefore \(M(n) = 1+pM(n-2) + qM(n-1)\) or rearranging \(M(n) - qM(n-1) - pM(n-2) = 1\).
Suppose \(M(n) = (-p)^n\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= (-p)^n - (1-p)(-p)^n - p(-p)^{n-2} \\ &= (-p)^{n-2}(p^2+(1-p)p-p) \\ &= 0 \end{align*} Suppose \(M(n) = B\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= B - (1-p)B - pB \\ &= 0 \end{align*} Finally, if \(M(n) = Cn\) notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= Cn - (1-p)C(n-1) - pC(n-2) \\ &= C(n(1-(1-p)+p)+(1-p)+2p) \\ &= C(1+p) \end{align*} Therefore if \(C = \frac{1}{1+p}\) we have that: \(M(n) = A(-p)^n + B + Cn\) satisfies our recurrence. We also need \(M(0) = 0\) and \(M(1) = q\) \begin{align*} 0 &= M(0) \\ &= A + B \\ 1-p &= M(1) \\ &= -pA+B \end{align*} \((1+p)A = p-1 \Rightarrow A = \frac{p-1}{1+p}, B = \frac{1-p}{1+p}\). Therefore: \[ M(n) = -\frac{1-p}{1+p}(-p)^n + \frac{1-p}{1+p} + \frac{n}{1+p} \] is a possible solution to this equation

View