Why is $(n+1)(n+2)cdots(n+s)$ divisible by $s!$? [duplicate]

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

This question already has an answer here:

• 
  The product of $n$ consecutive integers is divisible by $n$ factorial
  
  7 answers
  
  

Why is

$$(n+1)(n+2) cdots (n+s), text with n,s in ℕ$$

divisible by $s!$ ?

I derived this from the formula that gives the number of combinations of class $k$ with $n$ elements:

$$fracn!k!(n-k)!$$

combinatorics divisibility

share|cite|improve this question

edited Aug 1 at 19:52

asked Aug 1 at 19:46

davide

1155

marked as duplicate by Sil, Delta-u, Dietrich Burde, Micah, Taroccoesbrocco Aug 2 at 0:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
  – Jack D'Aurizio♦
  Aug 1 at 19:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
  – Doug M
  Aug 1 at 19:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
  – A. Pongrácz
  Aug 1 at 19:53
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
  – davide
  Aug 1 at 19:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh, that is odd. I see now, this question makes much more sense.
  – A. Pongrácz
  Aug 1 at 19:54
  

  
  
  
  

 | 
show 3 more comments

up vote
2
down vote

favorite

This question already has an answer here:

• 
  The product of $n$ consecutive integers is divisible by $n$ factorial
  
  7 answers
  
  

Why is

$$(n+1)(n+2) cdots (n+s), text with n,s in ℕ$$

divisible by $s!$ ?

I derived this from the formula that gives the number of combinations of class $k$ with $n$ elements:

$$fracn!k!(n-k)!$$

combinatorics divisibility

share|cite|improve this question

edited Aug 1 at 19:52

asked Aug 1 at 19:46

davide

1155

marked as duplicate by Sil, Delta-u, Dietrich Burde, Micah, Taroccoesbrocco Aug 2 at 0:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
  – Jack D'Aurizio♦
  Aug 1 at 19:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
  – Doug M
  Aug 1 at 19:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
  – A. Pongrácz
  Aug 1 at 19:53
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
  – davide
  Aug 1 at 19:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh, that is odd. I see now, this question makes much more sense.
  – A. Pongrácz
  Aug 1 at 19:54
  

  
  
  
  

 | 
show 3 more comments

up vote
2
down vote

favorite

up vote
2
down vote

favorite

This question already has an answer here:

• 
  The product of $n$ consecutive integers is divisible by $n$ factorial
  
  7 answers
  
  

Why is

$$(n+1)(n+2) cdots (n+s), text with n,s in ℕ$$

divisible by $s!$ ?

I derived this from the formula that gives the number of combinations of class $k$ with $n$ elements:

$$fracn!k!(n-k)!$$

combinatorics divisibility

share|cite|improve this question

edited Aug 1 at 19:52

asked Aug 1 at 19:46

davide

1155

This question already has an answer here:

• 
  The product of $n$ consecutive integers is divisible by $n$ factorial
  
  7 answers
  
  

Why is

$$(n+1)(n+2) cdots (n+s), text with n,s in ℕ$$

divisible by $s!$ ?

I derived this from the formula that gives the number of combinations of class $k$ with $n$ elements:

$$fracn!k!(n-k)!$$

This question already has an answer here:

• 
  The product of $n$ consecutive integers is divisible by $n$ factorial
  
  7 answers
  
  

combinatorics divisibility

share|cite|improve this question

edited Aug 1 at 19:52

asked Aug 1 at 19:46

davide

1155

share|cite|improve this question

share|cite|improve this question

edited Aug 1 at 19:52

edited Aug 1 at 19:52

edited Aug 1 at 19:52

asked Aug 1 at 19:46

davide

1155

asked Aug 1 at 19:46

davide

1155

asked Aug 1 at 19:46

davide

1155

1155

marked as duplicate by Sil, Delta-u, Dietrich Burde, Micah, Taroccoesbrocco Aug 2 at 0:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

marked as duplicate by Sil, Delta-u, Dietrich Burde, Micah, Taroccoesbrocco Aug 2 at 0:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
  – Jack D'Aurizio♦
  Aug 1 at 19:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
  – Doug M
  Aug 1 at 19:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
  – A. Pongrácz
  Aug 1 at 19:53
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
  – davide
  Aug 1 at 19:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh, that is odd. I see now, this question makes much more sense.
  – A. Pongrácz
  Aug 1 at 19:54
  

  
  
  
  

 | 
