Problems

Filters
Clear Filters

8 problems found

2023 Paper 2 Q6
D: 1500.0 B: 1500.0
proof by induction fibonacci sequence matrix exponentiation recurrence relation binomial theorem determinant 2x2 matrices

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\,.\]

View
2016 Paper 1 Q8
D: 1500.0 B: 1530.6
generating functions generalised binomial theorem binomial series recurrence relation power series Fibonacci sequence partial fractions sequences

Given an infinite sequence of numbers \(u_0\), \(u_1\), \(u_2\), \(\ldots\,\), we define the generating function, \(\f\), for the sequence by \[ \f(x) = u_0 + u_1x +u_2 x^2 +u_3 x^3 + \cdots \,. \] Issues of convergence can be ignored in this question.

  1. Using the binomial series, show that the sequence given by \(u_n=n\,\) has generating function \(x(1-x)^{-2}\), and find the sequence that has generating function \(x(1-x)^{-3}\). Hence, or otherwise, find the generating function for the sequence \(u_n =n^2\). You should simplify your answer.
    • \(\bf (a)\) The sequence \(u_0\), \(u_1\), \(u_2\), \(\ldots\,\) is determined by \(u_{n} = ku_{n-1}\) (\(n\ge1\)), where \(k\) is independent of \(n\), and \(u_0=a\). By summing the identity \(u_{n}x^n \equiv ku_{n-1}x^n\), or otherwise, show that the generating function, f, satisfies \[ \f(x) = a + kx \f(x) \] Write down an expression for \(\f(x)\).
    • \(\bf (b)\) The sequence \(u_0, u_1, u_2, \ldots\,\) is determined by \(u_{n} = u_{n-1}+ u_{n-2}\) (\(n\ge2\)) and \(u_0=0\), \(u_1=1\). Obtain the generating function.

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*}
    • \(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*}

View
2013 Paper 1 Q6
D: 1500.0 B: 1501.4
binomial theorem binomial coefficients Pascals identity Fibonacci sequence recurrence relation summation proof by algebraic manipulation combinatorial identity

By considering the coefficient of \(x^r\) in the series for \((1+x)(1+x)^n\), or otherwise, obtain the following relation between binomial coefficients: \[ \binom n r + \binom n {r-1} = \binom {n+1} r \qquad (1\le r\le n). \] The sequence of numbers \(B_0\), \(B_1\), \(B_2\), \(\ldots\) is defined by \[ B_{2m} = \sum_{j=0}^m \binom{2m-j}j \text{ and } B_{2m+1} = \sum_{k=0}^m \binom{2m+1-k}k . \] Show that \(B_{n+2} - B_{n+1} = B_{n}\,\) (\(n=0\), \(1\), \(2\), \(\ldots\,\)). What is the relation between the sequence \(B_0\), \(B_1\), \(B_2\), \(\ldots\) and the Fibonacci sequence \(F_0\), \(F_1\), \(F_2\), \(\ldots\) defined by \(F_0=0\), \(F_1=1\) and \(F_n = F_{n-1}+F_{n-2}\) for \(n\ge2\)?

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

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
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
2007 Paper 3 Q3
D: 1700.0 B: 1469.5
proof by induction Fibonacci sequence recurrence relation divisibility sequences algebraic identity

A sequence of numbers, \(F_1, F_2, \ldots\), is defined by \(F_1=1, F_2=1\), and \[ F_n=F_{n-1}+F_{n-2}\, \quad \text{for \(n\ge 3\)}. \]

  1. Write down the values of \(F_3, F_4, \ldots , F_8\).
  2. Prove that \(F^{\vphantom{2}}_{2k+3}F^{\vphantom{2}}_{2k+1} -F_{2k+2}^2 = -F^{\vphantom{2}}_{2k+2}F^{\vphantom{2}}_{2k}+F_{2k+1}^2\,\).
  3. Prove by induction or otherwise that \(F^{\vphantom{2}}_{2n+1}F^{\vphantom{2}}_{2n-1}-F^2_{2n}=1\,\) and deduce that \(F^2_{2n}+1\,\) is divisible by \(F^{\vphantom{2}}_{2n+1}\,.\)
  4. Prove that \(F^2_{2n-1}+1\,\) is divisible by \(F^{\vphantom{2}}_{2n+1}\,.\)

