Talk:Factorial Divides Product of Successive Numbers

From ProofWiki
Jump to navigation Jump to search

I'm afraid I don't see what the problem is, LF. At which stage in the proof is there a problem? I'm invoking a result I'm planning on putting up today (the red link), that a set of $n$ successive numbers contains a multiple of $n$. Surely that's true, and then this follows? --GFauxPas (talk) 16:58, 12 November 2014 (UTC)

The problem lies therein that if it contains a multiple of $2$ and one of $6$, then it does not necessarily contain one of $2 \cdot 6$... I hope that's clear enough. — Lord_Farin (talk) 17:09, 12 November 2014 (UTC)
But the product of the numbers surely is a multiple of $12$? --GFauxPas (talk) 17:17, 12 November 2014 (UTC)
Unless both factors would come from the same number (and this doesn't happen, which is what we have to prove). — Lord_Farin (talk) 17:57, 12 November 2014 (UTC)
Is the proof salvageable? --GFauxPas (talk) 18:09, 12 November 2014 (UTC)

I don't know yet. I'm thinking about it. — Lord_Farin (talk) 18:16, 12 November 2014 (UTC)

I have a proof using primes, but it's not very elegant. I tried to continue with your idea but it is hard to define how to choose one of the possible elements of $S$ in a suitable way. — Lord_Farin (talk) 19:45, 12 November 2014 (UTC)
Perhaps comment the current proof out, put up yours, and I'll see if I think of a way to fix it. --GFauxPas (talk) 22:34, 12 November 2014 (UTC)
As has been pointed out, Divisibility of Product of Consecutive Integers is a proof of the same thing:
$m^{\overline n} = \dfrac {\left({m + n - 1}\right)!} {\left({m - 1}\right)!} = n! \dfrac {\left({m + n - 1}\right)!} {\left({m - 1}\right)! n!} = n! \dbinom {m + n - 1} {m - 1}$
As $\binom {m + n - 1} {m - 1}$ is an integer (there's a proof somewhere), the result follows. --prime mover (talk) 22:55, 12 November 2014 (UTC)
I was hoping to use this result to prove Binomial Coefficient is Integer. --GFauxPas (talk) 22:21, 13 November 2014 (UTC)
O yes of course, I see.
If you're just interested in proving that, and you're not emotionally committed to this approach here, can you not prove that by just using Pascal's Rule, induction, and the fact that the sum of two integers is itself an integer? --prime mover (talk) 22:34, 13 November 2014 (UTC)

That's a good idea. But I'd like to see what LF came up with. --GFauxPas (talk) 22:39, 13 November 2014 (UTC)

Basically, my proof is as follows (but it's not really easy to transform it into PW style):
For every prime $p$, we ought to prove $\operatorname{ord}_p(m^{\overline n}) \ge \operatorname{ord}_p(n!)$.
Then, provided $p \le n$:

$$\operatorname{ord}_p(\prod_{i=0}^{n-1} m+i) = \sum_{i=0}^{n-1}\operatorname{ord}_p(m+i) = \sum_{j=0}^{\lfloor n/p\rfloor}\operatorname{ord}_p(p\lceil m/p\rceil + jp) = \lfloor n/p\rfloor + \sum_{j=0}^{\lfloor n/p\rfloor} \operatorname{ord}_p(\lceil m/p\rceil + j)$$

$$\operatorname{ord}_p(\prod_{i=0}^{n-1} 1+i) = \sum_{i=0}^{n-1}\operatorname{ord}_p(1+i) = \sum_{j=0}^{\lfloor n/p\rfloor}\operatorname{ord}_p(p + jp) = \lfloor n/p\rfloor + \sum_{j=0}^{\lfloor n/p\rfloor} \operatorname{ord}_p(1+j)$$

and we apply induction to the last two sums. — Lord_Farin (talk) 19:35, 14 November 2014 (UTC)
Oh, it's $\lceil (n-1)/p \rceil$ in place of $\lfloor n/p\rfloor$ in the upper limits. — Lord_Farin (talk) 19:36, 14 November 2014 (UTC)
I'm guessing $\operatorname{ord}$ is the power of $p$ in the prime factorization? --GFauxPas (talk) 19:56, 14 November 2014 (UTC)
Indeed. — Lord_Farin (talk) 20:13, 14 November 2014 (UTC)