Problems

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

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)$.
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:

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

2008 Paper 3 Q5

D: 1700.0 B: 1499.3

proof by induction recurrence relation sequences polynomial identity Chebyshev polynomials quadratic equation geometric progression

The functions ${\rm T}_n(x)$, for $n=0$, 1, 2, $\ldots\,$, satisfy the recurrence relation \[ {\rm T}_{n+1}(x) -2x {\rm T}_n(x) + {\rm T}_{n-1}(x) =0\, \ \ \ \ \ \ \ (n\ge1). \tag{$*$} \] Show by induction that \[ \left({\rm T}_n(x)\right)^2 - {\rm T}_{n-1}(x) {\rm T}_{n+1}(x) = \f(x)\,, \] where $\f(x) = \left({\rm T}_1(x)\right)^2 - {\rm T}_0(x){\rm T}_2(x)\,$. In the case $\f(x)\equiv 0$, determine (with proof) an expression for ${\rm T}_n(x)$ in terms of ${\rm T}_0(x)$ (assumed to be non-zero) and ${\rm r}(x)$, where ${\rm r}(x) = {\rm T}_1(x)/ {\rm T}_0(x)$. Find the two possible expressions for ${\rm r}(x)$ in terms of $x$. %Conjecture (without proof) the general form of the solution of $(*)$.

View

2008 Paper 3 Q8

D: 1700.0 B: 1500.0

sequences recurrence relation power series geometric series partial fractions sum to infinity finite sum generating functions

The coefficients in the series \[ S= \tfrac13 x + \tfrac 16 x^2 + \tfrac1{12} x^3 + \cdots + a_rx^r + \cdots \] satisfy a recurrence relation of the form $a_{r+1} + p a_r =0$. Write down the value of $p$. By considering $(1+px)S$, find an expression for the sum to infinity of $S$ (assuming that it exists). Find also an expression for the sum of the first $n+1$ terms of $S$.
The coefficients in the series \[ T=2 + 8x +18x^2+37 x^3 +\cdots + a_rx^r + \cdots \] satisfy a recurrence relation of the form $a_{r+2}+pa_{r+1} +qa_r=0$. Find an expression for the sum to infinity of $T$ (assuming that it exists). By expressing $T$ in partial fractions, or otherwise, find an expression for the sum of the first $n+1$ terms of $T$.

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$}. \]

Write down the values of $F_3, F_4, \ldots , F_8$.
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\,$.
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}\,.$
Prove that $F^2_{2n-1}+1\,$ is divisible by $F^{\vphantom{2}}_{2n+1}\,.$

View

2007 Paper 3 Q13

D: 1700.0 B: 1500.0

probability discrete probability distributions recurrence relation expected value random walk first passage time geometric series approximation

A frog jumps towards a large pond. Each jump takes the frog either $1\,$m or $2\,$m nearer to the pond. The probability of a $1\,$m jump is $p$ and the probability of a $2\,$m jump is $q$, where $p+q=1$, the occurence of long and short jumps being independent.

Let $p_n(j)$ be the probability that the frog, starting at a point $(n-\frac12)\,$m away from the edge of the pond, lands in the pond for the first time on its $j$th jump. Show that $p_2(2)=p$.
Let $u_n$ be the expected number of jumps, starting at a point $(n-\frac12)\,$m away from the edge of the pond, required to land in the pond for the first time. Write down the value of $u_1$. By finding first the relevant values of $p_n(m)$, calculate $u_2$ and show that $u_3= 3-2q+q^2\(.
Given that \)u_n$ can be expressed in the form $u_n= A(-q)^{n-1} +B +Cn$, where $A$, $B$ and $C$ are constants (independent of $n$), show that $C= (1+q)^{-1}$ and find $A$ and $B$ in terms of $q$. Hence show that, for large $n$, $u_n \approx \dfrac n{p+2q}$ and explain carefully why this result is to be expected.

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.

Determine the values of $k$ for which the sequence $(*)$ is: (a) constant; (b) periodic with period 2; (c) periodic with period 4.
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

2005 Paper 3 Q4

D: 1700.0 B: 1457.9

sequences recurrence relation proof by induction geometric sequence periodic sequence ratio closed form expression

