So far I have that $k$ consecutive integers $(d+k)(d+k-1)(d+k-2) \cdots (d+1) = \frac{(d+k)!}{d!}$. How can I prove that $k!$ is the largest integer that divides the product of any $k$ consecutive integers without using the binomial theorem?
Asked
Active
Viewed 109 times
0
-
1I thought that the largest integer that divides $\frac{(d+k)!}{d!}$ is the number $\frac{(d + k)!}{d!}$. Am I missing something here? What is "the largest integer" supposed to mean here? – Ben Grossmann Sep 12 '16 at 02:25
-
k! is the answer in the book, and the original question is correct. I'm as confused as you are. – DERPYPENGUIN Sep 12 '16 at 02:26
-
1I would assume that the book wants you to fix $k$ and compute the gcd of all the numbers $k!/0!$, $(k+1)!/1!$, $(k+2)!/2!$, and so on. In which case Omnomnom's answer shows that $k!$ is a common divisor, and the fact that $k!$ is one of these numbers shows that it's the greatest one... – Micah Sep 12 '16 at 02:33
-
2That is, for "the largest integer that divides the product of $k$ consecutive integers" I would read "the largest integer that divides the product of any $k$ consecutive integers." – Micah Sep 12 '16 at 02:34
-
Edited the original question – DERPYPENGUIN Sep 12 '16 at 02:37
2 Answers
1
I assume you merely want to prove that $k!$ divides this product. Here's a combinatoric proof:
$(d+k) \cdots (d+1)$ is precisely the number of distinct arrangements of the numbers $1,2,\dots,(d+k-1),(d+k)$ that are $k$ digits long (and have no repetitions). Consider the list of such arrangements.
Note that for any one subset of $\{1,2,\dots,(d+k)\}$ with size $k$, there are $k!$ arrangements consisting of these elements. Thus, the number of elements is $k!$ multiplied by the number of subsets of size $k$. The conclusion follows.
Ben Grossmann
- 225,327
