MAT 2016

This paper contains 7 questions of which you should attempt 5. There are directions throughout the paper as to which questions are appropriate for your course.

A: Oxford Applicants: if you are applying to Oxford for the degree course:

• Mathematics or Mathematics & Philosophy or Mathematics & Statistics, you should attempt Questions 1,2,3,4,5.
• Mathematics & Computer Science, you should attempt Questions 1,2,3,5,6.
• Computer Science or Computer Science & Philosophy, you should attempt 1,2,5,6,7.

Directions under A take priority over any directions in B which are relevant to you.

B: Imperial Applicants: if you are applying to Imperial College for any of the Mathematics courses: Mathematics, Mathematics (Pure Mathematics), Mathematics with a Year in Europe, Mathematics with Applied Mathematics/Mathematical Physics, Mathematics with Mathematical Computation, Mathematics with Statistics, Mathematics with Statistics for Finance, Mathematics Optimisation and Statistics, you should attempt Questions 1,2,3,4,5.

 

Further credit cannot be obtained by attempting extra questions. Calculators are not permitted.

 

Question 1 is a multiple choice question with ten parts. Marks are given solely for correct answers but any rough working should be shown in the space between parts. Answer Question 1 on the grid on Page 2. Each part is worth 4 marks.

 

Answers to questions 2-7 should be written in the space provided, continuing on to the blank pages at the end of this booklet if necessary. Each of Questions 2-7 is worth 15 marks.

---

Average scores of MAT 2016

• The average score of all Oxford applicants for Maths, Maths & Stats, and Maths & Philosophy: $\mu_1=50.3$
• The average score of those applicants who were shortlisted for interview: $\mu_2=66.7$
• The average score of those applicants who were made offers: $\mu_3=73.1$

Other years' scores $(\mu_1,\mu_2,\mu_3)$

	$\mu_1$	$\mu_2$	$\mu_3$
MAT 2019	44.9	63.6	69.3
MAT 2018	50.8	67.1	72.9
MAT 2017	51.3	68.7	73.6
MAT 2016	50.3	66.7	73.1
MAT 2015	43.7	56.3	62.7
MAT 2014	48.4	63.1	71.5
MAT 2013	44.8	54.2	60.6
MAT 2012	52.1	63.0	68.2
MAT 2011	50.3	63.3	71.3
MAT 2010	49.0	61.4	69.3
MAT 2009	51.3	61.2	70.5
MAT 2008	58.7	68.0	77.0
MAT 2007	56.9	63.0	75.2

---

Question 1

Solution. It is a geometric sequence and as we find the first few terms,

$$ \begin{align} a_1&=1 \\ a_2&=l \\ a_3&=l^2 \\ a_4&=l^3 \\ &\;\vdots \\ a_{15}&=l^{14} \end{align} $$

So the product of the first 15 terms is:

$$ \begin{align} \prod_{r=1}^{15}a_r&=a_1a_2a_3\cdots a_{15} \\ &=1\cdot l\cdot l^2\cdots l^{14} \\ &=l^{1+2+\cdots+14} \\ &=l^{\frac{14\times15}{2}} \\ &=l^{105} \end{align} $$

Hence, the answer is (d).

---

Comment: We can also generalise the result

$$ \prod_{r=1}^na_r=l^{\sum_{r=1}^{n-1}r}=l^{\frac{n(n-1)}{2}} $$

---

Solution. Let $a$ denote the side of the hexagon as shown in the diagram. Since each side of the square is 1, the right hand corner provides a constraint through Pythagoras' theorem:

$$ \begin{align} (1-a)^2+(1-a)^2&=a^2 \\ 2(1-a)^2&=a^2 \\ \sqrt{2}(1-a)&=a \\ \left(1+\sqrt{2}\right)a&=\sqrt{2} \\ \Rightarrow\quad a=\frac{\sqrt{2}}{\sqrt{2}+1}&=\sqrt{2}\left(\sqrt{2}-1\right)=2-\sqrt{2} \quad\checkmark \end{align} $$

Hence, the answer is (b).

---

Comment: Since both a and 1-a are positive, we took the positive square root. One could solve the equation $2(1-a)^2=a^2$ more carefully:

$$ \begin{align} 2\left(1-2a+a^2\right)=a^2& \\ a^2-4a+2=0& \\ (a-2)^2=2& \\ \Rightarrow\quad a=2\pm\sqrt{2}& \quad\checkmark \end{align} $$

---

Solution. We complete the square and re-express the equation:

$$ \begin{align} x^2+ax+y^2+by&=c \\ \left(x+\frac{a}2\right)^2+\left(y+\frac{b}2\right)^2&=c+\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2 \end{align} $$

So the centre is at $\left(-\frac{a}2,-\frac{b}2\right)$ and the radius is $\sqrt{c+\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2}$. In order to contain the origin inside the circle, we need: $$ \begin{align} r&>OP \\ \sqrt{c+\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2}&>\sqrt{\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2} \\ c+\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2&>\left(\frac{a}2\right)^2+\left(\frac{b}2\right)^2 \\ \Rightarrow\quad c&>0 \end{align} $$

Hence, the answer is (a).

---

Solution. We factorise the equation:

$$ \begin{align} \cos^n(x)+\cos^{2n}(x)&=0 \\ \cos^n(x)\left[1+\cos^n(x)\right]&=0 \\ \Rightarrow\quad \underbrace{\cos(x)=0}_{{\rm 2\;solutions}}\quad{\rm or}\quad \cos^n(x)&=-1 \end{align} $$

For $\cos^n(x)=-1$, we find no solutions for $n$ even and 1 solution for $n$ odd ($\cos(x)=-1$ which gives $x=\pi$). Thus, the answer is (d).

---

Solution. The basic shape is guided by $y=(x-1)^2$ and $y=\cos(\pi x)$ add oscillations to it. Let's check a few points:

$$ \begin{align} && y&=(x-1)^2-\cos(\pi x) \\ x=0\;:&& y(0)&=(-1)^2-\cos(0)=0 \\ x=1\;:&& y(1)&=-\cos(\pi)=1 \\ x=2\;:&& y(2)&=1^2-\cos(2\pi)=0 \\ x=3\;: && y(3)&=2^2-\cos(3\pi)=5 \end{align} $$

We notice that there are no zeroes for $x<0$ and $x>2$. For $0\le x\le 2$, $\cos(\pi x)$ has one full period, i.e. the curve must show one cycle of oscillation. Hence, the answer is (a).

---

