Sequences Solutions

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 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 2012 Q5

(i) $P_2=P_1\textbf{L}P_1\textbf{R}=\textbf{FLFR}\;\textbf{L}\;\textbf{FLFR}\;\textbf{R}$

(ii) There's one $\textbf{F}$ in $P_0$, and then $P_{n+1}$ contains two copies of $P_n$ (and no other $\textbf{F}$ commands) so it has twice as many $\textbf{F}$ commands as $P_n$. Therefore $P_n$ has $2^n$ $\textbf{F}$ commands.

(iii) $P_{n+1}$ contains twice as many commands as $P_n$, plus two extra commands (the $\textbf{L}$ added in between and the $\textbf{R}$ at the end). So $l_{n+1}=2l_n+2$.

Consider $l_n+2$. The right-hand side of our equation is $2(l_n+2)-2$ so we can write
$$
(l_{n+1}+2)=2(l_n+2)
$$
This means that $l_n+2$ just doubles when $n$ is increased by $1$. So $l_n=A\times 2^n$ for some $n$. Note that $l_0=1$ so $l_0+2=3$. Compare this with $A\times 2^0$ and we see that $A=3$. Therefore $l_n=3\times 2^n-2$. Check that $l_0=1$, and $l_1=4$, and $l_2=10$. Check that $2\times (3\times 2^n-2)+2=3\times 2^{n+1}-2$.

(iv) The robot turns left just as often as it turns right, so after performing the program $P_n$, the robot is facing along the positive $x$-axis again.

(v) First draw the paths for $P_1$ and $P_2$ and $P_3$.

P0 right then up. P1 right then up twice then left ]. P3 right then up twice then left then up then left twice then down. P4. Right the up twice then left then up then left twice then down then up again along the same line! then left twice then down, left, down twice, and right.

(vi) If the robot starts at $(a,b)$ facing along the positive $x$-axis and performs program $P_n$, it moves to $(a+x_n,b+y_n)$. But if it first turns left and then performs program $P_n$, then what would have been a motion in the positive $x$-direction becomes a motion in the positive $y$-direction, and what would have been a motion in the positive $y$-direction becomes a motion in the negative $x$-direction. So if the robot starts at $(a,b)$ facing along the positive $x$-axis and performs program $\textbf{L}P_n$, then it is now at $(a-y_n,b+x_n)$.

For program $P_{n+1}$ the robot first performs $P_n$, moving to $(x_n,y_n)$, and then performs $\textbf{L}P_n$, moving to $(x_n-y_n,y_n+x_n)$ by the argument above.

Note that $(x_4,y_4)$ is $(-4,0)$, so the overall effect of the operation $P_4$ is a bit like $\textbf{F}$ but four times as much displacement, and in the opposite direction (and taking a complicated route to get there, of course). That means that as we generate $P_5$ and $P_6$ and $P_7$ and $P_8$, the overall displacements are the same as for $P_1$ and $P_2$ and $P_3$ and $P_4$, except $4$ times as large and with a minus sign. In particular, the displacement for $P_8$ is $((-4)^2,0)=(16,0)$.

That's the same as $\textbf{F}$ except 16 times as much displacement. This pattern continues; from here it's like starting again but with $\textbf{F}$ being 16 times as large. The displacement for $P_{8k}$ is therefore $16^k$.