Sequences

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 an relation like $a_{n+1}=f(a_n)$ for $n\geq 0$, if we're given the function $f(x)$ and also given a first term like $a_0=1$. (The "first term" might be $a_0$ if we feel like counting from zero).
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".
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).

Revision Questions

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$.
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}$.
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?
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$.
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$.
When does the sum $1+x^3+x^6+x^9+x^{12}+...$ converge? Simplify it in the case that it converges.
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.
If the first term of an arithmetic progression is 5 and the common difference is 3, what is the $15^\text{th}$ term?
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?
If the sum of the first $n$ terms of an arithmetic progression is $3n^2 + 5n$, what is the $n^\text{th}$ term?
What is the sum of the first 100 positive even integers (starting at 2)?
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.
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$.
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 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 2012 Q5

A particular robot has three commands;
$\textbf{F}$: Move forward a unit distance;
$\textbf{L}$: Turn left $90^\circ$
$\textbf{R}$: Turn right $90^\circ$

A program is a sequence of commands. We consider particular programs $P_n$ (for $n\geqslant0$) in this question. The basic program $P_0$ just instructs the robot to move forward: \[P_0=\textbf{F}.\] The program $P_{n+1}$ (for $n\geqslant 0$) involves performing $P_n$, turning left, performing $P_n$, turning left, performing $P_n$ again, then turning right: \[P_{n+1}=P_n\textbf{L}P_n\textbf{R}.\] So, for example, $P_1=\textbf{FLFR}$.

(i) Write down the program $P_2$.

(ii) How far does the robot travel during the program $P_n$? In other words, how many $\textbf{F}$ commands does it perform?

(iii) Let $l_n$ be the total number of commands in $P_n$; so, for example, $l_0=1$ and $l_1=4$.
Write down an equation relating $l_{n+1}$ to $l_n$. Hence write down a formula for $l_n$ in terms of $n$. Hint: consider $l_n+2$.

(iv) The robot starts at the origin, facing along the positive $x$-axis. What direction is the robot facing after performing the program $P_n$?

(v) Draw the path the robot takes when it performs the program $P_4$.

(vi) Let $(x_n,y_n)$ be the position of the robot after performing the program $P_n$, so $(x_0,y_0)=(1,0)$ and $(x_1,y_1)=(1,1)$. Give an equation relating $(x_{n+1},y_{n+1})$ to $(x_n,y_n)$

What is $(x_8,y_8)$? What is $(x_{8k},y_{8k})$?

Hints

(i) Extend what we've learned about $P_1$ to $P_2$. I suppose $P_2=P_1\textbf{L}P_1\textbf{R}$ but we can do better than that!

(ii) How many $\textbf{F}$ commands are there in $P_0$, $P_1$, and $P_2$?

(iii) $l_{n+1}$ is the length of $P_{n+1}$. How long are $P_0$, $P_1$, and $P_2$? From the definition $P_{n+1}=P_n\textbf{L}P_n\textbf{R}$, what would you expect the length of $P_3$?

It's hard to solve this recursion relation using MAT-level maths. Luckily, there's a hint. We could give the sequence $l_n+2$ a name like $a_n$ and try to convert our fact about $l_{n+1}$ and $l_n$ into a fact about $a_{n+1}$ and $a_n$.

(iv) How many $\textbf{L}$ commands are there in $P_n$? How many $\textbf{R}$ commands are there in $P_n$?

(v) Draw paths for $P_1$ and $P_2$ and $P_3$ first.

Remember that the robot spins on the spot for $\textbf{L}$ and for $\textbf{R}$.

Remember that, during $P_2$, the robot turns at the end of $P_1$ and then immediately turns again for the $\textbf{L}$ before the next $P_1$ starts.

At the end of each $P_n$, the robot is facing in a particular direction which might or might not be the direction of the most recent $\textbf{F}$ command that it moved (it might have done some spinning at the end).

(vi) Here are two things to think about.

What would happen if we started the robot at $(a,b)$ and ran program $P_n$?
What would happen if we started the robot at $(0,0)$ and ran $\textbf{L}P_n$?

Find $(x_2,y_2)$ and $(x_3,y_3)$ and so on up to $(x_8,y_8)$. If you spot any shortcuts, take them!

Describe a simpler program $\textbf{Q}$ that takes the robot from $(0,0)$ to $(x_8,y_8)$ (literally a shortcut for the robot to take). Explain why $(x_9,y_9)$ is the same position that a robot would end up in if it ran the program $\textbf{QLQR}$. Why is this a bit like the calculations you just did for $(x_2,y_2)$ and $(x_3,y_3)$?