Solution. By the factor theorem, in order to have $x^2+1$ as a factor, substituting $x^2=-1$ into the equation should yield zero, i.e.

$$ \begin{align} f(x)&=\left(3+x^4\right)^n-\left(x^2+3\right)^n\left(x^2-1\right)^n \\ \Rightarrow\quad f\left(x^2=-1\right)&=(3+1)^n-(-1+3)^n(-2)^n \\ &=4^n-2^n(-2)^n \end{align} $$

and this becomes zero when $n$ is even. Hence, the answer is (b).

---

Comment: Alternatively, we may use $x^2+1=(x+i)(x-i)$ and test $x=\pm i$ and the result reads the same:

$$ \begin{align} x=i\;:&& f(i)&=\left(3+i^4\right)^n-\left(i^2+3\right)^n\left(i^2-1\right)^n =4^n-2^n(-2)^n \\ x=-i\;:&& f(-i)&=\left(3+(-i)^4\right)^n-\left((-i)^2+3\right)^n\left((-i)^2-1\right)^n=4^n-2^n(-2)^n \end{align} $$

---

Solution. We write down the first few terms to recognise any pattern:

$$ \begin{align} x_0&=1 \\ x_1&=1 \\ x_2&=x_0+x_1=2 \\ x_3&=x_0+x_1+x_2=4 \\ x_4&=x_0+x_1+x_2+x_3=8 \\ x_5&=x_0+x_1+x_2+x_3+x_4=16 \\ &\;\vdots \\ x_n&=x_0+x_1+\cdots+x_{n-1}=2^{n-1},\quad x\ge1 \end{align} $$

So the sum

$$ \begin{align} \sum_{k=0}^\infty\frac1{x_k}&=x_0+\sum_{k=1}^\infty\frac1{2^{k-1}} \\ &=1+\left(1+\frac12+\frac14+\frac18+\cdots\right) \\ &=1+2 \\ &=3 \end{align} $$

Hence, the answer is (d).

---

Solution. As we draw the diagram,

we want the purple area ($A_1$) bigger than the orange area ($A_2$). That is,

$$ \begin{align} A_1&=\int_{-\sqrt{a}}^{\sqrt{a}}\left(a-x^2\right)\,dx \\ &=2\int_0^{\sqrt{a}}\left(a-x^2\right)\,dx \\ &=2\left[ax-\frac13x^3\right]_0^{\sqrt{a}} \\ &=2\left(a^{\frac32}-\frac13a^{\frac23}\right) \\ &=\frac43a^{\frac32} \\ \\ A_2&=\left\vert\int_{-a^{\frac14}}^{a^{\frac14}}\left(x^4-a\right)\,dx\right\vert \\ &=\left\vert2\int_0^{a^{\frac14}}\left(x^4-a\right)\,dx\right\vert \\ &=\left\vert2\left[\frac15x^5-ax\right]_0^{a^{\frac14}}\right\vert \\ &=\left\vert2\left(\frac15a^{\frac54}-a^{\frac54}\right)\right\vert \\ &=\frac85a^{\frac54} \end{align} $$

which yields $$ \begin{align} A_1&>A_2 \\ \frac43a^{\frac32}&>\frac85a^{\frac54} \\ \Rightarrow\quad a^{\frac32-\frac54}&>\frac65 \\ \Rightarrow\quad a^{\frac14}&>\frac65 \\ \Rightarrow\quad a&>\left(\frac65\right)^4 \end{align} $$

Hence, the answer is (e).

---

Solution. Let $ax+by=c$. We want to know the maximum of $c$ which occurs at the extremum of the $y$-intercept of a straight line $\ell$:

$$ y=-\frac{a}{b}x+\frac{c}{b} $$

Without loss of generality due to symmetry which we will clarify shortly (see Comment 1 below), assume $a,b>0$. Then the maximum of the $y$-intercept occurs when the straight line is tangent to the circle, as shown in the diagram.

Assuming $a,b>0$

Since the gradient of the line $\ell$ is $-\frac{a}{b}$, the gradient of $OP$, which is perpendicular to $\ell$, is $\frac{b}{a}$. Therefore, the coordinates of $P$ on the unit circle are given by $$P=\left(\frac{a}{\sqrt{a^2+b^2}},\frac{b}{\sqrt{a^2+b^2}}\right)$$ and it determines the value of $c$:

$$ \begin{align} y&=-\frac{a}{b}x+\frac{c}{b} \\ P\quad\Rightarrow\quad\frac{b}{\sqrt{a^2+b^2}}&=-\frac{a}{b}\cdot\frac{a}{\sqrt{a^2+b^2}}+\frac{c}{b} \\ \Rightarrow\quad c&=\frac{a^2+b^2}{\sqrt{a^2+b^2}}=\sqrt{a^2+b^2} \quad\checkmark \end{align} $$

Hence, the answer is (c).

---

Comment 1: There are three other cases where the signs of $a,b$ are $(-,+),(-,-)$ and $(+,-)$, i.e. the point P is in the 2nd, 3rd and 4th quadrant, respectively. The diagrams below show that they all give rise to the same maximum value of $c$.

$a<0$ and $b>0$

$a<0$ and $b<0$

$a>0$ and $b<0$

---

Comment 2: Similar questions can be found in MAT 2005 Q1 J and MAT 2011 Q4 (i).

---

Comment 3: It can also be solved by the Cauchy-Schwarz inequality, $$ \mathbf u\cdot\mathbf v\le\Vert\mathbf u\Vert\Vert\mathbf v\Vert $$

Let $\mathbf u=\begin{pmatrix}a\\b\end{pmatrix}$ and $\mathbf v=\begin{pmatrix}x\\y\end{pmatrix}$, then we have $$ \begin{align} ax+by=\begin{pmatrix}a\\b\end{pmatrix}\cdot\begin{pmatrix}x\\y\end{pmatrix}&\le \left\Vert\begin{pmatrix}a\\b\end{pmatrix}\right\Vert\left\Vert\begin{pmatrix}x\\y\end{pmatrix}\right\Vert \\ &=\sqrt{a^2+b^2}\underbrace{\sqrt{x^2+y^2}}_{\le 1} \\ &\le\sqrt{a^2+b^2} \quad\checkmark \end{align} $$

---

Solution.