The sequence $u_n$ ($n= 1, 2, \ldots$) satisfies the recurrence relation \[ u_{n+2}= \frac{u_{n+1}}{u_n}(ku_n-u_{n+1}) \] where $k$ is a constant. If $u_1=a$ and $u_2=b\,$, where $a$ and $b$ are non-zero and $b \ne ka\,$, prove by induction that \[ u_{2n}=\Big(\frac b a \Big) u_{2n-1} \] \[ u_{2n+1}= c u_{2n} \] for $n \ge 1$, where $c$ is a constant to be found in terms of $k$, $a$ and $b$. Hence express $u_{2n}$ and $u_{2n-1}$ in terms of $a$, $b$, $c$ and $n$. Find conditions on $a$, $b$ and $k$ in the three cases:

the sequence $u_n$ is geometric;
$u_n$ has period 2;
the sequence $u_n$ has period 4.

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

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

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}\,$.

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

View

2004 Paper 3 Q6

D: 1700.0 B: 1503.0

sequences recurrence relation quadratic identity algebraic manipulation periodic sequence proof telescoping

Given a sequence $w_0$, $w_1$, $w_2$, $\ldots\,$, the sequence $F_1$, $F_2$, $\ldots$ is defined by $$F_n = w_n^2 + w_{n-1}^2 - 4w_nw_{n-1} \,.$$ Show that $\; F_{n}-F_{n-1} = \l w_n-w_{n-2} \r \l w_n+w_{n-2}-4w_{n-1} \r \; $ for $n \ge 2\,$.

The sequence $u_0$, $u_1$, $u_2$, $\ldots$ has $u_0 = 1$, and $u_1 = 2$ and satisfies \[ u_n = 4u_{n-1} -u_{n-2} \quad (n \ge 2)\;. \] Prove that \ $ u_n^2 + u_{n-1}^2 = 4u_nu_{n-1}-3 \; $ for $n \ge 1\,$.
A sequence $v_0$, $v_1$, $v_2$, $\ldots\,$ has $v_0=1$ and satisfies \begin{equation*} v_n^2 + v_{n-1}^2 = 4v_nv_{n-1}-3 \quad (n \ge 1). \tag{$\ast$} \end{equation*} \makebox[7mm]{(a) \hfill}Find $v_1$ and prove that, for each $n\ge2\,$, either $v_n= 4v_{n-1} -v_{n-2}$ or $v_n=v_{n-2}\,$. \makebox[7mm]{(b) \hfill}Show that the sequence, with period 2, defined by \begin{equation*} v_n = \begin{cases} 1 & \mbox{for $n$ even} \\ 2 & \mbox{for $n$ odd} \end{cases} \end{equation*} \makebox[7mm]{\hfill}satisfies $(\ast)$. \makebox[7mm]{(c) \hfill}Find a sequence $v_n$ with period 4 which has $v_0=1\,$, and satisfies~$(\ast)$.

View

2004 Paper 3 Q7

D: 1700.0 B: 1500.0

integration reduction formula inequality logarithm summation bounding recurrence relation ln 2

For $n=1$, $2$, $3$, $\ldots\,$, let \[ I_n = \int_0^1 {t^{n-1} \over \l t+1 \r^n} \, \mathrm{d} t \, . \] By considering the greatest value taken by $\displaystyle {t \over t+1}$ for $0 \le t \le 1$ show that $I_{n+1} < {1 \over 2} I_{n}\,$. Show also that $\; \displaystyle I_{n+1}= - \frac 1{\; n\, 2^n} + I_{n}\,$. Deduce that $\; \displaystyle I_n < \frac1 {\; n \, 2^{n-1}}\,$. Prove that \[ \ln 2 = \sum_{r=1}^n {1 \over \; r\, 2^r} + I_{n+1} \] and hence show that ${2 \over 3} < \ln 2 < {17 \over 24}\,$.

View

2003 Paper 2 Q12

D: 1600.0 B: 1484.0

probability binomial distribution conditional probability expectation recurrence relation branching process geometric series convergence