View
1999 Paper 3 Q5
D: 1700.0 B: 1516.0
sequences recurrence relation Fibonacci sequence proof by induction algebraic identity summation of squares

The sequence \(u_0\), \(u_1\), \(u_2\), ... is defined by $$ u_0=1,\hspace{0.2in} u_1=1, \quad u_{n+1}=u_n+u_{n-1} \hspace{0.2in}{\rm for}\hspace{0.1in}n \ge 1\,. $$ Prove that $$ u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n ) \,. $$ Using induction, or otherwise, prove the following result: \[ u_{2n} = u^2_n + u^2_{n-1} \quad \mbox{ and }\quad u_{2n+1} = u^2_{n+1} - u^2_{n-1} \] for any positive integer \(n\).

Solution: Claim: \(u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )\) Proof: (By Induction). (Base Case): \(n = 1\) \begin{align*} && LHS &= u_{n+2}^2 + u_{n-1}^2 \\ &&&= u_3^2 + u_0^2 \\ &&&= 3^2 + 1^2 = 10\\ && RHS &= 2(u_{n+1}^2+u_n^2) \\ &&&= 2(2^2 + 1^2) \\ &&&= 10 \end{align*} Therefore the base case is true. (Inductive hypothesis) Suppose \(u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )\) is true for some \(n = k\), ie \(u^2_{k+2} + u^2_{k-1} = 2( u^2_{k+1} + u^2_k )\), the consider \(n = k+1\) \begin{align*} && LHS &= u_{k+1+2}^2 + u_{k+1-1}^2 \\ &&&= (u_{k+1}+u_{k+2})^2+u_k^2 \\ &&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}u_{k+2} \\ &&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}(u_{k+1}+u_k) \\ &&&= u_{k+2}^2 + u_{k+1}^2+u_k^2+2u_{k+1}^2+2u_{k+1}u_k \\ &&&= u_{k+1}^2+2u_{k+1}^2+ u_{k+1}^2+u_k^2+2u_{k+1}u_k \\ &&&= u_{k+2}^2+2u_{k+1}^2+ (u_{k+1}+u_k)^2 \\ &&&= u_{k+2}^2+2u_{k+1}^2+ u_{k+2}^2 \\ &&&=2(u_{k+2}^2+u_{k+1}^2) \\ &&&= RHS \end{align*} Therefore it is true for \(n = k+1\). Therefore by the principle of mathematical induction it is true for all \(n \geq 1\) Claim: $ u_{2n} = u^2_n + u^2_{n-1} \quad \mbox{ and }\quad u_{2n+1} = u^2_{n+1} - u^2_{n-1} $ Proof: Notice that \(\begin{pmatrix}u_{n+1} \\ u_n \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix}1 \\1 \end{pmatrix}\), in particular \begin{align*} && \begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\ \Rightarrow && \begin{pmatrix}u_{2n}& u_{2n-1} \\ u_{2n-1} & u_{2n-2} \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{2n} \\ &&&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\ &&&=\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2} \end{pmatrix}\\ &&&= \begin{pmatrix}u_{n}^2+u_{n-1}^2& u_{n-1}(u_n+u_{n-2}) \\ u_{n-1}(u_n+u_{n-2}) & u_{n-1}^2+u_{n-2}^2 \end{pmatrix} \end{align*} Therefore \(u_{2n} = u_{n}^2+u_{n-1}^2\) and \(u_{2n+1} = u_n(u_{n+1}+u_{n-1}) =(u_{n+1}-u_{n-1})(u_{n+1}-u_{n-1}) = u_{n+1}^2-u_{n-1}^2\)

View