• (a) $\Pi(n)=1$ means that $n$ is of the form $p^m$ where $p$ is a prime number and $m$ some positive integer, e.g. $2^m$, $3^m$, $5^m$ and so on. If $x(n)$ is one of {4, 6, 8}, then $n=2^m$, $n\ge2$ and thus cannot be prime. Hence, the statement is true.
• (b) For $\Pi(n)=1$, we have $$ \begin{align} x\left(2^m\right)&\in\{2,4,6,8\} \\ x\left(3^m\right)&\in\{1,3,7,9\} \\ x\left(5^m\right)&\in\{5\} \\ x\left(7^m\right)&\in\{1,3,7,9\} \\ &\;\vdots \end{align} $$ so no values of $x(n)$ guarantees that $n$ is prime. Hence, the statement is false.
• (c) For $\Pi(n)=1$, since 10 is not prime, we can never have $x(n)=0$. Hence, the statement is true.
• (d) We can find at least two integers that satisfy $\Pi(n)+x(n)=2$, namely $$ \begin{align} n=10=2\times5\;:&&\Pi(10)&=2,& x(10)&=0 \\ n=11\,:&&\Pi(11)&=1,& x(11)&=1 \end{align} $$ and thus we cannot tell if $n$ is prime. Hence, the statement is true.
• (e) From findings of (b), it is clear that $$ x\left(p_1^{m_1}\times p_2^{m^2}\right)\in\{0,1,2,\cdots,9\} $$ For example,$$ \begin{align} x\left(2\times5\right)&=0 \\ x\left(3\times7\right)&=1 \\ x\left(2\times364\right)&=2 \\ x\left(3\times7^4\right)&=3 \\ x\left(2\times5\right)&=4 \\ x\left(3\times5\right)&=5 \\ x\left(2\times3\right)&=6 \\ x\left(3^3\times7^4\right)&=7 \\ x\left(2^3\times3^4\right)&=8 \\ x\left(3^2\times7^4\right)&=9 \end{align} $$ So the statement is true.

Hence, the answer is (b).

---

Solution. (i) [1 mark] We have:

$$ \begin{align} A(B(x))&=2B(x)+1=2(3x+2)+1=6x+5 \\ B(A(x))&=3A(x)+2=3(2x+1)+2=6x+5 \end{align} $$

---

