Sequences

Part of the Oxford MAT Livestream.

Solutions are available here

MAT syllabus

Sequences defined iteratively and by formulae. Arithmetic and geometric progressions*. Their sums*. Convergence condition for infinite geometric progressions*.

* Part of full A-level Mathematics syllabus.

Revision

• A sequence $a_n$ might be defined by a formula for the $n^\text{th}$ term like $a_n=n^2-n$.
• A sequence $a_n$ might be defined with a "recurrence relation" like $a_{n+1}=f(a_n)$ for $n\geq 0$, if we're given the function $f(x)$ and also given a value for the first term $a_0$. (I'm counting from zero, so my "first term" is $a_0$, but it's also common to start with $a_1$, in which case the recurrence relation could be given as $a_{n+1}=f(a_n)$ for $n\geq 1$).
• The sum of the first $n$ terms of a sequence $a_k$ can be written with the notation $\displaystyle \sum_{k=0}^{n-1} a_k$ (if the first term is $a_0$) or $\displaystyle\sum_{k=1}^n a_k$ (if the first term is $a_1$).
• An arithmetic sequence is one where the difference between terms is constant. The terms can be written as $a$, $a+d$, $a+2d$, $a+3d$, $\dots$, where $a$ is the first term and $d$ is the common difference.
• The sum of the first $n$ terms of an arithmetic sequence with first term $a$ and common difference $d$ is $\displaystyle\frac{n}{2}\left(2a+(n-1)d\right)$, which you can remember as "first term plus last term, times the number of terms, divided by two" or $\displaystyle\frac{n}{2}(a+l)$, writing $l$ for the last term.
• A geometric sequence is one where the ratio between consecutive terms is constant. The terms can be written as $a$, $ar$, $ar^2$, $ar^3$, $\dots$ where $a$ is the first term and $r$ is the common ratio.
• The sum of the first $n$ terms of a geometric sequence with first term $a$ and common ratio $r$ is $\displaystyle \frac{a(1-r^n)}{1-r}$. One way to remember this is to remember what happens if we multiply the sum of the first $n$ terms of a geometric series by $(1-r)$,
  $$\begin{align*} (1-r)(a+ar+\dots +ar^{n-1})=&(a-ar)+(ar-ar^2)+\dots+(ar^{n-1}-ar^n)\\ =&a-ar^n. \end{align*}$$
• For a geometric sequence $a_n$, the sum to infinity is written as $\displaystyle \sum_{k=0}^\infty a_k$. If the common ratio $r$ satisfies $|r|<1$ then this is equal to $\displaystyle \frac{a}{1-r}$. If $|r|\geq 1$ then this sum to infinity does not converge (it does not approach any particular real number).
• A periodic sequence has terms that repeat in a cycle; there is some $L$ such that for all $n\geq 0$, we have $a_{n+L}=a_n$. The order of a periodic sequence is the minimum such $L$.

Revision Questions

1. A sequence is defined by $a_n=n^2-n$. What is $a_3$? What is $a_{10}$? Find $a_{n+1}-a_n$ in terms of $n$. Find $a_{n+1}-2a_n+a_{n-1}$ in terms of $n$.
2. A sequence is defined by $a_0=1$ and $a_n=a_{n-1}+3$ for $n\geq 1$. Find $a_0+a_1+\dots + a_{10}$. Find $a_{1000}$.
3. A sequence is defined by $a_0=1$ and $a_n=\frac{a_{n-1}}{3}$ for $n\geq 1$. Find $a_0+a_1+\dots + a_{10}$. Find $a_{1000}$. Does the sum of all the terms of this sequence converge? If it does, what is the sum to infinity?
4. A sequence is defined by $a_0=1$ and $a_n=3a_{n-1}+1$ for $n\geq 1$. A sequence $b_n$ is defined by $b_n=A \times 3^n+B$ where $A$ and $B$ are real numbers. Find values for $A$ and $B$ such that $a_n=b_n$ for all $n\geq 0$.
5. A sequence is defined by $a_n=An^2+Bn+C$ where $A$, $B$, and $C$ are real numbers. Find $A$, $B$, and $C$ in terms of $a_0$, $a_1$, and $a_2$.    
6. When does the sum $1+x^3+x^6+x^9+x^{12}+...$ converge? Simplify it in the case that it converges.
7. When does the sum $\displaystyle 2-x+\frac{x^2}{2}-\frac{x^3}{4}+\dots$ converge? Simplify it in the case that it converges.
8. If the first term of an arithmetic progression is 5 and the common difference is 3, what is the $15^\text{th}$ term?
9. The sum of the first $k$ terms of an arithmetic progression is equal to the sum of the next $k$ terms. What can you deduce?
10. If the sum of the first $n$ terms of an arithmetic progression is $3n^2 + 5n$, what is the $n^\text{th}$ term?
11. What is the sum of the first 100 positive even integers (starting at 2)?
12. The first term of a geometric progression is 3 and the third term is 27. Find two possibilities for the sum of the first 5 terms.
13. A sequence is defined by $a_0=3$ and then for $n\geq 1$ $a_n$ is the sum of all previous terms. Find $a_n$ in terms of $n$ for $n\geq 1$.
14. A sequence is defined by $C_0=1$ and then for $n\geq 0$, $$\displaystyle C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}.$$
    Find $C_1$ and $C_2$ and $C_3$ and $C_4$.

