Year: 2013
Paper: 1
Question Number: 6
Course: LFM Stats And Pure
Section: Binomial Theorem (positive integer n)
Around 1500 candidates sat this paper, a significant increase on last year. Overall, responses were good with candidates finding much to occupy them profitably during the three hours of the examination. In hindsight, two or three of the questions lacked sufficient 'punch' in their later parts, but at least most candidates showed sufficient skill to identify them and work on them as part of their chosen selection of questions. On the whole, nearly all candidates managed to attempt 4-6 questions – although there is always a significant minority who attempt 7, 8, 9, … bit and pieces of questions – and most scored well on at least two. Indeed, there were many scripts with 6 question-attempts, most or all of which were fantastically accomplished mathematically, and such excellence is very heart-warming.
Difficulty Rating: 1500.0
Difficulty Comparisons: 0
Banger Rating: 1501.4
Banger Comparisons: 2
By considering the coefficient of $x^r$ in the series for $(1+x)(1+x)^n$, or otherwise, obtain the following relation between binomial coefficients:
\[
\binom n r + \binom n {r-1} = \binom {n+1} r
\qquad (1\le r\le n).
\]
The sequence of numbers $B_0$, $B_1$, $B_2$, $\ldots$ is defined by
\[
B_{2m} = \sum_{j=0}^m \binom{2m-j}j
\text{ and }
B_{2m+1} = \sum_{k=0}^m \binom{2m+1-k}k
.
\]
Show that $B_{n+2} - B_{n+1} = B_{n}\,$ ($n=0$, $1$, $2$, $\ldots\,$).
What is the relation between the sequence $B_0$, $B_1$, $B_2$, $\ldots$ and the Fibonacci sequence $F_0$, $F_1$, $F_2$, $\ldots$ defined by $F_0=0$, $F_1=1$ and $F_n = F_{n-1}+F_{n-2}$ for $n\ge2$?The coefficient of $x^{r-1}$ in $(1+x)^n$ is $\binom{n}{r-1}$ and the coefficient of $x^r$ in $(1+x)^n$ is $\binom{n}{r}$. The only ways to get $x^r$ in the expansion of $(1+x)(1+x)^n$ is to either multiply the $x^r$ term from the second expansion by $1$ or the $x^{r-1}$ term by $x$. This is $\binom{n}{r-1} + \binom{n}{r}$.
However, the coefficient of $x^r$ in $(1+x)^{n+1}$ is $\binom{n+1}r$, so $\binom{n}{r} + \binom{n}{n-1} = \binom{n+1}r$.
Claim: $B_{n+2} - B_{n+1} = B_{n}$.
Proof: Consider $n$ even, ie $n = 2m$
\begin{align*}
B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} - \sum_{j=0}^m \binom{2m+1-j}{j} \\
&= \binom{2(m+1)-(m+1)}{m+1} +\sum_{j=0}^m \left ( \binom{2(m+1)-j}{j} - \binom{2m+1-j}{j} \right) \\
&= 1 + \sum_{j=1}^m \binom{2m+1-j}{j-1} \\
&= 1 + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\
&= \binom{m}{m} + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\
&= \sum_{j=0}^{m} \binom{2m-j}{j} \\
&= B_n
\end{align*}
Consider $n$ even, ie $n = 2m+1$
\begin{align*}
B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)+1-j}{j} - \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} \\
&= \sum_{j=0}^{m+1} \left (\binom{2(m+1)+1-j}{j} - \binom{2(m+1)-j}{j}\right)\\
&= \sum_{j=1}^{m+1} \binom{2(m+1)-j}{j-1} \\
&= \sum_{j=0}^{m} \binom{2m+1-j}{j} \\
&= B_n
\end{align*}
as required.
$B_0 = 1, B_1 = 2$, therefore $B_n = F_{n+2}$
Although this question attracted a few more attempts than Q3, it was the lowest-scoring of the pure maths questions. Confident use of the sigma-notation is clearly in short supply and this was, perhaps, that feature of the question that deterred most candidates from attempting it. Also, many attempts were simply from those candidates cherry-picking the opening three marks for proving the standard "Pascal's Triangle" result, mostly by proving it directly from the definition of the binomial coefficient in terms of factorials (which we had decided to allow when setting the paper). This almost invariably accounted for 3 of the 6.7 marks gained on average for the question as a whole. Those who proceeded further than this opening result generally fell into a couple of very wide traps: a careless handling of the terms at the ends of the series (which, being 1, could be replaced by other binomial coefficients that were also 1) and a failure to consider odd and even cases separately. A final obstacle, were one needed, lay in the oversight of establishing the validity of the relationship between the Bn's and the Fn's for their starting terms – surprisingly, many candidates failed to evaluate B0 and B1 correctly.