Year: 2011
Paper: 3
Question Number: 7
Course: LFM Pure
Section: Proof by induction
The percentages attempting larger numbers of questions were higher this year than formerly. More than 90% attempted at least five questions and there were 30% that didn't attempt at least six questions. About 25% made substantive attempts at more than six questions, of which a very small number indeed were high scoring candidates that had perhaps done extra questions (well) for fun, but mostly these were cases of candidates not being able to complete six good solutions.
Difficulty Rating: 1700.0
Difficulty Comparisons: 0
Banger Rating: 1486.2
Banger Comparisons: 1
Let
\[
T _n =
\left( \sqrt{a+1} + \sqrt a\right)^n\,,
\]
where $n$ is a positive integer and $a$ is any given positive integer.
\begin{questionparts}
\item
In the case when $n$ is even, show
by induction that
$T_n$ can be written in the form
\[
A_n +B_n \sqrt{a(a+1)}\,,
\]
where
$A_n$ and $B_n$ are integers (depending on $a$ and $n$)
and $A_n^2 =a(a+1)B_n^2 +1$.
\item In the case when $n$ is odd, show by considering
$(\sqrt{a+1} +\sqrt a)T_m$ where $m$ is even, or otherwise,
that $T_n$
can be written in the form
\[
C_n \sqrt {a+1} + D_n \sqrt a \,,
\]
where $C_n$ and $D_n$ are integers (depending on $a$ and $n$) and
$ (a+1)C_n^2 = a D_n^2 +1\,$.
\item Deduce that, for each $n$, $T_n$ can be written
as the sum of the square roots of two consecutive integers.
\end{questionparts}\begin{questionparts}
\item Claim: For all $n \geq 1$ $T_{2n} = A_{2n} + B_{2n}\sqrt{a(a+1)}$ where $A_{2n}, B_{2n}$ are integers and $A_{2n}^2 = a(a+1)B_{2n}^2+1$
Proof: (By induction)
Base case: $n =1$.
\begin{align*}
&& T_2 &= (\sqrt{a+1}+\sqrt{a})^2 \\
&&&= a+1+2\sqrt{a(a+1)}+a \\
&&&=2a+1+2\sqrt{a(a+1)} \\
\Rightarrow && A_2 &= 2a+1 \\
&& B_2 &= 2 \\
&& A_2^2 &= 4a^2+4a+1 \\
&& a(a+1)B_1^2 + 1 &= 4a^2+4a+1
\end{align*}
Therefore our base case is true. Suppose it is true for some $n = k$ then consider $n = k+1$ we must have $T_{2k} = A_{2k}+B_{2k}\sqrt{a(a+1)}$
\begin{align*}
&& T_{2(k+1)} &= T_{2k} (\sqrt{a+1}+\sqrt{a})^2 \\
&&&= \left (A_{2k}+B_{2k}\sqrt{a(a+1)} \right)\left (2a+1+2\sqrt{a(a+1)} \right) \\
&&&= (2a+1)A_{2k}+2a(a+1)B_{2k} + (2A_{2k}+(2a+1)B_{2k})\sqrt{a(a+1)} \\
\Rightarrow && A_{2(k+1)} &= (2a+1)A_{2k}+2a(a+1)B_{2k} \in \mathbb{Z} \\
&& B_{2(k+1)} &= 2A_{2k}+(2a+1)B_{2k} \in \mathbb{Z} \\
&& A_{2(k+1)}^2 &= \left ( (2a+1)A_{2k}+2a(a+1)B_{2k} \right)^2 \\
&&&= (2a+1)^2A_{2k}^2+4a^2(a+1)^2B_{2k}^2+4a(a+1)(2a+1)A_{2k}B_{2k} \\
&&&= a^2(a+1)^2(2a+1)^2B_{2k}^2+(2a+1)^2\\
&&&\quad\quad+4a^2(a+1)^2B_{2k}^2+4a(a+1)(2a+1)A_{2k}B_{2k}\\
&& a(a+1)B_{2(k+1)}^2 + 1 &= a(a+1)\left ( 2A_{2k}+(2a+1)B_{2k} \right)^2 \\
&&&= 4a(a+1)A_{2k}^2 + 4a(a+1)(2a+1)A_{2k}B_{2k} + a(a+1)(2a+1)^2B_{2k}^2 + 1\\
&&&= 4a^2(a+1)^2B_{2k}^2+4a(a+1) + \\
&&&\quad\quad+ 4a(a+1)(2a+1)A_{2k}B_{2k} + a(a+1)(2a+1)^2B_{2k}^2 + 1
\end{align*}
So our relation holds ad therefore by induction we're done.
\item When $n$ is odd, notice that
\begin{align*}
&& T_n &= (\sqrt{a+1}+\sqrt{a})(A_m+B_m\sqrt{a(a+1)})\\
&&&= \sqrt{a+1}(\underbrace{A_m+aB_m}_{C_n})+\sqrt{a}(\underbrace{(a+1)B_m+A_m}_{D_n}) \\
\\
&& (a+1)C_n^2 &= (a+1)(A_m+aB_m)^2 \\
&&&= (a+1)(A_m^2+2aA_mB_m+B_m^2) \\
&&&= (a+1)(a(a+1)B_m^2+1+2aA_mB_m+B_m^2) \\
&&&= a(a+1)^2B_m^2 + 2a(a+1)A_mB_m+(a+1)B_m^2+a+1 \\
&& aD_n^2+1 &= a((a+1)^2B_m + 2(a+1)A_mB_m + A_m^2)+1 \\
&&&= a(a+1)^2B_m + 2a(a+1)A_mB_m + aB_{m}^2+a+1
\end{align*}
\item For even $n$ $T_n = \sqrt{a(a+1)B_{2n}^2+1} + \sqrt{a(a+1)B_{2n}^2}$
For odd $n$, $T_n = \sqrt{aD_n^2+1}+ \sqrt{aD_n^2}$ therefore it is always the sum of the square root of two consecutive integers.
\end{questionparts}
The popularity and success rate of this was very similar to question 6. Quite a few failed to realise the importance of the relation involving 1 as part of the induction, and even if they did tripped up on that part of the working. Part (ii) generally went well and the result in Cₙ and Dₙ was found more easily. Very few had a problem with part (iii) but a small number failed totally to see what it was about.