MAT questions

MAT 2016 Q1A

A sequence $a_n$ has first term $a_1 = 1$, and subsequent terms defined by $a_{n+1} = la_n$ for $n \geqslant 1$. What is the product of the first 15 terms of the sequence?

(a) $l^{14}$,
(b) $15 +  l^{14}$,
(c) $15l^{14}$,
(d) $l^{105}$,
(e) $15 + l^{105}$.

Hints

• Work out the first few terms of the sequence.
• What's the product of the first three terms of the sequence? Can you simplify your answer? What sum did you need to do in order to simplify your answer?
• How would that change with 15 terms? What would the $15^\text{th}$ term be?
• What happens if $l=1$?

MAT 2017 Q1C

A sequence $(a_n)$ has the property that $$a_{n+1} = \frac{a_{n}}{a_{n-1}}$$ for every $n \geqslant 2$. Given that $a_1 = 2$ and $a_2 = 6$, what is $a_{2017}$?

(a) $\displaystyle\frac{1}{6}$,
(b) $\displaystyle\frac{2}{3}$,
(c) $\displaystyle\frac{3}{2}$,
(d) $\displaystyle 2$,
(e) $\displaystyle 3$.

Hints

• Work out the first few terms of the sequence.
• You might find that after a while the calculations you're doing repeat previous calculations. Will that keep happening?
• For which values of $n$ is $a_n=2$? You know that $n=1$ is one such value of $n$.

MAT 2016 Q1G

The sequence $x_{n}$, where $n\geqslant 0$, is defined by $x_{0}=1$ and $$x_{n}=\sum_{k=0}^{n-1}x_{k}\qquad \text{for }n\geqslant 1.$$

The sum $$\sum_{k=0}^{\infty }\frac{1}{x_{k}}$$ equals

(a) 1,
(b) $\displaystyle \frac{6}{5}$,
(c) $\displaystyle \frac{8}{5}$,
(d) 3,
(e)  $\displaystyle \frac{27}{5}$.

Hints

• Work out the first few terms of the sequence.
• The $\Sigma$ notation means that $x_1=x_0$, and then $x_2=x_0+x_1$, and then $x_3=x_0+x_1+x_2$, and so on. Each term in the sequence is the sum of all the previous terms.
• Now work out $1/x_n$ for the values of $x_n$ you've calculated.
• It's not quite true that this sequence has a common ratio, but it's almost true!
• The sum of all the terms of the sequence is the same thing as the sum of the first two plus the sum of all the others.

MAT 2008 Q2

(i) Find a pair of positive integers, $x_{1}$ and $y_{1},$ that solve the equation
$$\begin{equation*} \left( x_{1}\right) ^{2}-2\left( y_{1}\right) ^{2}=1. \end{equation*}$$

(ii) Given integers $a,b,$ we define two sequences $x_{1},x_{2},x_{3},\ldots$ and $y_{1},y_{2},y_{3},\ldots$ by setting
$$\begin{equation*} x_{n+1}=3x_{n}+4y_{n},\qquad y_{n+1}=ax_{n}+by_{n},\qquad\text{for }n\geqslant 1. \end{equation*}$$

Find positive values for $a,b$ such that
$$\begin{equation*} \left( x_{n+1}\right) ^{2}-2\left( y_{n+1}\right) ^{2}=\left( x_{n}\right)^{2}-2\left( y_{n}\right) ^{2}. \end{equation*}$$

(iii) Find a pair of integers $X,Y$ which satisfy $X^{2}-2Y^{2}=1$ such that $X>Y>50.$

(iv) Using the values of $a$ and $b$ found in part (ii), what is the approximate value of $x_{n}/y_{n}$ as $n$ increases?

Hints

