Hi, I'm stuck on this MI from Cambridge (Y12 3U: Ex 2A Q10).
"Prove by mathematical induction that for all positive integers n,
(n + 1) (n + 2) (n + 3) × · · · × 2n = 2^n × ( 1 × 3 × 5 × · · · × (2n − 1) ) ."
I'm used to seeing the · · ·'s only on one side, so I'm not sure what to do when they're on both sides. Thanks in advance!
(Also from the 1999 exam if I recall. It appears both there and Cambridge.)
\[ \text{When }n=1,\\ LHS = 1\times 2 = 2,\\ RHS = 2^1(1) = 2. \]
\[ \text{Assume that}\\ (k+1)(k+2)(k+3)\cdots 2k = 2^k (1\times 3\times 5\times \cdots \times (2k-1)) \]
Everyone always gets confused at this question because it's a bit tricky writing out what you need to prove for the inductive step. On the \(RHS\), this should be a bit more obvious - simply increment the power by 1, and add in the next term.
Now on the left, both the
first term and the
last term are affected here, since they both have \(k\)'s in them. When \(n=k\), the first term was \(k+1\). When \(n=k+1\), the first term is \(k+2\).
When \(n=k\) the last term was \(2k\). When \(n=k+1\), the last term thus must be \(2(k+1)\), i.e. \(2k+2\).
So in the inductive step, we wish to prove that
\[(k+2)(k+3)\cdots (2k)(2k+1)(2k+2) = 2^{k+1} (1\times 3\times 5\times \cdots \times (2k-1)(2k+1)) \]
\begin{align*}
LHS &= (k+2)(k+3)\cdots (2k)(2k+1)(2k+2)\\
&= 2(k+1)(k+2)(k+3)\cdots (2k)(2k+1)\\
&= 2\left[2^{k} (1\times3\times5\times\cdots\times(2k-1) \right](2k+1)\\
&= 2^{k+1} (1\times3\times5\times\cdots\times(2k-1)(2k+1))
\end{align*}