show 3 more comments

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
  – Jack D'Aurizio♦
  Aug 1 at 19:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
  – Doug M
  Aug 1 at 19:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
  – A. Pongrácz
  Aug 1 at 19:53
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
  – davide
  Aug 1 at 19:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh, that is odd. I see now, this question makes much more sense.
  – A. Pongrácz
  Aug 1 at 19:54
  

  
  
  
  

5

5

Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
– Jack D'Aurizio♦
Aug 1 at 19:48

Binomial coefficients are integers by induction, since $binomnk=binomn-1k+binomn-1k-1$. It follows that $frac(n+s)!n!=s!binomn+sn$ is an integer too.
– Jack D'Aurizio♦
Aug 1 at 19:48

for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
– Doug M
Aug 1 at 19:50

for all $kle s, k$ divides at least one factor of $(n+1)(n+2)...(n+s)$
– Doug M
Aug 1 at 19:50

There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
– A. Pongrácz
Aug 1 at 19:53

There is a mistake in the post, you meant divisible by $s$. The cleanest explanation is, as you suggested, with the binomial coefficient, which is an integer. So in fact, a much stronger statement is true: $(n+s)!/n!$ is divisible by $s!$ as well.
– A. Pongrácz
Aug 1 at 19:53

@mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
– davide
Aug 1 at 19:53

@mrtaurho the question was edited (not by me) and the assertion became wrong. I restored it now.
– davide
Aug 1 at 19:53

Oh, that is odd. I see now, this question makes much more sense.
– A. Pongrácz
Aug 1 at 19:54

Oh, that is odd. I see now, this question makes much more sense.
– A. Pongrácz
Aug 1 at 19:54

 | 
show 3 more comments

3 Answers
3

active

oldest

votes

up vote
0
down vote

Every sequence of $m$ consecutive integers has one member divisible by $m$. For example, two consecutive integers contain one integer divisible by $2$, three consecutive integers contain one integer divisible by $3$, and so on. $s$ consecutive integers not only has one integer divisible by $s$, but it also contains at least one sub sequence of $s-a$ integers for all $1le a <s$. Thus a sequence of $s$ consecutive integers, regardless of the starting point $n$, will have integers in it divisible by every integer $1le ale s$, so the product of the members of that sequence will be divisible by $s!$

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This has the same problem Mike Earnest pointed out in the other answer.
  – qwr
  Aug 1 at 20:13
  

  
  
  
  

add a comment | 

up vote
0
down vote

Let $N = (n+1)(n+2)cdots (n+s)$. We must show that for each prime $p$, the number of times $p$ occurs in the prime factorization of $N$ is at least that the number of times $p$ occurs in $s!$.

Let $m_i$ be the number of entries in the list $L=(n+1,n+2,dots,n+s)$ which are divisible by $p^i$. You can convince yourself that the number of factors of $p$ in $N$ is
$$
m_1 + m_2 + m_3 + dots
$$
I claim that
$$
m_i ge lfloor s/p^irfloor
$$
This follows because, breaking $L$ into $lfloor s/p^irfloor$ disjoint sections of $p^i$ consecutive integers (with some numbers left over), each section contains exactly one multiple of $p^i$. Therefore, the number of $p$'s in $N$ is at least
$$
lfloor s/prfloor + lfloor s/p^2rfloor + lfloor s/p^3rfloor + dots
$$
But you can also show that the above is exactly the number of occurences of $p$ in $s!$, by the same reasoning. This completes the proof.

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

add a comment | 

up vote
0
down vote

We know that the number ways to pick $s$ items from $n + s$ choices must be $frac (n + 1)(n+2).....(n+s)s!=frac (n+s)!n!$ by basic combinatorics so $s!$ must divide $(n + 1)(n+2).....(n+s)$.

It used to astonish me that a practical explanation was much simpler than an algebraic proof. It galled my actually.

An algebraic proof should be simple: As there are $s$ consecutive terms $s$ will divide exactly one of the terms. Then $s-1$ will divide one of the terms (at least) and $s-2$ will divide one of the terms. And so on so $s!$ should divide the product.

The trouble that as $k$ will divide a term and $m$ will divide a term, it is possible that they divide the same term and we could be over counting.

Consider a prime $ple s$ and suppose ... well will do this step by step:

If $p le s < 2p$ then $p^1|s!$ is the highest power that divide $s!$ and of the $sge p$ consecutive terms, one is divisible by $p$ so $p|frac (n+s)!n!$. And the highest fact of $p$ that divides $s!$ divide $frac (n+s)!n!$ and we can move on to the next prime factor of $s!$. We don't have to worry about double counting because once we are done with $p$ we will be dealing with terms relatively prime to $p$.

