Minus One Makes A Difference

This can be done directly by factoring out the denominator. We have:

$\frac{ 71 - 1}{1} \times \frac{71-2} {2} \times \frac{71-3}{3} \times \ldots = \frac{ 70 \times 69 \times \ldots \times (71-43) } { 1 \times 2 \times \ldots \times 43 }$

This is immediately recognizable as $70 \choose 43$ .

Unfortunately, it is not yet any of the options. We consider what else it could be expressed as. Using ${ n \choose m } = \frac{n}{m} { n-1 \choose m-1 }$ , we see that with $n=71, m = 44$ , the answer is $\frac{44}{71} { 71 \choose 44 }$ .

Let us define

$P_n=\left(\frac{71}{1}-1\right)\left(\frac{71}{2}-1\right)\cdots\left(\frac{71}{n}-1\right)$ where $n\leq 70$

We will use mathematical induction to prove that

$P_n=\frac{n+1}{71}\begin{pmatrix}71\\n+1\end{pmatrix}\dots\text{equation 1}$

Then the problem is easily completed since $P_{43}=\boxed{\frac{44}{71}\begin{pmatrix}71\\44\end{pmatrix}}$

Proof

Equation 1 is easily checked for $n=1$ . Now assume that it holds for $P_k$ . From the definition of $P_n$ we have

$P_{k+1}=P_k\left(\frac{71}{k+1}-1\right)=\frac{k+1}{71}\begin{pmatrix}71\\{k+1}\end{pmatrix}\frac{70-k}{k+1}=\frac{70-k}{71}\frac{71!}{(k+1)!(70-k)!}$

Multiplying the numerator and denominator by $(k+2)$ and doing some very careful cancelling gives

$P_{k+1}=\frac{k+2}{71}\frac{71!}{(k+2)!(71-(k+2)!}=\frac{k+2}{71}\begin{pmatrix}71\\k+2\end{pmatrix}$

We have shown that he formula holds for $n=1$ and that if it holds for $n=k$ then it holds for $n=k+1$ . Invoking the principle of mathematical induction then completes the proof.