Sequences Solutions

Part of the Oxford MAT Livestream.

Revision Questions

$a_3=3^2-3=6$. $a_{10}=90$.
$a_{n+1}-a_n=\left((n+1)^2-(n+1)\right)-\left(n^2-n\right)=2n$.
$a_{n+1}-2a_n+a_{n-1}=\left(a_{n+1}-a_n\right)-\left(a_{n}-a_{n-1}\right)=2n-2(n-1)$ using the previous part, and this is $2$.
This is the sum of the first 11 terms of an arithmetic sequence with first term $a=1$ and common difference $3$. So the sum is $\frac{11}{2}\left(2+10\times 3\right)=176$. Also, $a_{1000}=3001$.
This is the sum of the first 11 terms of a geometric sequence with first term $a=1$ and common ratio $\frac{1}{3}$. So the sum is $\frac{\left(1-3^{-11}\right)}{1-3^{-1}}=\frac{3}{2}\left(1-3^{-11}\right)$. Also, $a_{1000}=3^{-1000}$.
The common ratio is between $-1$ and $1$ so the sum to infinity does converge. The sum to infinity is $\frac{1}{1-3^{-1}}=\frac{3}{2}$.
In particular, we would need $a_0=b_0$ so $1=A+B$. Also, we would need $a_1=b_1$ so $4=3A+B$. So $A=\frac{3}{2}$ and $B=-\frac{1}{2}$.
We should check that this works for all $n$, so let's check that if $a_{n-1}=b_{n-1}$ then $a_n=b_n$. We know that $a_n=3a_{n-1}+1$ and we can work out $3b_{n-1}+1=3\times\frac{3}{2}3^{n-1}-\frac{3}{2}+1=\frac{3}{2}3^n-\frac{1}{2}$ which is exactly $b_n$. So if $a_{n-1}=b_{n-1}$ then $a_n=b_n$. The sequences match for all $n$.
At first sight, this doesn't look like enough information; we haven't been told the values of any of the terms in the sequence! The key is that we're asked to give our answer in terms of the first three terms of the sequence without solving for what those are.
For example, if we substitute $n=0$ then we find $a_0=C$. So we've got an expression for $C$ in terms of $a_0$.
Now substitute $n=1$ and $n=2$ to get $a_1=A+B+C$ and $a_2=4A+2B+C$. We want $A$ and $B$ in terms of the variables $a_0$, $a_1$, $a_2$, and we can use the fact that $C=a_0$ to eliminate $C$. These are simultaneous equations for $A$ and $B$ with solution
\[ A=\frac{1}{2}\left(a_2-2a_1+a_0\right),\qquad B=\frac{1}{2}\left(-a_2+4a_1-3a_0\right)\]
This is a geometric sequence with common ratio $x^3$, and the sum to infinity converges if $|x^3|<1$, which is precisely $|x|<1$.
In that case, it converges to $(1-x^3)^{-1}$.
This is a geometric sequence with common ratio $-\frac{x}{2}$, and the sum to infinity converges if $\left|-\frac{x}{2}\right|<1$, which is precisely $|x|<2$.
In that case, it converges to $\displaystyle\frac{2}{1+\frac{x}{2}}=\frac{4}{2+x}$.
The $15^\text{th}$ term will be equal to the first plus 14 times the common difference, so $5+14\times 3=47$.
This is strange because the next $k$ terms should each be $kd$ more than the corresponding term $k$ places before it in the sequence. For the sum to be the same, we would need $d=0$ (a constant sequence) or $k=0$ (no numbers in the statement!).
The $n^\text{th}$ term is the same thing as the sum of the first $n$ terms minus the sum of the first $(n-1)$ terms, so we want $\left(3n^2+5n\right)-\left(3(n-1)^2+5(n-1)\right)=6n+2$.
Alternatively, just set $n=1$ and $n=2$ to find the first term is $8$ and the sum of the first two terms is $22$ so the second term is $14$ and the common difference is therefore $6$.
$2+4+6+8+\dots+200$ is the sum of an arithmetic progression with first term $a=2$, common difference $d=2$ and number of terms $n=100$, so the sum is $$\frac{n}{2}(2a+(n-1)d)=50\times 202=10100.$$
What's the common ratio? We have $a=3$ and $ar^2=27$ so either $r=3$ or $r=-3$. The sum of the first five terms is
$$\frac{a(r^5-1)}{r-1}=\frac{3((\pm 3)^5-1)}{(\pm 3)-1}= \quad\text{either}\quad363 \quad\text{or}\quad 183$$
First note that $a_1=3$ (the only previous term is 3) and then $a_2=3+3=6$. After that, $a_3=6+3+3=12$ and it seems like the terms double each time.
That's true because $a_{n}=a_{n-1}+a_{n-2}+\dots+a_0$ and $a_{n-1}=a_{n-2}+\dots+a_0$ so $a_{n}=a_{n-1}+a_{n-1}=2a_{n-1}$.
So after $a_0$ this is a geometric sequence with $a_n=3\times 2^{n-1}$ for $n\geq 1$.
For $C_1$ I'll put $n=0$ into the equation, so that the left-hand side reads $C_1$. The right-hand side is then \[\sum_{i=0}^0 C_iC_{-i}.\] That looks pretty weird written out like that; the sum from $i=0$ to $0$ is just the term with $i=0$, which is $C_0^2$. So $C_1=C_0^2=1$.
Now for $C_2$, I'll put $n=1$ into the equation. The right-hand side is more interesting now; I get \[\sum_{i=0}^1C_iC_{1-i}\] which is $C_0C_1+C_1C_0$. So $C_2=C_0C_1+C_1C_0=2$.
Then $C_3=C_2C_0+C_1C_1+C_0C_2=5$ and $C_4=C_3C_0+C_2C_1+C_1C_2+C_0C_3=14$.