If $k*p le s < (k+1)*p le p^2$, then there are $k$ terms in $1,... s$ that are divisible by $p$ and $p^k|s!$ is the highest term that divide $s!$. Now $p$ must divide one of the terms $n+1,...., n+p$ terms. Call that term $m$ and $p$ must divide each of the terms $m+p....., m+ (k-1)p le n+ kp le n+s$. So $p^k|frac (n+s)!n!$.

And if $k*p^m + j*p^m-1 + .... le s$. We can repeat the above steps to get that there are $k$ terms in $n+1,... ,n+s$ that are $v, v+p^m,... , v + (k-1)p^m$ that are divisible by $p^m$. of the remaining terms there are $j$ terms that are each divisible by $p^m-1$ and so on. Thus $p^km + j(m-1) + ...|s!$ is the highest power of $p$ that divides $s!$ and $p^km + j(m-1) + ...|frac (n+s)!n!$.

And that's it. We won't double count by divide all prime factors of $s!$ out of $frac (n+s)!n!$.

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

add a comment | 

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

Every sequence of $m$ consecutive integers has one member divisible by $m$. For example, two consecutive integers contain one integer divisible by $2$, three consecutive integers contain one integer divisible by $3$, and so on. $s$ consecutive integers not only has one integer divisible by $s$, but it also contains at least one sub sequence of $s-a$ integers for all $1le a <s$. Thus a sequence of $s$ consecutive integers, regardless of the starting point $n$, will have integers in it divisible by every integer $1le ale s$, so the product of the members of that sequence will be divisible by $s!$

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This has the same problem Mike Earnest pointed out in the other answer.
  – qwr
  Aug 1 at 20:13
  

  
  
  
  

add a comment | 

up vote
0
down vote

Every sequence of $m$ consecutive integers has one member divisible by $m$. For example, two consecutive integers contain one integer divisible by $2$, three consecutive integers contain one integer divisible by $3$, and so on. $s$ consecutive integers not only has one integer divisible by $s$, but it also contains at least one sub sequence of $s-a$ integers for all $1le a <s$. Thus a sequence of $s$ consecutive integers, regardless of the starting point $n$, will have integers in it divisible by every integer $1le ale s$, so the product of the members of that sequence will be divisible by $s!$

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This has the same problem Mike Earnest pointed out in the other answer.
  – qwr
  Aug 1 at 20:13
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

Every sequence of $m$ consecutive integers has one member divisible by $m$. For example, two consecutive integers contain one integer divisible by $2$, three consecutive integers contain one integer divisible by $3$, and so on. $s$ consecutive integers not only has one integer divisible by $s$, but it also contains at least one sub sequence of $s-a$ integers for all $1le a <s$. Thus a sequence of $s$ consecutive integers, regardless of the starting point $n$, will have integers in it divisible by every integer $1le ale s$, so the product of the members of that sequence will be divisible by $s!$

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

Every sequence of $m$ consecutive integers has one member divisible by $m$. For example, two consecutive integers contain one integer divisible by $2$, three consecutive integers contain one integer divisible by $3$, and so on. $s$ consecutive integers not only has one integer divisible by $s$, but it also contains at least one sub sequence of $s-a$ integers for all $1le a <s$. Thus a sequence of $s$ consecutive integers, regardless of the starting point $n$, will have integers in it divisible by every integer $1le ale s$, so the product of the members of that sequence will be divisible by $s!$

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

share|cite|improve this answer

share|cite|improve this answer

answered Aug 1 at 20:05

Keith Backman

38427

answered Aug 1 at 20:05

Keith Backman

38427

answered Aug 1 at 20:05

Keith Backman

38427

38427

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This has the same problem Mike Earnest pointed out in the other answer.
  – qwr
  Aug 1 at 20:13
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  This has the same problem Mike Earnest pointed out in the other answer.
  – qwr
  Aug 1 at 20:13
  

  
  
  
  

1

1

This has the same problem Mike Earnest pointed out in the other answer.
– qwr
Aug 1 at 20:13

This has the same problem Mike Earnest pointed out in the other answer.
– qwr
Aug 1 at 20:13

add a comment | 

up vote
0
down vote

Let $N = (n+1)(n+2)cdots (n+s)$. We must show that for each prime $p$, the number of times $p$ occurs in the prime factorization of $N$ is at least that the number of times $p$ occurs in $s!$.

