Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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


Expand that out and get:


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


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?

share|cite|improve this question
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
up vote 4 down vote accepted

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.)

share|cite|improve this answer
Sometimes induction doesn't need to be started. If $\forall n\in N (\; [ \forall m\in N \;( m<n \to ( \psi (m)\;) ] \; \to \psi (n) \;)$ then $\forall n\in N\; (\psi (n).$ – user254665 Jan 20 at 17:29

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\down}{\downarrow}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $$ n\pars{n + 1}\ldots\pars{n + r - 1}={\pars{n + r -1}! \over \pars{n - 1}!} ={\pars{n + r -1}! \over \pars{n - 1}!r!}\,r! = {n + r - 1 \choose r}r! $$

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

share|cite|improve this answer
Because it is the co-efficient of $x^r$ in the binomial expansion of $(1+x)^{n+r-1}.$ – user254665 Jan 20 at 16:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.