The life of a certain species of elementary particles can be described as follows. Each particle has a life time of $T$ seconds, after which it disintegrates into $X$ particles of the same species, where $X$ is a random variable with binomial distribution $\mathrm{B}(2,p)\,$. A population of these particles starts with the creation of a single such particle at $t=0\,$. Let $X_n$ be the number of particles in existence in the time interval $nT < t < (n+1)T\,$, where $n=1\,$, $2\,$, $\ldots$. Show that $\P(X_1=2 \mbox { and } X_2=2) = 6p^4q^2\;$, where $q=1-p\,$. Find the possible values of $p$ if it is known that $\P(X_1=2 \vert X_2=2) =9/25\,$. Explain briefly why $\E(X_n) =2p\E(X_{n-1})$ and hence determine $\E(X_n)$ in terms of $p$. Show that for one of the values of $p$ found above $\lim_{n \to \infty}\E(X_n) = 0$ and that for the other $\lim_{n \to \infty}\E(X_n) = + \infty\,$.

View

2003 Paper 3 Q4

D: 1700.0 B: 1516.0

parametric equations tangent recurrence relation trigonometric periodic sequence curve tan identity algebraic manipulation

A curve is defined parametrically by \[ x=t^2 \;, \ \ \ y=t (1 + t^2 ) \;. \] The tangent at the point with parameter $t$, where $t\ne0\,$, meets the curve again at the point with parameter $T$, where $T\ne t\,$. Show that \[ T = \frac{1 - t^2 }{2t} \mbox { \ \ \ and \ \ \ } 3t^2\ne 1\;. \] Given a point $P_0\,$ on the curve, with parameter $t_0\,$, a sequence of points $P_0 \, , \; P_1 \, , \; P_2 \, , \ldots$ on the curve is constructed such that the tangent at $P_i$ meets the curve again at $P_{i+1}$. If $t_0 = \tan \frac{ 7 } {18}\pi\,$, show that $P_3 = P_0$ but $P_1\ne P_0\,$. Find a second value of $t_0\,$, with $t_0>0\,$, for which $P_3 = P_0$ but $P_1\ne P_0\,$.

View

2003 Paper 3 Q13

D: 1700.0 B: 1500.0

probability conditional probability recurrence relation Markov chain symmetry simultaneous equations random walk

In a rabbit warren, underground chambers $A, B, C$ and $D$ are at the vertices of a square, and burrows join $A$ to $B$, \ $B$ to $C$, \ $C$ to $D$ and $D$ to $A$. Each of the chambers also has a tunnel to the surface. A rabbit finding itself in any chamber runs along one of the two burrows to a neighbouring chamber, or leaves the burrow through the tunnel to the surface. Each of these three possibilities is equally likely. Let $p_A\,$, $p_B\,$, $p_C$ and $p_D$ be the probabilities of a rabbit leaving the burrow through the tunnel from chamber $A$, given that it is currently in chamber $A, B, C$ or $D$, respectively.

Explain why $p_A = \frac13 + \frac13p_B + \frac13 p_D$.
Determine $p_A\,$.
Find the probability that a rabbit which starts in chamber $A$ does not visit chamber~$C$, given that it eventually leaves the burrow through the tunnel in chamber $A$.

View

2002 Paper 1 Q8

D: 1500.0 B: 1516.0

sequences geometric sequences recurrence relation loan repayment geometric series summation financial mathematics

I borrow $C$ pounds at interest rate $100\alpha \,\%$ per year. The interest is added at the end of each year. Immediately after the interest is added, I make a repayment. The amount I repay at the end of the $k$th year is $R_k$ pounds and the amount I owe at the beginning of $k$th year is $C_k$ pounds (with $C_1=C$). Express $C_{n+1}$ in terms of $R_k$ ($k= 1$, $2$, $\ldots$, $n$), $\alpha$ and $C$ and show that, if I pay off the loan in $N$ years with repayments given by $R_k= (1+\alpha)^kr\,$, where $r$ is constant, then $r=C/N\,$. If instead I pay off the loan in $N$ years with $N$ equal repayments of $R$ pounds, show that \[ \frac R C = \frac{\alpha (1+\alpha)^{N} }{(1+\alpha)^N-1} \;, \] and that $R/C\approx 27/103$ in the case $\alpha =1/50$, $N=4\,$.

View

Problems

Filters