Let $m_i$ be the number of entries in the list $L=(n+1,n+2,dots,n+s)$ which are divisible by $p^i$. You can convince yourself that the number of factors of $p$ in $N$ is
$$
m_1 + m_2 + m_3 + dots
$$
I claim that
$$
m_i ge lfloor s/p^irfloor
$$
This follows because, breaking $L$ into $lfloor s/p^irfloor$ disjoint sections of $p^i$ consecutive integers (with some numbers left over), each section contains exactly one multiple of $p^i$. Therefore, the number of $p$'s in $N$ is at least
$$
lfloor s/prfloor + lfloor s/p^2rfloor + lfloor s/p^3rfloor + dots
$$
But you can also show that the above is exactly the number of occurences of $p$ in $s!$, by the same reasoning. This completes the proof.

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

add a comment | 

up vote
0
down vote

Let $N = (n+1)(n+2)cdots (n+s)$. We must show that for each prime $p$, the number of times $p$ occurs in the prime factorization of $N$ is at least that the number of times $p$ occurs in $s!$.

Let $m_i$ be the number of entries in the list $L=(n+1,n+2,dots,n+s)$ which are divisible by $p^i$. You can convince yourself that the number of factors of $p$ in $N$ is
$$
m_1 + m_2 + m_3 + dots
$$
I claim that
$$
m_i ge lfloor s/p^irfloor
$$
This follows because, breaking $L$ into $lfloor s/p^irfloor$ disjoint sections of $p^i$ consecutive integers (with some numbers left over), each section contains exactly one multiple of $p^i$. Therefore, the number of $p$'s in $N$ is at least
$$
lfloor s/prfloor + lfloor s/p^2rfloor + lfloor s/p^3rfloor + dots
$$
But you can also show that the above is exactly the number of occurences of $p$ in $s!$, by the same reasoning. This completes the proof.

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

add a comment | 

up vote
0
down vote

up vote
0
down vote

Let $N = (n+1)(n+2)cdots (n+s)$. We must show that for each prime $p$, the number of times $p$ occurs in the prime factorization of $N$ is at least that the number of times $p$ occurs in $s!$.

Let $m_i$ be the number of entries in the list $L=(n+1,n+2,dots,n+s)$ which are divisible by $p^i$. You can convince yourself that the number of factors of $p$ in $N$ is
$$
m_1 + m_2 + m_3 + dots
$$
I claim that
$$
m_i ge lfloor s/p^irfloor
$$
This follows because, breaking $L$ into $lfloor s/p^irfloor$ disjoint sections of $p^i$ consecutive integers (with some numbers left over), each section contains exactly one multiple of $p^i$. Therefore, the number of $p$'s in $N$ is at least
$$
lfloor s/prfloor + lfloor s/p^2rfloor + lfloor s/p^3rfloor + dots
$$
But you can also show that the above is exactly the number of occurences of $p$ in $s!$, by the same reasoning. This completes the proof.

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

Let $N = (n+1)(n+2)cdots (n+s)$. We must show that for each prime $p$, the number of times $p$ occurs in the prime factorization of $N$ is at least that the number of times $p$ occurs in $s!$.

Let $m_i$ be the number of entries in the list $L=(n+1,n+2,dots,n+s)$ which are divisible by $p^i$. You can convince yourself that the number of factors of $p$ in $N$ is
$$
m_1 + m_2 + m_3 + dots
$$
I claim that
$$
m_i ge lfloor s/p^irfloor
$$
This follows because, breaking $L$ into $lfloor s/p^irfloor$ disjoint sections of $p^i$ consecutive integers (with some numbers left over), each section contains exactly one multiple of $p^i$. Therefore, the number of $p$'s in $N$ is at least
$$
lfloor s/prfloor + lfloor s/p^2rfloor + lfloor s/p^3rfloor + dots
$$
But you can also show that the above is exactly the number of occurences of $p$ in $s!$, by the same reasoning. This completes the proof.

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

share|cite|improve this answer

share|cite|improve this answer

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

answered Aug 1 at 20:24

Mike Earnest

14.7k11644

14.7k11644

add a comment | 

add a comment | 

up vote
0
down vote

We know that the number ways to pick $s$ items from $n + s$ choices must be $frac (n + 1)(n+2).....(n+s)s!=frac (n+s)!n!$ by basic combinatorics so $s!$ must divide $(n + 1)(n+2).....(n+s)$.

