# Proving $r!$ divides the product of r succesive positive integers

I have to prove the following theorem:

Prove that the product of $r$ consecutive positive integers in divisible by $r!$

I am having a hard time getting a generalization down for the full set of real numbers, if I start from 1 and work up to r, I have the following:

$$r!k=\prod_{i=1}^{r}n_i$$

Can easily prove the base case of this, (n=1), and then go in to prove:

$$(r+1)!k=\prod_{i=1}^{r+1}n_i$$

Expand that out and get:

$$(r+1)r!k=n(n+1)(n+2).....(n+r)(n+r+1)$$

Can say that the product of the first $r$ elements in equal to $r!k$ by our base case. Leaving using with:

$$(r+1)k=(n+r+1)$$

Not sure where I can go from here, n is the integer that we start at, so how can I get it to work out to be equal to our induction hypothesis?

-
Hint: ${n+r\choose r}$ is an integer. –  vadim123 Feb 4 '14 at 17:23
Thanks for the hint, got it now. –  Richard P Feb 7 '14 at 3:34

You can do this by simultaneous induction on $r$ and $n$. Note that

\begin{align} (n+1)\cdots(n+r)&=(n+1)\cdots(n+r-1)n\quad+\quad(n+1)\cdots(n+r-1)r\\ &=((n-1)+1)\cdots((n-1)+r)\quad+\quad(n+1)\cdots(n+(r-1))r \end{align}

(I inserted a little extra space around the central plus signs to make the key pieces easier to see.) By induction on $n$, $r!$ divides $((n-1)+1)\cdots((n-1)+r)$, and by induction on $r$, $(r-1)!$ divides $(n+1)\cdots(n+(r-1))$, hence $r!$ divides $(n+1)\cdots(n+(r-1))r$.

(Please note, I'm glossing over all the fine points of getting the inductions started.)

-


$${n\pars{n + 1}\ldots\pars{n + r - 1} \over r!} = {n + r - 1 \choose r} \quad\mbox{which is an integer !!!}$$

-