Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
Hint: ${n+r\choose r}$ is an integer. –  vadim123 Feb 4 at 17:23
    
Thanks for the hint, got it now. –  Richard P Feb 7 at 3:34

2 Answers 2

up vote 3 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|improve this answer

$\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|improve this answer

Your Answer

 
discard

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.