It used to astonish me that a practical explanation was much simpler than an algebraic proof. It galled my actually.

An algebraic proof should be simple: As there are $s$ consecutive terms $s$ will divide exactly one of the terms. Then $s-1$ will divide one of the terms (at least) and $s-2$ will divide one of the terms. And so on so $s!$ should divide the product.

The trouble that as $k$ will divide a term and $m$ will divide a term, it is possible that they divide the same term and we could be over counting.

Consider a prime $ple s$ and suppose ... well will do this step by step:

If $p le s < 2p$ then $p^1|s!$ is the highest power that divide $s!$ and of the $sge p$ consecutive terms, one is divisible by $p$ so $p|frac (n+s)!n!$. And the highest fact of $p$ that divides $s!$ divide $frac (n+s)!n!$ and we can move on to the next prime factor of $s!$. We don't have to worry about double counting because once we are done with $p$ we will be dealing with terms relatively prime to $p$.

If $k*p le s < (k+1)*p le p^2$, then there are $k$ terms in $1,... s$ that are divisible by $p$ and $p^k|s!$ is the highest term that divide $s!$. Now $p$ must divide one of the terms $n+1,...., n+p$ terms. Call that term $m$ and $p$ must divide each of the terms $m+p....., m+ (k-1)p le n+ kp le n+s$. So $p^k|frac (n+s)!n!$.

And if $k*p^m + j*p^m-1 + .... le s$. We can repeat the above steps to get that there are $k$ terms in $n+1,... ,n+s$ that are $v, v+p^m,... , v + (k-1)p^m$ that are divisible by $p^m$. of the remaining terms there are $j$ terms that are each divisible by $p^m-1$ and so on. Thus $p^km + j(m-1) + ...|s!$ is the highest power of $p$ that divides $s!$ and $p^km + j(m-1) + ...|frac (n+s)!n!$.

And that's it. We won't double count by divide all prime factors of $s!$ out of $frac (n+s)!n!$.

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

add a comment | 

up vote
0
down vote

We know that the number ways to pick $s$ items from $n + s$ choices must be $frac (n + 1)(n+2).....(n+s)s!=frac (n+s)!n!$ by basic combinatorics so $s!$ must divide $(n + 1)(n+2).....(n+s)$.

It used to astonish me that a practical explanation was much simpler than an algebraic proof. It galled my actually.

An algebraic proof should be simple: As there are $s$ consecutive terms $s$ will divide exactly one of the terms. Then $s-1$ will divide one of the terms (at least) and $s-2$ will divide one of the terms. And so on so $s!$ should divide the product.

The trouble that as $k$ will divide a term and $m$ will divide a term, it is possible that they divide the same term and we could be over counting.

Consider a prime $ple s$ and suppose ... well will do this step by step:

If $p le s < 2p$ then $p^1|s!$ is the highest power that divide $s!$ and of the $sge p$ consecutive terms, one is divisible by $p$ so $p|frac (n+s)!n!$. And the highest fact of $p$ that divides $s!$ divide $frac (n+s)!n!$ and we can move on to the next prime factor of $s!$. We don't have to worry about double counting because once we are done with $p$ we will be dealing with terms relatively prime to $p$.

If $k*p le s < (k+1)*p le p^2$, then there are $k$ terms in $1,... s$ that are divisible by $p$ and $p^k|s!$ is the highest term that divide $s!$. Now $p$ must divide one of the terms $n+1,...., n+p$ terms. Call that term $m$ and $p$ must divide each of the terms $m+p....., m+ (k-1)p le n+ kp le n+s$. So $p^k|frac (n+s)!n!$.

And if $k*p^m + j*p^m-1 + .... le s$. We can repeat the above steps to get that there are $k$ terms in $n+1,... ,n+s$ that are $v, v+p^m,... , v + (k-1)p^m$ that are divisible by $p^m$. of the remaining terms there are $j$ terms that are each divisible by $p^m-1$ and so on. Thus $p^km + j(m-1) + ...|s!$ is the highest power of $p$ that divides $s!$ and $p^km + j(m-1) + ...|frac (n+s)!n!$.

And that's it. We won't double count by divide all prime factors of $s!$ out of $frac (n+s)!n!$.

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

add a comment | 

up vote
0
down vote

up vote
0
down vote

We know that the number ways to pick $s$ items from $n + s$ choices must be $frac (n + 1)(n+2).....(n+s)s!=frac (n+s)!n!$ by basic combinatorics so $s!$ must divide $(n + 1)(n+2).....(n+s)$.

