Divisibility of Product of Consecutive Integers

From ProofWiki
Jump to navigation Jump to search

Theorem

The product of $n$ consecutive positive integers is divisible by the product of the first $n$ consecutive positive integers.

That is:

$\displaystyle \forall m, n \in \Z_{>0}: \exists r \in \Z: \prod_{k \mathop = 1}^n \paren {m + k} = r \prod_{k \mathop = 1}^n k$


Proof

\(\displaystyle \prod_{k \mathop = 1}^n \paren {m + k}\) \(=\) \(\displaystyle \frac {\paren {m + n}!} {m!}\)
\(\displaystyle \) \(=\) \(\displaystyle n! \frac {\paren {m + n}!} {m! \, n!}\)
\(\displaystyle \) \(=\) \(\displaystyle n! \binom {m + n} m\) Definition of Binomial Coefficient
\(\displaystyle \) \(=\) \(\displaystyle \binom {m + n} m \prod_{k \mathop = 1}^n k\)


Hence the result, and note that for a bonus we have identified exactly what the divisor is:

$\dbinom {m + n} m$

$\blacksquare$


Examples

Product of $5$ to $8$

\(\displaystyle 5 \times 6 \times 7 \times 8\) \(=\) \(\displaystyle 1680\)
\(\displaystyle \) \(=\) \(\displaystyle 70 \times 24\)
\(\displaystyle \) \(=\) \(\displaystyle \binom 8 4 \times 1 \times 2 \times 3 \times 4\)


Product of $10$ to $13$

\(\displaystyle 10 \times 11 \times 12 \times 13\) \(=\) \(\displaystyle 17 \, 160\)
\(\displaystyle \) \(=\) \(\displaystyle 715 \times 24\)
\(\displaystyle \) \(=\) \(\displaystyle \binom {13} 4 \times 1 \times 2 \times 3 \times 4\)


Product of $4$ to $8$

\(\displaystyle 4 \times 5 \times 6 \times 7 \times 8\) \(=\) \(\displaystyle 6720\)
\(\displaystyle \) \(=\) \(\displaystyle 56 \times 120\)
\(\displaystyle \) \(=\) \(\displaystyle \binom 8 5 \times 1 \times 2 \times 3 \times 4 \times 5\)


Product of $11$ to $15$

\(\displaystyle 11 \times 12 \times 13 \times 14 \times 15\) \(=\) \(\displaystyle 360 \, 360\)
\(\displaystyle \) \(=\) \(\displaystyle 3003 \times 120\)
\(\displaystyle \) \(=\) \(\displaystyle \binom {15} 5 \times 11 \times 12 \times 13 \times 14 \times 15\)


Sources