(ii) [3 marks] We find the first few $A^n(x)=A(A(A(\cdots A(x)\cdots)$ and generalise the result: $$ \begin{align} A^2(x)&=A(A(x)) \\ &=2A(x)+1 \\ &=2(2x+1)+1 \\ &=2^2x+2+1 \\ \\ A^3(X)&=A\left(A^2(x)\right) \\ &=2A^2(x)+1 \\ &=2\left(2^2x+2+1\right)+1 \\ &=2^4x+2^2+2+1 \\ \\ A^4(x)&=A\left(A^3(x)\right) \\ &=2A^3(x)+1 \\ &=2\left(2^3x+2^2+2+1\right)+1 \\ &=2^4x+2^3+2^2+2+1 \\ &\;\vdots \\ A^n(x)&=2^nx+\underbrace{2^{n-1}+2^{n-2}+\cdots+2+1}_{{\rm a\; geometric\; series}} \\ &=2^nx+\frac{2^n-1}{2-1} \\ &=2^nx+\left(2^n-1\right)\quad\checkmark \end{align} $$

---

(iii) [4 marks] We want $F(x)=108x+c$. As we combine $A^m(x)$ and $B^n(x)$, for example: $$ \begin{align} A^2B(x)&=2^2B(x)+3=2^2(3x+2)+3=2^2\cdot3x+11 \\ B^2(x)&=3(3x+2)+2=3^2x+8 \\ AB^2(x)&=2\left(3^2x+8\right)+1=2\cdot3^2x+17 \\ A^2B^2(x)&=2^2B^2(x)+3=2^2\left(3^2x+8\right)+3=2^2\cdot3^2x+35 \end{align} $$ We notice that the coefficient of $x$ in $A^mB^n$ is of the form $2^m3^n$. Thus, by prime factorisation, $108=2^2\times3^3$, i.e. $F(x)$ requires two factors of $A$ and three factors of $B$, and there are $\binom{5}{2}=10$ possible combinations as follows: $$ \begin{align} AABBB \\ ABABB \\ ABBAB \\ ABBBA \\ BAABB \\ BABAB \\ BABBA \\ BBAAB \\ BBABA \\ BBBAA \\ \end{align} $$

---

(iv) [3 marks] Since $AB=BA$ by part (i), the 10 different possibilities above give rise to the same result and hence we expect to have only one possible value of $c$. $$ \begin{align} A^2(x)&=2^2x+3 \\ B^3(x)&=3^2B(x)+8=3^2(3x+2)+8=3^3x+26 \\ \Rightarrow\quad A^2B^3(x)&=2^2B^3(x)+3 \\ &=2^2\left(3^3x+26\right)+3 \\ &=2^2\cdot3^3x+107 \\ \Rightarrow\quad c&=107\quad\checkmark \end{align} $$ Aside: We can check this explicitly for all 10 of them, but perhaps not during the exam though. Here, we check two other 'randomly picked' ones: $$ \begin{align} ABAB(x)&=6AB(x)+5=6(6x+5)+5=36x+35 \\ BABAB(x)&=3(36x+35)+2=108x+107 \quad\checkmark \\ BBBAA(x)&=3^3A^2(x)+26=3^3\left(2^2x+3\right)+26=108x+107 \quad\checkmark \end{align} $$

---

(v) [4 marks] From part (iii), we want to find $(m_i,n_i)$ such that $$ 2^{m_1}3^{n_1}+2^{m_2}3^{n_2}+\cdots+2^{m_k}3^{n_k}=214 $$ As we list the values of the form $2^m3^n$ and less than 214, $$ \begin{align} (m,n)&& 2^m3^n& \\ \\ (1,1)&& 2^13^1&=6 \\ (1,2)&& 2^13^2&=18 \\ (2,1)&& 2^23^1&=12 \\ (2,2)&& 2^23^2&=36 \\ (1,3)&& 2^13^3&=54 \\ (2,3)&& 2^23^3&=108 \\ (3,3)&& 2^33^3&=216>214 \\ (3,1)&& 2^33^1&=24 \\ (3,2)&& 2^33^2&=72 \\ (4,1)&& 2^43^1&=48 \\ (4,2)&& 2^43^2&=144 \\ (5,1)&& 2^53^1&=96 \\ (6,1)&& 2^63^1&=192 \end{align} $$ In an ascending order: $$ 6\;,12\;,18\;,24\;,36\;,48\;,54\;,72\;,96\;,108\;,144\;,192 $$ and they are all multiples of 6. Since 214 is not a multiple of 6, we can't express it as $6m+6n+6p+\cdots$.

---

Comment: We could also work out the exact form of $B^n(x)$ and answer the question (iii) onwards. $$ \begin{align} B^2(x)&=B(B(x)) \\ &=3B(x)+2 \\ &=3(3x+2)+2 \\ &=3^2x+3\cdot2+2 \\ \\ B^3(x)&=B\left(B^2(x)\right) \\ &=3B^2(x)+2 \\ &=3\left(3^2x+3\cdot2+2\right)+2 \\ &=3^3x+3^2\cdot2+3\cdot2+2 \\ \\ B^4(x)&=B\left(B^3(x)\right) \\ &=3B^3(x)+2 \\ &=3\left(3^3x+3^2\cdot2+3\cdot2+2\right)+2 \\ &=3^4x+3^3\cdot2+3^2\cdot2+3\cdot2+2 \\ &\;\vdots \\ B^n(x)&=3^nx+2\underbrace{\left(3^{n-1}+3^{n-2}+\cdots+3+1\right)}_{{\rm a\; geometric\; series}} \\ &=3^nx+2\frac{3^n-1}{3-1} \\ &=3^nx+\left(3^n-1\right) \end{align} $$

We can now provide an alternative approach to part (v). We notice that both $A^m(x)$ and $B^n(x)$ have a constant coefficient one less than the $x$ coefficient: $$ \begin{align} A^m(x)&=2^mx+\left(2^m-1\right) \\ B^n(x)&=3^nx+\left(3^n-1\right) \end{align} $$ We notice that this is also true for $A^mB^n(x)$: $$ \begin{align} A^mB^n(x)&=2^mB^n(x)+\left(2^m-1\right) \\ &=2^m\left(3^nx+3^n-1\right)+\left(2^m-1\right) \\ &=2^m3^nx+2^m\left(3^n-1\right)+\left(2^m-1\right) \\ &=2^m3^nx+\left(2^m3^n-1\right) \end{align} $$ In part (v), the right hand side reads $214x+92$, i.e. it must be the sum of $214-92=122$ functions of the form $A^mB^n$: $$ \sum_{k=1}^{122}A^{m_k}B^{n_k}(x)=214x+92 $$ For positive integers $(m_k,n_k)$, the minimal function would be $AB(x)=6x+5$ and hence the minimum value of the $x$ coefficient of 122 such functions is $6\times122=732$. Hence, it is not possible to find such functions with the $x$ coefficient of 214.

 

---

Solution. We note that the bilateral condition is a symmetry about $x=\alpha$. To see this more explicitly, let $x=\alpha-t$ and the condition becomes

$$ f(\alpha-t)=f(\alpha+t) $$

Comment: 'Bilateral' means 'having or relating two sides' and the 'bilateral symmetry' is a terminology in biology that describes organisms with a single plane of symmetry.

 

(i) [1 mark] $f(x)=(x-\alpha)^2$ is symmetric about $x=\alpha$ so we expect it to be bilateral, and can also show this by an explicit calculation: $$ \begin{align} f(x)&=(x-\alpha)^2 \\ \Rightarrow\quad f(2\alpha-x) &=(2\alpha-x-\alpha)^2 \\ &=(\alpha-x)^2 \\ &=(x-\alpha)^2 \\ &=f(x) \qquad\square \end{align} $$

 

(ii) [2 marks] For $f(x)=x-\alpha$ with no symmetry, we find: $$ \begin{align} f(x)&=x-\alpha \\ \Rightarrow\quad f(2\alpha-x) &=(2\alpha-x)-\alpha \\ &=\alpha-x \\ &=-(x-\alpha) \\ &=-f(x) \end{align} $$ hence $f(x)$ is not bilateral$.\quad\checkmark$

 

(iii) [2 marks] We show it by an explicit calculation: For $n\in\mathbb Z_+$, $$ \begin{align} \int_a^bx^n\,dx &=\left[\frac1{n+1}x^{n+1}\right]_a^b \\ &=\frac1{n+1}\left(b^{n+1}-a^{n+1}\right) \\ &=-\frac1{n+1}\left(a^{n+1}-b^{n+1}\right) \\ &=-\left[\frac1{n+1}x^{n+1}\right]_b^a \\ &=-\int_b^ax^n\,dx\qquad\square \end{align} $$

 

(iv) [3 marks] We can write a general polynomial of degree $n$ as a sum: $$ f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n=\sum_{r=0}^na_rx^r $$ Then, $$ \begin{align} \int_a^bf(x)\,dx &=\int_a^b\left(\sum_{r=0}^na_rx^r\right)\,dx \\ &=\int_a^b\left(a_0+a_1x+\cdots+a_nx^n\right)\,dx \\ &=a_0+a_1\int_a^bx\,dx+a_2\int_a^bx^2\,dx+\cdots+a_n\int_a^bx^n\,dx \\ &=\sum_{r=0}^na_r\underbrace{\left(\int_a^bx^r\,dx\right)}_{-\int_b^ax^r\,dx} \\ &=-\sum_{r=0}^na_r\left(\int_b^ax^r\,dx\right) \\ &=-\int_b^a\sum_{r=0}^na_rx^r\,dx \\ &=-\int_b^af(x)\,dx \qquad\square \end{align} $$

 

(v) [2 marks] We consider a bilateral function, i.e. a symmetric function about $x=\alpha$ as shown in the diagram below.

An example of bilateral functions, i.e. symmetric about $x=\alpha$

By symmetry, the two shaded areas (orange and purple) are equal:

$$ A_{{\rm orange}}=\int_\alpha^tf(x)\,dx=\int_{2\alpha-t}^\alpha f(x)\,dx=A_{{\rm purple}} \qquad\square $$

 

(vi) [2 marks] We find

$$ \begin{align} G(t)&\equiv\int_\alpha^tf(x)\,dx \\ &=\int_{2\alpha-t}^\alpha f(x)\,,dx \quad{\rm by\;(v)} \\ &=-\int_\alpha^{2\alpha-t}f(x)\,dx \quad{\rm by\;(iv)} \\ &=-G(2\alpha-t) \qquad\square \end{align} $$

 

(vii) [2 marks] Now, both $f$ and $G$ are bilateral, i.e.

$$ \begin{align} f\;{\rm bilateral\;}&:& G(t)&=-G(2\alpha-t) \\ G\;{\rm bilateral\;}&:& G(t)&=G(2\alpha-t) \\ \\ && \Rightarrow\quad G(t)&=-G(t) \\ &&\Rightarrow\quad G(t)&=0 \qquad\square \end{align}$$

---

Solution. We draw a diagram with the circles $C_1$ and $C_2$ as shown below.

(i) [3 marks] The centres of the circles touching both $l$ and the $x$-axis lie on the bisector of the angle $2\alpha$, i.e. since the gradient of the bisector is $\tan\alpha$, the centres are on the line: $$ y = (\tan\alpha)x $$

Suppose that the centre $P$ has coordinates $(a,b)$. Now, the radius of $C_1$ is 1, so we find $b=1$. Since $P$ is on the line $y=(\tan\alpha)x$, we find

$$ \begin{gather} 1=(\tan\alpha)a\qquad\Rightarrow\qquad a=\frac1{\tan\alpha} \\ \therefore\quad P=\left(\frac1{\tan\alpha},1\right) \end{gather} $$

 

(ii) [1 mark] The equation of circle $C_1$ then reads

$$ \left(x-\frac1{\tan\alpha}\right)^2+(y-1)^2=1$$

 

(iii) [3 marks] The circle $C_2$ satisfies the same conditions except that its radius is 3 so we find:

$$ \begin{gather} {\rm Centre\;:}\qquad Q=\left(\frac3{\tan\alpha},3\right) \\ C_2\;:\qquad \left(x-\frac3{\tan\alpha}\right)^2+(y-3)^2=9 \end{gather} $$

For $C_1$ and $C_2$ to touch as shown in the diagram below,

$C_1$ and $C_2$ are touching

the triangle $APQ$ must form a right-angled triangle with $PQ=4$, $AQ=2$ and $PQ=\frac2{\tan\alpha}$. By Pythagoras' theorem,

$$ \begin{align} AP&=\sqrt{PQ^2-AQ^2} \\ \Rightarrow\quad \frac3{\tan\alpha}-\frac1{\tan\alpha}&=\sqrt{4^2-2^2} \\ \Rightarrow\quad \frac2{\tan\alpha}&=2\sqrt{3} \\ \Rightarrow\quad \tan\alpha&=\frac1{\sqrt{3}} \\ \therefore\quad\alpha&=\frac{\pi}6 \quad\checkmark \end{align} $$

Aside: With $\alpha=\frac{\pi}6$, the equations of $C_1$ and $C_2$ read: $$ \begin{align} C_1\;:&& \left(x-\sqrt{3}\right)^2+(y-1)^2&=1 \\ C_2\;:&& \left(x-3\sqrt{3}\right)^2+(y-3)^2&=9 \end{align} $$

 

(iv) [3 marks] We have another circle $C_3$ touching both lines as well as $C_2$, as shown in the diagram below.

$C_3$ touches both lines and $C_2$

The equation of $C_3$ reads (recall $\alpha=\frac{\pi}6$)

$$ \begin{align} \left(x-\frac{r}{\tan\alpha}\right)^2+(y-r)^2&=r^2 \\ \alpha=\frac{\pi}6\quad\Rightarrow\quad \left(x-r\sqrt{3}\right)^2+(y-r)^2&=r^2 \end{align} $$

The triangle $BQR$ now forms a right-angled triangle with

$$ \begin{align} QR&=r+3 \\ RB&=r-3 \\ QB&=\frac{r}{\tan\alpha}-\frac{3}{\tan\alpha}=\frac{r-3}{\tan\alpha}=\sqrt{3}(r-3) \end{align} $$

By Pythagoras' theorem, we find

$$ \begin{align} QB^2+RB^2&=QR^2 \\ \left[\sqrt{3}(r-3)\right]^2+(r-3)^2&=(r+3)^2 \\ 4(r-3)^2&=(r+3)^2 \\ \Big[2(r-3)+(r+3)\Big]\Big[2(r-3)-(r+3)\Big]&=0 \\ (3r-3)(r-9)&=0 \\ \Rightarrow\quad r=1\quad{\rm or}\quad r&=9 \end{align} $$

The radius of $C_1$ corresponds to $r=1$, so the radius of $C_3$ is $r=9.\quad\checkmark$

 

Comment: It appears that the subsequent radii form a geometric sequence with the common ratio 3, is this a coincidence? We can generalise this result a little further - see An investigation below.

 

(v) [5 marks] We want the orange area shown in the diagram below.

It is given by:

$$ \begin{align} A_{\rm orange}&=A_{{\rm trapezium\;}PMNQ}-A_{\rm blue}-A_{\rm purple} \\ &=\frac{1+3}2\times2\sqrt{3}-\frac12\left(\frac{\pi}2+\frac{\pi}6\right)-\frac12\cdot3^2\cdot\left(\frac{\pi}2-\frac{\pi}6\right) \\ &=4\sqrt{3}-\frac{\pi}3-\frac{3\pi}2 \\ &=4\sqrt{3}-\frac{11}6\pi \quad\checkmark \end{align} $$

 

An investigation for enthusiasts. We may consider a more general situation and find the relation between the radii of subsequent circles and the angle $\alpha$.

(a) Show that the radii form a geometric sequence with the common ratio $$r=\frac{1+\sin\alpha}{1-\sin\alpha}$$(b) The area of the region bounded by the $x$-axis and the circles $C_1$ and $C_2$ is given by $$ A=\frac12\left(\frac1{\tan\alpha}+\alpha\right)\left(r_2^2-r_1^2\right)-\frac{\pi}4\left(r_1^2+r_2^2\right) $$

(a) Without loss of generality, we investigate the relation between $r_1$ and $r_2$. The equations of circles $C_1$ and $C_2$ read: $$ \begin{align} C_1\;:&& \left(x-\frac{r_1}{\tan\alpha}\right)^2+(y-r_1)^2&=r_1^2 \\ C_2\;:&& \left(x-\frac{r_2}{\tan\alpha}\right)^2+(y-r_2)^2&=r_2^2 \end{align} $$ There are two equivalent approaches to find the relation between $r_1$, $r_2$ and $\alpha$:

• In the triangle $PAQ$, we can read off $\sin\alpha$: $$ \sin\alpha=\frac{r_2-r_1}{r_2+r_1} $$
• We could also apply Pythagoras' theorem to $\triangle PAQ$ with $P\left(\frac{r_1}{\tan\alpha},r_1\right)$ and $Q\left(\frac{r_2}{\tan\alpha},r_2\right)$, $$ \begin{align} PA^2+AQ^2&=PQ^2 \\ \left(\frac{r_2-r_1}{\tan\alpha}\right)^2+(r_2-r_1)^2&=(r_1+r_2)^2 \\ \Rightarrow\quad \left(\frac1{\tan^2\alpha}+1\right)(r_2-r_1)^2&=(r_1+r_2)^2 \\ \Rightarrow\quad \left(\frac{1+\tan^2\alpha}{\tan^2\alpha}\right)(r_2-r_1)^2&=(r_1+r_2)^2 \\ \Rightarrow\quad \left(\frac{\sec^2\alpha}{\tan^2\alpha}\right)(r_2-r_1)^2&=(r_1+r_2)^2 \\ \Rightarrow\quad \sin^2\alpha&=\left({r_2-r_1}{r_2+r_1}\right)^2 \end{align} $$ This is indeed equivalent to the first approach.

Rearranging the equation yields $$ r_2=\left(\frac{1+\sin\alpha}{1-\sin\alpha}\right)r_1 \qquad\square $$ (b) The interstitial area bounded by the $x$-axis and the two circles is: $$ \begin{align} A&=A_{\rm Trapezium}-A_{C_1\;{\rm sector}}-A_{C_2\;{\rm sector}} \\ &=\left(\frac{r_1+r_2}2\right)\frac{r_2-r_1}{\tan\alpha}-\frac12r_1^2\left(\frac{\pi}2+\alpha\right)-\frac12r_2^2\left(\frac{\pi}2-\alpha\right) \\ &=\frac{r_2^2-r_1^2}{2\tan\alpha}-\frac{\pi}4\left(r_1^2+r_2^2\right)+\frac{\alpha}2\left(r_2^2-r_1^2\right) \\ &=\frac12\left(\frac1{\tan\alpha}+\alpha\right)\left(r_2^2-r_1^2\right)-\frac{\pi}4\left(r_1^2+r_2^2\right) \end{align} $$ and we do not see an obvious relation for the subsequent interstitial areas.

 

A final cross-check: For $\alpha=\frac{\pi}6$ and $r_1=1$, we find: $$ \begin{align} {\rm Common\;ratio\;}:&& r&=\frac{1+\sin\frac{\pi}6}{1-\sin\frac{\pi}6}=\frac{1+\frac12}{1-\frac12}=3\quad\checkmark \\ {\rm Interstitial\;area\;}:&& A&=4\left(\frac1{\tan\frac{\pi}6}+\frac{\pi}6\right)-\frac{5\pi}2=4\sqrt{3}-\frac{11\pi}6\quad\checkmark \end{align} $$ as in Question 4 above.

---

Solution. (i) [3 marks] We have $$ \begin{align} f(n)&=(An+B)2^n+C \\ &=2+8+24+\cdots+n2^n=\sum_{r=1}^nr2^r \end{align} $$ and setting $n=1,2,3$ yield: $$ \begin{align} f(1)&=2A+2B+C=2 \\ f(2)&=8A+4B+C=10 \\ f(3)&=24A+8B+C=34 \end{align} $$

---

(ii) [3 marks] We solve the simultaneous equations: $$ \begin{align} \frac{f(2)-f(1)}2&=3A+B=4 \\ \frac{f(3)-f(2)}4&=4A+B=6 \\ \\ \Rightarrow\quad A&=2 \\ B&=-2 \\ {\rm and}\quad C&=2 \end{align} $$

---

(iii) [2 marks] This is essentially an inductive step: we assume $$ s_n=f(n)=(2n-2)2^n+2 $$ and find $$ \begin{align} s_{n+1} &=s_n+(n+1)2^{n+1} \\ &=(2n-2)2^n+2+(n+1)2^{n+1} \\ &=(2n-2)2^n+2+(2n+2)2^n \\ &=(4n)2^n+2 \\ &=\big[2(n+1)-2\big]2^n+2 \\ &=f(n+1)\qquad\square \end{align} $$

---

(iv) [4 marks] We have: $$ \begin{align} t_n&=n+2(n-1)+4(n-2)+8(n-3)+\cdots+2^{n-1}1 \\ &=n+2(n-1)+2^2(n-2)+2^3(n-3)+\cdots+2^{n-1}1 \\ &=\sum_{r=0}^{n-1}2^r(n-r) \\ &=n\sum_{r=0}^{n-1}2^r-\sum_{r=0}^{n-1}r2^r \\ &=n\sum_{r=0}^{n-1}2^r-\underbrace{\sum_{r=1}^{n-1}r2^r}_{=s_{n-1}} \\ &=n\left(\frac{2^n-1}{2-1}\right)-\Big(\big[2(n-1)-2\big]2^{n-1}+2\Big) \\ &=n\left(2^n-1\right)-(n-2)2^n-2 \\ &=2^{n+1}-n-2 \quad\checkmark \\ \\ u_n&=\frac12+\frac24+\frac38+\cdots+\frac{n}{2^n} \\ &=\frac12+\frac2{2^2}+\frac3{2^3}+\cdots+\frac{n}{2^n} \\ &=\sum_{r=1}^n\frac{r}{2^r} \\ &=\sum_{r=1}^nr2^{-r} \\ &=\frac1{2^n}\sum_{r=1}^nr2^{n-r} \\ &=\frac1{2^n}\underbrace{\left(2^{n-1}+2^{n-2}2+\cdots+2^2(n-2)+2^1(n-1)+n\right)}_{=t_n} \\ &=\frac1{2^n}\left(2^{n+1}-n-2\right) \\ &=2-\frac{n+2}{2^n} \quad\checkmark \end{align} $$

---

(v) [3 marks] We find: $$ \begin{align} \sum_{k=1}^ns_k &=\sum_{k=1}^n\Big((2k-2)2^k+2\Big) \\ &=2\underbrace{\sum_{k=1}^nk2^k}_{s_n}-2\sum_{k=1}^n2^k+2\underbrace{\sum_{k=1}^n1}_{=n} \\ &=2\Big((2n-2)2^n+2\Big)-2\left[\frac{2\left(2^n-1\right)}{2-1}\right]+2n \\ &=(n-1)2^{n+2}+4-2^{n+2}+4+2n \\ &=(n-2)2^{n+2}+2n+8 \quad\checkmark \end{align} $$

Exercise. Derive $$ s_n=\sum_{r=1}^nr2^r=(2n+2)2^n+2 $$ from first principles.

Solution. It is analogous to the derivation of a geometric series: $$ \begin{align} s_n&=2+8+24+\cdots+n2^n \\ &=2^1+2\cdot2^2+3\cdot2^3+\cdots+n\cdot2^n=\sum_{r=1}^nr2^r \\ 2s_n&=2^2+2\cdot2^3+\cdots+(n-1)2^n+n\cdot2^{n+1} \\ \\ \Rightarrow\quad -s_n&=\underbrace{2^1+2^2+2^3+\cdots+2^n}_{{\rm a\;geometric\;series}}-n\cdot2^{n+1} \\ &=\frac{2\left(2^n-1\right)}{2-1}-2^{n+1}n \\ \Rightarrow\quad s_n&=2^{n+1}n-2\left(2^n-1\right) \\ &=(n-1)2^{n+1}+2 \qquad\square \end{align} $$

---

Solution. (i) [3 marks] We notice that we may think of the four dancers in a circle. In order to perform an off-beat dance, there must be at least one dancer who is 1. We consider the two cases where (a) $A=0$, (b) $A=1$.

• Case 1: $A=0$. Then, in order for $A$ to be off-beat, either $(B,C)=(1,0)$ (first) or $(B,C)=(0,1)$ (second in the diagram above). In order for $D$ to be off-beat, $D=0$. Then, among $B$ and $C$, the dancer with 0 cannot be off-beat.
• Case 2: $A=1$. Then, in order for $A$ to be off-beat, $(B,C)=(0,0)$ (third) or $(B,C)=(1,1)$ (fourth in the diagram above). In order for $D$ to be off-beat, $D=1$. If $(B,C,D)=(0,0,1)$, then $B$ and $C$ are not off-beat., and $(B,C,D)=(1,1,1)$ is not allowed in the question.
• Therefore, it is not possible for the four dancers to perform an off-beat dance.

Aside: One could also consider the three cases where (a) there is one dancer with 1, (b) two dancers with 1s, (c) three dancers with 1s. (Since there must always be at least a 1 and a 0 in the group, we do not consider the case where all four dancers are 1s, although this is an interest case - see Comment 1 below.)

• Case 1 - One dancer with 1: Without loss of generality, assume $A=1$ (first in the diagram above). Then, $D$ cannot be off-beat. Hence, it is not possible to perform an off-beat dance with only one dancer with 1.
• Case 2 - Two dancers with 1s: Without loss of generality, assume $(A,B)=(1,1)$ or $(A,D)=(1,1)$. For $(A,B)=(1,1)$ (second in the diagram above), $A$ and $B$ cannot be off-beat. For $(A,D)=(1,1)$ (third in the diagram above), both $B$ and $C$ cannot be off-beat. Hence it is not possible to perform an off-beat dance with two dancers with 1s.
• Case 3 - Three dancers with 1s: Without loss of generality, assume $(A,B,C)=(1,1,1)$ (fourth in the diagram above). Then, $D$ cannot be off-beat. Hence it is not possible to perform an off-beat dance with three dancers with 1s.
• Therefore, it is not possible for the four dancers to perform an off-beat dance.

Comment 1: If all four dancers were with 1s, they would perform an off-beat dance, but this is not allowed in the question.

Comment 2: Our first approach is easier to generalise for the subsequent parts (ii), (iii), (iv) and we make use of the second approach for (v) and (vi) of the question.

 

(ii) [3 marks] Similarly, we divide the scenarios into two cases where (a) $A=0$, (b) $A=1$.

• Case 1: $A=0$. Then, in order for $A$ to be off-beat, either $(B,F)=(1,0)$ (left) or $(B,F)=(0,1)$ (middle in the diagram above). In order for $B$ to be off-beat, $C$ has to be different from $B$, i.e. if $B=1$ then $C=0$; and if $B=0$ then $C=1$. In order for $C$ to be off-beat, $D$ has to be the same as $A$. In fact, in order for $D$ to be off-beat, $E$ has to be the same as $B$. In order for $E$ to be off-beat, $F$ has to be the same as $C$. In other words, whenever we consider a new dancer, the new dancer has to be the same the third previous dancer, i.e. it is $A$ for $D$, it is $B$ for $E$ and it is $C$ for $F$.
• Case 2: $A=1$. Then, in order for $A$ to be off-beat, $(B,F)=(0,0)$ (right in the diagram above). In order for $B$ to be off-beat, $C=0$. In order for $C$ to be off-beat, $D$ has to be the same as $A$ and we notice that the previous logic persists.
• Therefore, there are 3 possible ways for six dancers to perform an off-beat dance, as shown in the diagram above.

(iii) [3 marks] From part (ii), we notice that as long as the new dancer is the same as the third previous dancer, it is possible to perform an off-beat dance, That is, as long as the number of dancers is a multiple of 3, this is possible.

 

(iv) [2 marks] Now, the dancers hold hands with dancers one person away from them around the ring. A moment's thought suggests that there is actually one ring of dancers for $n$ odd, while there are two rings of dancers for $n$ even, as shown in the diagram below.

Examples of odd and even numbers of dancers: There is one ring for $n$ odd and two rings (red and purple) for $n$ even.

• For $n$ odd, there is one ring of dancers and this has to be a multiple of 3 from part (iii), i.e. $$ n=6k+3=3(2k+1),\quad k\in\mathbb Z_+$$
• For $n$ even, there are two rings of dancers and each ring has to be a multiple of 3, i.e. $$ \begin{gather} n=3p+3q=3(p+q)\quad{\rm such\;that}\quad p+q=2k,\quad k\in\mathbb Z_+ \\ \Rightarrow\quad n=6k,\quad k\in\mathbb Z_+ \end{gather}$$

(v) [1 mark] All four aliens are holding hands with each other, as shown in the diagram below. For an off-beat dance, there are two cases: (a) only one dancer is 1 (b) three dancers are 1s.

All four aliens are holding hands with each other

• Case 1 - One dancer with 1: Without loss of generality, assume $A=1$, then the other three have to be 0s. By symmetry, there are three other possibilities where $B,C$ or $D$ is $0$ and the other three are 1s. That is, there are ${}_4C_1=4$ possible ways with one 1 and three 0s, as shown in the diagram below.

  

  4 possible ways with one 1 and three 0s

• Case 2 - Three dancers with 1s: It means that only one dancer is with 0. Without loss of generality, assume $A=0$. Again, by symmetry, there are ${}_4C_1=4$ possible ways with one 0 and three 1s, as shown in the diagram below.

  

  4 possible ways with three 1s and one 0

• Conclusion: There are 8 different ways in total.

(vi) [3 marks] The six aliens hold hands with their direct neighbours and the alien opposite them in the ring, as shown in the diagram below.

Six aliens holding hands

Without loss of generality, let's focus on $A$. From part (v), we just need to examine 6 cases - 3 cases from one 1 and three 0s, and another 3 cases from three 1s and one 0. (There were two other cases in part (v) with $(A,B,D,F)=(0,0,0,1)$ and $(1,0,1,1)$, but they are symmetric and thus equivalent to $(0,1,0,0)$ and $(1,1,1,0)$ respectively.)

6 cases to be examined: 3 cases with only one 1 (left) & another 3 cases with three 1s (right)

A careful examination shows that the first and the sixth cases give rise to an off-beat dance. These are:

Two possible off-beat dances

Therefore, there are 2 possible ways.

---

Comment: This question is an example taken from 『Concrete Mathematics』 by Graham, Knuth and Patashnik, 2nd Edition, Chapter 7 Generating Functions, 7.3 Solving Recurrences, Example 6.

 

Solution. (i) [2 marks] There are three 2-spans:

(ii) [4 marks] There are eight 3-spans:

Top group size 1 on the first row, size 2 on the second row and size 3 on the third row

(iii) [3 marks] As advised, we focus on the possible sizes of the top groups of tips and how the group is connected to the hub. If we look at our answers to parts (i) and (ii), we notice that:

• Among three 2-spans, there are two possible sizes of the top groups $1$ and $2$: one is with the group size 1 and two with the group size 2.
• Among eight 3-spans, there are three possible sizes of the top groups $1,2$ and $3$: three are with the size 1, two with the size 2 and three with the size 3.

For 4-fans, there are four possible sizes of the top group, namely, $1,2,3$ and $4$.

1. First of all, we work out 4-spans with the top group size 4 and there are four of them as shown in the diagram.

   

   Four 4-spans with the top group size 4

   Further, a moment's thought suggests that there are always $n$ n-spans with the top group size $n$. $$ \begin{align} z_n({\rm size\;n})&=n \\ z_4({\rm size\;4})&=4 \end{align} $$ where $z_n$ denotes the number of $n$-spans.

2. For 4-spans with the top group size 1, we can produce these by attaching an extra tip to the top of every one of eight 3-spans as shown in the diagram.

   

   4-spans with the top group size 1 are produced by attaching an extra tip (in red) to the previous eight 3-spans

   i.e. we can express this as: $$ z_4({\rm size}\;1)=z_3 $$

3. For 4-spans with the top group size 2, let's count separately the possilities for the top group of 2 tips and the rest which also has 2 tips.

   

   4-spans with the top group size 2

   (a) For the top group of 2 tips, there are 2 possibilities as we noted earlier in 1 that there are always $n$ $n$-spans with the top group size $n$. Here we want the number of 2-spans with the top group size 2, and thus it is 2. (b) For the remaining 2 tips, the number of possibilities is equal to the number of 2-spans, i.e. $z_2=3$. $$ z_4({\rm size\;2})=2z_2 $$
4. For 4-spans with the top group size 3, we similarly find:

   

   4-spans with the top group size 3

   (a) For the top group of 3 tips, there are 3 possibilities. (b) For the remaining 1 tip, we have $z_1=1$ possibility. $$ z_4({\rm size\;3})=3z_1 $$

Therefore, as we add them all, we find:

$$ \begin{align} z_4&=z_4({\rm size\;1}) +z_4({\rm size\;2}) +z_4({\rm size\;3}) +z_4({\rm size\;4}) \\ &=z_3+2z_2+3z_1+4 \\ &=8+6+3+4 \\ &=21 \quad\checkmark \end{align} $$

 

(iv) [4 marks] We can generalise this to $z_n$. Let's apply the logic developed in part (iii) to $z_5$ and then $z_n$. $$ z_5=z_5({\rm size\;1}) +z_5({\rm size\;2}) +z_5({\rm size\;3}) +z_5({\rm size\;4}) +z_5({\rm size\;5}) $$

• For $z_5({\rm size\;1})$, we can produce these by attaching an extra tip to each one of 4-spans, i.e. $$z_5({\rm size\;1})=z_4$$
• $z_5({\rm size\;2})$: (a) For the top group of size 2, we have 2 possibilities. (b) For the remaining 3 tips, we have $z_3$ possibilities. $$ z_5({\rm size\;2})=2z_3 $$
• $z_5({\rm size\;3})$: (a) For the top group of size 3, we have 3 possibilities. (b) For the remaining 2 tips, we have $z_2$ possibilities. $$ z_5({\rm size\;3})=3z_2 $$
• $z_5({\rm size\;4})$: (a) For the top group of size 4, we have 4 possibilities. (b) For the remaining 1 tip, we have $z_1$ possibilities. $$ z_5({\rm size\;4})=4z_1 $$
• For $z_5({\rm size\;5})$, we have 5 possibilities. $$ z_5({\rm size\;5})=5 $$

Thus we find $$ \begin{align} z_5&=z_5({\rm size\;1}) +z_5({\rm size\;2}) +z_5({\rm size\;3}) +z_5({\rm size\;4}) +z_5({\rm size\;5}) \\ &=z_4+2z_3+3z_2+4z_1+5 \end{align} $$ and further generalise to $z_n\,$: $$ \begin{align} z_n&=z_n({\rm size\;1}) +z_n({\rm size\;2}) +z_n({\rm size\;3}) +\cdots +z_n({\rm size\;n-1}) +z_n({\rm size\;n}) \\ &=z_{n-1}+2z_{n-2}+3z_{n-3}+\cdots+(n-1)z_1+n \\ &=\sum_{k=1}^{n-1}kz_{n-k}+n \quad\checkmark \end{align} $$ Let's check our answers using this formula: $$ \begin{align} z_1&=1 \\ z_2&=z_1+2=1+2=3 \\ z_3&=z_2+2z_1+3=3+2+3=8 \\ z_4&=z_3+2z_2+3z_1+4=8+6+3+4=21 \\ z_5&=z_4+2z_3+3z_2+4z_1+5=21+16+9+4+5=55\quad\checkmark \end{align} $$

 

(v) [2 marks] It is now a simple application: $$ \begin{align} z_6&=z_5+2z_4+3z_3+4z_2+5z_1+6 \\ &=55+42+24+12+5+6 \\ &=144 \quad\checkmark \end{align} $$

Aside: If we let $z_0=1$, then we can write the formula as $$ z_n=\sum_{k=1}^nkz_{n-k} $$