It used to astonish me that a practical explanation was much simpler than an algebraic proof. It galled my actually.

An algebraic proof should be simple: As there are $s$ consecutive terms $s$ will divide exactly one of the terms. Then $s-1$ will divide one of the terms (at least) and $s-2$ will divide one of the terms. And so on so $s!$ should divide the product.

The trouble that as $k$ will divide a term and $m$ will divide a term, it is possible that they divide the same term and we could be over counting.

Consider a prime $ple s$ and suppose ... well will do this step by step:

If $p le s < 2p$ then $p^1|s!$ is the highest power that divide $s!$ and of the $sge p$ consecutive terms, one is divisible by $p$ so $p|frac (n+s)!n!$. And the highest fact of $p$ that divides $s!$ divide $frac (n+s)!n!$ and we can move on to the next prime factor of $s!$. We don't have to worry about double counting because once we are done with $p$ we will be dealing with terms relatively prime to $p$.

If $k*p le s < (k+1)*p le p^2$, then there are $k$ terms in $1,... s$ that are divisible by $p$ and $p^k|s!$ is the highest term that divide $s!$. Now $p$ must divide one of the terms $n+1,...., n+p$ terms. Call that term $m$ and $p$ must divide each of the terms $m+p....., m+ (k-1)p le n+ kp le n+s$. So $p^k|frac (n+s)!n!$.

And if $k*p^m + j*p^m-1 + .... le s$. We can repeat the above steps to get that there are $k$ terms in $n+1,... ,n+s$ that are $v, v+p^m,... , v + (k-1)p^m$ that are divisible by $p^m$. of the remaining terms there are $j$ terms that are each divisible by $p^m-1$ and so on. Thus $p^km + j(m-1) + ...|s!$ is the highest power of $p$ that divides $s!$ and $p^km + j(m-1) + ...|frac (n+s)!n!$.

And that's it. We won't double count by divide all prime factors of $s!$ out of $frac (n+s)!n!$.

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

We know that the number ways to pick $s$ items from $n + s$ choices must be $frac (n + 1)(n+2).....(n+s)s!=frac (n+s)!n!$ by basic combinatorics so $s!$ must divide $(n + 1)(n+2).....(n+s)$.

It used to astonish me that a practical explanation was much simpler than an algebraic proof. It galled my actually.

An algebraic proof should be simple: As there are $s$ consecutive terms $s$ will divide exactly one of the terms. Then $s-1$ will divide one of the terms (at least) and $s-2$ will divide one of the terms. And so on so $s!$ should divide the product.

The trouble that as $k$ will divide a term and $m$ will divide a term, it is possible that they divide the same term and we could be over counting.

Consider a prime $ple s$ and suppose ... well will do this step by step:

If $p le s < 2p$ then $p^1|s!$ is the highest power that divide $s!$ and of the $sge p$ consecutive terms, one is divisible by $p$ so $p|frac (n+s)!n!$. And the highest fact of $p$ that divides $s!$ divide $frac (n+s)!n!$ and we can move on to the next prime factor of $s!$. We don't have to worry about double counting because once we are done with $p$ we will be dealing with terms relatively prime to $p$.

If $k*p le s < (k+1)*p le p^2$, then there are $k$ terms in $1,... s$ that are divisible by $p$ and $p^k|s!$ is the highest term that divide $s!$. Now $p$ must divide one of the terms $n+1,...., n+p$ terms. Call that term $m$ and $p$ must divide each of the terms $m+p....., m+ (k-1)p le n+ kp le n+s$. So $p^k|frac (n+s)!n!$.

And if $k*p^m + j*p^m-1 + .... le s$. We can repeat the above steps to get that there are $k$ terms in $n+1,... ,n+s$ that are $v, v+p^m,... , v + (k-1)p^m$ that are divisible by $p^m$. of the remaining terms there are $j$ terms that are each divisible by $p^m-1$ and so on. Thus $p^km + j(m-1) + ...|s!$ is the highest power of $p$ that divides $s!$ and $p^km + j(m-1) + ...|frac (n+s)!n!$.

And that's it. We won't double count by divide all prime factors of $s!$ out of $frac (n+s)!n!$.

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

share|cite|improve this answer

share|cite|improve this answer

answered Aug 1 at 21:26

fleablood

60.1k22575

answered Aug 1 at 21:26

fleablood

60.1k22575

answered Aug 1 at 21:26

fleablood

60.1k22575

60.1k22575

add a comment | 

add a comment |