(i) Searching small values of $x_1$ or small values of $y_1$ is a good idea here. We're only asked to find a pair, not all such pairs. The question doesn't specific whether zero counts as a positive number (some people do count it, some people don't), so that's up to you.

(ii) Substitute everything in and hope for the best. We want this to be true for lots of different values of $x_n$ and $y_n$ (presumably), so we might aim to do something like comparing coefficients.

Hopefully this will give us some equations involving $a$ and $b$. We're not too worried about finding all possible solutions here; we're just looking for anything that works, and that has $a$ and $b$ positive.

(iii) This part of the question is all about understanding the previous part. We found a way to generate a sequence $x_n$ and a sequence $y_n$, and we showed that the sequences satisfy some sort of rule. Why did we do that? What's it got to do with the value of $X^2-2Y^2$?

It's easy to get distracted by the relationship that we've just proved if you're looking for a link between $x_{n+1}$ and $x_n$. Don't forget that we also have rules like $x_{n+1}=3x_n+4y_n$ which are easier to work with if we want to calculate $x_{n+1}$ from our knowledge of previous values of $x_n$ and $y_n$.

Alternatively, try large numbers $Y$ until you find one with $2Y^2+1$ equal to a square number. This might take a while!

(iv) From our work on the previous parts, we know that $x_n$ and $y_n$ satisfy a particular equation. We also know that $x_n$ and $y_n$ will be large for large $n$. Can you see how to convert the equation you've got into a fact about $x_n/y_n$?

Extension

[Just for fun, not part of the MAT question]

•  Find some rational approximations to $\sqrt{3}$ with a similar method.

MAT 2016 Q5

This question concerns the sum $s_n$ defined by
$$s_n = 2 + 8 + 24 + \cdots + n2^n.$$  
(i) Let $f(n) = (An+B)2^n + C$ for constants $A$, $B$ and $C$ yet to be determined, and suppose $s_n = f(n)$ for all $n\geq1$.  By setting $n=1,2,3$, find equations that must be satisfied by $A$, $B$ and $C$.

(ii) Solve the equations from part (i) to obtain values for $A$, $B$ and $C$.

(iii) Using these values, show that if $s_k = f(k)$ for some $k\geq1$ then $s_{k+1} = f(k+1)$.

You may now assume that $f(n)=s_n$ for all $n\geq1$.

(iv) Find simplified expressions for the following sums:
     $$\begin{align*}     t_n&= n + 2(n-1) + 4(n-2) + 8(n-3) + \cdots + 2^{n-1}1,\\     u_n&=\frac12+\frac24 + \frac38 + \cdots + \frac{n}{2^n}.     \end{align*}$$

(v) Find the sum $$\sum_{k=1}^n s_k.$$

Hints

(i) Check that you understand the relationship between the expression $n2^n$ and the numbers $2$ and $8$ and $24$. But notice that these aren't the values of $s_n$. The sequence $s_n$ involves adding these numbers together, so that when $n=2$, the value of $s_n$ is the sum $2+8=10$ (not just $8$).

You'll need the values of $s_1$ and $s_2$ and $s_3$, and you'll need to calculate $f(1)$ and $f(2)$ and $f(3)$ in terms of $A$ and $B$ and $C$.

It's a good idea to write out your work clearly, so that you have three equations in a tidy format, ready for the next part.

(ii) My equations each have $+C$, so I can take the difference of the first and second, or I can take the difference of the second and third, and either way I'll eliminate $C$. That gives me two equations for two unknowns ($A$ and $B$).

(iii) What's the difference between $s_{k+1}$ and $s_k$? If we knew a neat formula for $s_k$, that would clearly help us calculate $s_{k+1}$ (you wouldn't just start the sum again). You might even have spotted that shortcut while working out $s_3$ in a previous part. What's the difference in terms of $k$?

For $s_{k+1}$ to be equal to $f(k+1)$, we need to show that the change from $s_k$ to $s_{k+1}$ matches the change from $f(k)$ to $f(k+1)$.

We have values for $A$ and $B$ and $C$ from the previous part, so there's no mystery to $f(k+1)$. We could calculate the difference between $f(k)$ and $f(k+1)$ in terms of $k$.

For all of this to work, we'll need to see matching expressions for those differences.

(iv) For $t_n$, expand each bracket. Collect terms together, and watch out for a sum that we've already done.

For $u_n$, find a relationship between $t_n$ and $u_n$.

(v) Use the formula for $s_k$.

Consider the terms corresponding to $A$ and $B$ and $C$ separately. Those are each just constants (which you know the value for!) and they can be brought outside each sum. For example, $$\sum_{k=1}^n \left(A k 2^k\right)=A \sum_{k=1}^n \left(k 2^k\right).$$

Once again, you'll need to recognise a sum that you've already done.

Extension

[Just for fun, not part of the MAT question]

•  Find the sum $$\sum_{m=1}^n \left(\sum_{k=1}^m s_k\right).$$