MAT Questions

MAT 2016 Q1A

The first fifteen terms are $1$, $l$, $l^2$, $l^3$, $\dots$, $l^{13}$, $l^{14}$.
The product of these terms is $1\times l \times l^2 \times \dots \times l^{14}$.
This simplifies to a power of $l$, where the exponent is $1+2+\dots+ 14$, which is an arithmetic series with value $\frac{1}{2}\times14\times 15= 105$.
The answer is (d).

MAT 2017 Q1C

The first few terms are $a_1=2$, $a_2=6$, $a_3=3$, $a_4=1/2$, $a_5=1/6$, $a_6=1/3$, $a_7=2$, $a_8=6$.
From here, the sequence repeats, because each term just depends on the previous two, which are now back to where we started.
$a_n$ will be equal to $2$ whenever $n$ is one more than a multiple of 6.
2016 is a multiple of 6, so 2017 is one more than a multiple of 6.
The answer is (d).

MAT 2016 Q1G

The first few terms are $x_0=1$, $x_1=1$, $x_2=2$, $x_3=4$, $x_4=8$.
After the first term, each term is twice the previous term (this is because the most recent term was the sum of all terms before that, so our next sum will include two copies of that sum).
The sum to infinity that we're asked for is $$1+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots$$ which is, after the first term, a geometric series that converges to 2. So the sum including the first term is 3.
The answer is (d).

MAT 2008 Q2

(i) Perhaps $(x,y)=(1,0)$ if you count zero as positive. Or $(x,y)=(3,2)$ if you don't.

(ii) We would need
$$
(3x_n+4y_n)^2-2(ax_n+by_n)^2=x_n^2-2y_n^2
$$
Multiply out the left-hand side.
$$
9x_n^2+24x_ny_n+16y_n^2-2a^2x_n^2-4abx_ny_n-2b^2y_n^2=x_n^2-2y_n^2
$$
This looks unlikely to be true, but one way to make it work would be to make the coefficients of $x_n^2$, and $x_ny_n$, and $y_n^2$ agree between the two expressions. We would need
$$
9-2a^2=1\qquad \text{and}\qquad 24-4ab=0\qquad \text{and}\qquad 16-2b^2=-2
$$
Amazingly, we can satisfy all of these by setting $a=2$ and $b=3$.

(iii) Use the sequences $x_n$ and $y_n$. The relationship we proved in the previous part of the question means that $$x_{n+1}^2-2y_{n+1}^2=x_n^2-2y_n^2=x_{n-1}^2-2y_{n-1}^2=\dots=x_2^2-2y_2^2=x_1^2-2y_1^2=1.$$

If we generate the first few terms with the rules in part (ii), we find
\begin{equation*}
x_1=3, \quad y_1=2,\qquad x_2=17, \quad y_2=12, \qquad x_3=99, \quad y_3=70.
\end{equation*}
So $X=99$, $Y=70$ works (check; $99^2=9801$, $70^2=4900$, so $X^2-2Y^2=1$).

(iv) These values of $x_n$ and $y_n$ satisfy $\left(x_n\right)^2-2\left(y_n\right)^2=1$. If we divide this by $y_n^2$ then we get
$$
\left(\frac{x_n}{y_n}\right)^2-2=\frac{1}{(y_n)^2}
$$
If $y_n$ is very large, then the right-hand side of this equality is very small. So $(x_n/y_n)^2$ must be close to 2. Since $x_n/y_n$ is positive, we can conclude that it is close to $\sqrt{2}$ for large $n$.

Extension

Consider $x_n^2-3y_n^2=1$. Let $x_1=1$ and $y_1=0$. Suppose $x_{n+1}=ax_n+by_n$ and $y_{n+1}=cx_n+dy_n$. It would be nice to have $(ax_n+by_n)^2-3(cx_n+dy_n)^2=x_n^2-3y_n^2$. Comparing terms, we want $a^2-3c^2=1$ and $ab-3cd=0$ and $b^2-3d^2=-3$. We can achieve all of these with $a=2$, $b=3$, $c=1$, and $d=2$. Then generate some more solutions for $(x,y)$; $(1,0)\rightarrow(2,1)\rightarrow(7,4)\rightarrow(26,15)\rightarrow(97,56)$. So $\sqrt{3}\approx \frac{97}{56}$.

MAT 2016 Q5

(i) $s_1=2$ and $s_2=10$ and $s_3=34$. Meanwhile, $f(1)=(A+B)2+C$, $f(2)=(2A+B)2^2+C$, and $f(3)=(3A+B)2^3+C$. So we have the following equations.
\begin{align*}
    2 =& 2 A + 2 B + C\\
    10 =& 8 A + 4 B + C\\
    34 =& 24A + 8 B + C
\end{align*}
(ii) Take the difference between the first and second equations. Take the difference between the second and third equations. Simplify to get $4 = 3 A + B$ and $6 = 4 A + B$. Take the difference to get $A=2$. Then $B=-2$ and $C=2$ from the other equations. So $f(n)=(2A-2)2^n+2$.

(iii) The difference between $s_{k+1}$ and $s_k$ is just the final term in the sum, $(k+1)2^{k+1}$.

The difference between $f(k+1)$ and $f(k)$ is $\left[(2(k+1)-2)2^{k+1}+2\right] - \left[(2k-2)2^{k}+2\right]$, which simplifies to
$$
(2k)2^{k+1}-(k-1)2^{k+1}=(k+1)2^{k+1}
$$

That's the same expression for the difference. So if $s_k$ is equal to $f(k)$, then $s_{k+1}$ will be equal to $f(k+1)$.

(iv) That last term can be written as $2^{n-1}(n-(n-1))$ to make it easier to see the pattern. If we expand the brackets, we have $$
n + 2n-2 + 4n-8 + \dots + 2^{n-1}n-(n-1)2^{n-1}.
$$
The terms with minus signs are the sum we had before, up to $n-1$. The other terms are just a geometric series multiplied by $n$. So the sum is
$$
n(1+2+4+\dots +2^{n-1})-s_{n-1}
$$
which is $(2^n - 1)n - (2(n-1)-2)2^{n-1}-2 = 2^{n+1}-n-2$ after simplifying.

Then $u_n$ is just $t_n/2^n$ (with the terms written in the opposite order).

(v) We can use the formula for $s_k$ and expand to get $$\sum_{k=1}^n \left((2k-2)2^k +2 \right)= 2 \sum_{k=1}^n k2^k -2 \sum_{k=1}^n 2^k +\sum_{k=1}^n 2.$$
The first of these is just $2s_n$, then the second term is $-2(2^{n+1}-2)$ and the third is just $2n$.

Using the formula for $s_n$ and simplifying gives $2^{n+2}n-2^{n+3}+2n+8$.

Extension

The extension asks for the sum of that last expression. Using the formula for the sum $s_n$, the sum of a geometric sequence, and the sum of an arithmetic sequence, we get $$4\times((2n-2)2^n+2)-8\times(2^{n+1}-2)+n(n+1)+8n=(n-3)2^{n+3}+n^2+9n+24.$$