I have checked several cases numerically and it works. I don't have a concrete proof.
Does anyone have any thought on this to share ?
Isn it that such a product divided by k! is a binomial coefficient?
Thanks Patrick. Yep, that's right. I missed it altogether. I was working with another problem yesterday, which I could reduce it to this one, but then notice this observation. Thanks a lot.
Any book on introductory combinatorics will give you enough detail on binomial coefficients that Patric is talking about.
Yes, there follows the proof. Imagine that the product of the k consecutive positive integers start with the positive integer s. So you have s(s+1)(s+2) ...(s+k-1) = (s+k-1)! / (s-1)!. Divide it by k!, so you get (s+k-1)! / ((s-1)! k!) = binomial(s-1, k), which is always an integer, q.e.d.
Cassio Pagnoncelli, I am sorry but this is not a proof. You have merely rewritten expression as a binomial coefficient. Actually proof would consists of an argument which shows conclusively that everything in the denominator is cancelled out, leaving you with integers in the numerator.
But that is very hard to show in general. There will be so many cases to consider that it will be hard to keep track. But you can prove it for k = 3 though. You have to take some kind of combinatorial approach.
However, I am not saying you cannot do it in general. May be you can. Numbers are so mysterious and funny.
Cassio, you only expanded what Patrick expressed in gentle shortness. Tridib should nevertheless be able to interprete this as a full proof. We know (and should be able to prove) that binomial(s-1, k) equals the coeeficient of a x^k in the espansion of (1+x)^(s-1) (which gives rise to the name!) and, as such, obviously an integer! This is a nice example of an elementary fact that is easier proved in a suitable context than when approached directly.
This proof candidate seems pretty rigorous for me, Mr. Dutta. A simple argument proves binomial(s-1, k) is always an integer: there are exactly (s+k-1)!/((s-1)!k!) = binomial(s-1, k) distinct ways to pick k elements out from a population consisting of s-1 elements; hence, it is only permitted binomial(s-1, k) to be an integer, for s and k positive integers, since "# of distinct ways" is a non-negative integer.
Oh Fabricio, think again. That (s,k) |--> (s+k-1)!/((s-1)!k!) is of type NxN-->N is only a (silly!) reformulation of what we want to prove.
Ulrich, I'm sorry, I really don't understand how it's not a complete proof. Could you please explain me? Patrick's argument, for me, assets the same as a step-by-step machine-level proof would present.
Cassio, the proof ,using combinatorial argument is easy . What I tried to emphasis above was that a general proof, without resorting to any combinatorial argument, is extremely difficult. I think Ulrich is also saying this as well. Now, what you said in you first entry was not a proof, it was merely a restatement of the ( n C k ) formula, and hence cannot be considered a proof. Ulrich is also trying to explain the same thing to you.
Anyway, I think there is some misunderstanding here. Anyway, I guess it is now a bit more clear.
Well, it can be proved inductively, using Pascal s triangle that binomials are integral valued. No need of combinatorics there. You can also prove Pascal triangle analytically if you care...
I see...I didn't know that....thanks..Patric...mathematics always has surprises....
Cassio, our disagreement is only in nuances.
Let me explain how I saw the matter when I wrote my contribution:
Patrick gave a hint to the proof. Tridib unterstood it, and also for me it was a strong aha experience. ( if I would talk to myself I would have said: congratulations Patrick, this is just the observation that brings light into the darkness. )
Then came your contribution pretending to present 'the proof'. As you probably agree it added nothing to Patrick's hint, but explictness with respect to that part of the hint that you understood. Patrick's hint, however, has an implicit part that you did not understand and the internal necessity of which you obviously don't see, despite Tridip's and mine attempts to explain them. Here is my last attempt: When Patrick referred to 'a binomial coefficient' he referred not only to a formula that goes under this name but, also the context (expanding binomials, leading to Pascal's triangle, ...) from which it is clear that the quantity is integer-valued. The really interesting point is that (as I already wrote) this context leads us painlessly to an insight that by 'direct attack' (e.g. by analyzing the prime factors above and below the fraction bar) would not easily be obtained.
If the original question would be a mathematical research topic any proof would be acceptable that derives the desired result from established mathematical facts. Then the integer-valuedness of the formula for binomial coefficients could, of course, be taken as an established fact (with proper citation) and you could indeed claim to have given a valid proof. So, you see, its a matter of the point of view.
I hope you now understand both views and agree that the first one is more interesting.
Oh, now I understand, Mr. Mutze. Now it's clear for me. Thank you your explanations!
The question would then be: How many formerly-proven statements are we allowed to assume in the design of this proof?
Fabricio, it's certainly not a question of numbers. It's a question of understanding. Reading a proof should make us understand why the statement under consideration is true. Convincing us t h a t the statement is true, by referring to other deep facts that are known to be true for reasons that we don't understand, may be legitimate if very difficult problems are under investigation. For basics (as we discuss here), one should make the whole chain of arguments understandable.
Yes, Roberto..this is what I mean by proving it, without invoking heavy duty mathematical theorems, for example group theory etc.
Roberto, we have to divide by k! (k factorial) and not just k. Yes, first step would be what you have described above. Then we are left with a dilemma. k can divide any of the k consecutive numbers in the numerator....and you see the problem...
I think that indirectly you are trying to prove that for positive integers, binomial coefficients are integers. The problem can be represented as:
z=(n+k)! / (n! k!)
because the product of "k" consecutive positive integers can be represent as:
y = (n+k)! / n! = [(n+k) * (n+k-1)...(n-1) * (n!) ] / (n!) = (n+k) * (n+k-1)...(n-1)
where y is the product of k consecutive positive integers.
Defining n = p - k (where p is an integer),
z=(n+k)! / (n! k!) = p! / [k! * (p- k)! ]
which is the factorial formula of binomial coefficents.
Perhaps the following link can be helpful:
http://mathblag.wordpress.com/2011/11/17/generalized-binomial-coefficients/
EDIT: Sorry, I did not see the other answers. I just notice that Patrick Sole said something similar.
Federico,
you did not get to the 'problem' which most of the discussion was about.
Also your argument is of the form: The expression under consideration is a binomial coefficient. The binomial coefficients are known to be integer valued. Therefore, the expression under consideration is integer valued. Do you now understand why binomial coefficients are integer valued?
As I said at the end of the post, I did not see all the discussion.
First of all, my intention was not to present a proof. I just tried to show that the problem can be redifined (just as Patrick Sole noticed). Second, I never afirm that binomial coefficients are integer, I just mention that the problem that we are discussing is analogue to that one. Finally, I include a link where there is an attempt to formally prove that binomial coefficent are integers, that can be helpful.
I´m sorry again, I didn't see the previous posts. I will be more careful next time.
Thanks Ulrich for the comment.
This problem is as simple to define as it is complicated to solve and fascinating to think about, and I believe Roberto was in the right track.
If we apply arguments from modular arithmetic, we can show that among k consecutive naturals, there is necessarily one number divisible by each member of {1,...,k}, we might get an interesting conclusion from that. I can't quite think of a full picture, though.
@Fabricio
among the conseqution 5,4,3 of 3 natural numbers, show me that one which is divisible by 2 and by 3. It does not exist! Nevertheless 5*4*3 is clearly divisible by 1*2*3.
@all
since some contributors seem to think that we are dealing with a complicated problem, I'll write it down explicitely:
For arbitrary n>0 we consider the function
f(x) := (1+ x)^n =(1+x)*(1+x)*....(1+x) (n factors)
Expanding the n-fold product obviously results in a polynomial of order n with integer-valued coefficients. To be fully explicit let us introduce a notation for these coefficients:
f(x) = c_n_0*x^0 +c_n_1*x^1+c_n_2*x^2+ ... + c_n_n*x^n
On the other hand we have for polynomials (actually for a larger class of functions) the Taylor expansion arround x=0:
f(x) = f(0) +( f'(0)/1!)*x + (f''(0)/2!)*x^2 + ... + ( f^(n)(0)/n!)*x^n.
From the definition of f we get
f(0) = 1
f'(0) = (n*(1+x)^(n-1) for x=0) =n
f"(0)=n*(n-1)*(1+x)^(n-2) for x=0) = n*(n-1)
...
so that the coefficient of x^p in the Taylor expansion of f is
n*(n-1)*...*(n-(p-1))/p!
Since the expansion of polynomials p(x) in powers of x is unique, the integer valued coefficient
c_n_p
equals the Taylor coefficient
n*(n-1)*...*(n-(p-1))/p!
The latter is therefore also integer valued although seeing this directly by identifying the terms in denominator and nominator that cancel out is far from obvious.
This presentation follows that in
Wilhelm Maak: Differential- und Integralrechnung, Vandenhoek&Rupprecht, Goettingen 1960.
This was the first textbook in mathematics that I acquired when I started studying Physics in 1962. My Professor, Erhard Heinz, claimed it to be the only reasonable beginners textbook available. Since his favorits for further studies were Ince and Whittaker/Watson he did not restrict this claim to books written in German.
This textbook (which I consider a piece of art) manages it to come to our problem
on p. 91 (of total 370) in a chapter on interpolation, as an application of Newton's interpolation formula for polynomials. Taylor expansions of non-polynomials then are treated in the next chapter and thus are not needed for our problem.
@Ulrich Both integrality and explicit expression can be derived by double induction from Pascal s recursion
(n,k)=(n-1,k-1)+(n-1,k-2)
I think you missed my point, what I said is that for each member of {1,...,k}, there is at least one member of the k consecutive integers that is divisible by it.
As pointed out by Patrick, and others, this problem can be solved in many ways. However, there might be an elementary argument to prove it (as opposed to what I wrote previously).
\begin{Observation}
First, note (and as pointed out by Roberto) that k must divide exactly one of the numbers in the numerators.
Suppose, the numbers in the numerator are: r, r+1,....,(r+k-1). Suppose k divide (r+m), where m is one of {0,1,...,k-1}. If k has a prime factorization given by (p_1^\d_1)...(p_t^d_t), then (r+m) must have this product hidden in it's own prime factorization.
Again, notice that any one of the numbers {2,.....,k-1} in the denominator can divide at least one of the numbers in the numerator. NOTE, I AM NOT SAYING THAT THIS IS DONE IN TURN, ONE AFTER THE OTHER, NO.
Each in the denominator, as a single number, can divide at least one of the numbers in the numerator.
\end{Observation}
Say: the denominator has prime factorization: (p_1^c_1)(p_2^c_2)....(p_j^c_j).
Then, from the above observation, we see that the prime factorization of the numerator must have (p_1^s_1)(p_2^s_2)....(p_j^s_j)* (some more prime factors), and that
each s_i >= c_i, for each i = 1....j.
Hence the result follows.
If you are interested, play with few numerical values, and see if my argument holds. If not, I guess it can be improved to make it a proper argument. But this may be one of the elementary ways to solve the problem.
Dear Fabricio, it is OK when you explain what you wanted to say, but it is not OK to tell us that you did'nt say what you said.
From 2 consecutive positive integers one number is divisible by 2.
From 3 consecutive positive integers one number is divisible by 3, and one by 2.
From 4 consecut. posit. integers one number is divisible by 4, one by 3, one by 2.
From 9 cons. pos. int. one nr is div. by 9, one by 8, one by 7,..., one by 2.
From k cons. pos. int. one nr is divis. by k, one by (k-1), one by (k-2),..., one by 2.
Hugo,
you got it! This is the mechanism. Of course, the numbers selected as divisible need not always be new ones. For instance, for the consecutive numbers 11 12 13 14
the member 12 is divisible by 4 and 3. Finally 14 is divisible by 2. 11 and 13, as primes, go unused.
As I see it, this completes the reasoning started by Roberto. Thanks for the aha experience.
Hugo (and Ulrich), i am sorry, I don't get your point...from 4 consecutive positive integers, one number is divisible by 4 (ok...that's right), one by 3 and one by 2...i don't get that point. how about 13*12*11*10; 4 divides 12. ok. but 3 doesn't divide any of the remaining.....sorry...(of course 12 is divisible both by 4 and 3), but that's not what you are saying....i tried this approach even before Roberto mentioned it.. you cannot just simply use induction like that...unless I am missing something....I still think an elementary proof consists of a decomposition into prime factors, as I pointed out above.
@Ulrich, I doubt you can generalize your argument for any k. So it is not an aha moment yet. Sorry!
Sorry, I expressed myself very poorly. I was extremely sleep deprived.
Well, yeah, apparently induction is the way to go. Modular arithmetic seems to be superfluous for the problem as well.
Roberto, I guess what Hugo described above seems like that. So I asked the same question. Now, for numerical values, as small as the given example, it is easily seen to be the case. So I do not claim that 3 has to divide one of the remaining number ( if you see my sketch of the proof above, you will see what I mean ). I am confused regarding Hugo's sketch of the proof.
But Hugo's induction steps also doesn't make sense. This is why: once k divides exactly one of the numbers in the numerator, say r + m, then what is the guarantee that k-1 will divide at least one of the numbers ? Now with the example, we see that it happens to be 12. But in general, how do you know ?
We can be sure about k-1 dividing one of the numbers if we have k-1 consecutive positive integers. In the present case that means if k divides either the beginning number of the sequence in the numerator, or the end number, then you can say for sure that k-1 will divide any of the remaining numbers, as claimed by Hugo. But if that number happen to be in the middle of the sequence, then, we don't have a sequence of k-1 consecutive positive integers, and then we cannot claim that k-1 will divide any of the numbers for sure. Roberto does it make sense ? Do you see my problem with the induction ?
Have you seen my sketch of the proof by way of prime decomposition ? I think that approach is much better and more full proof. I am not saying that Induction won't work. It may work. But it is going to be very messy argument. Hugo's approach to induction, I am affraid, won't work, unless you clarifies my question.
I fully agree with Tridib's two last contributions.
I admit that I erroneously considered Hugo's argument as conclusive for our problem.
So far we only know:
The product of k consecutive positive integers is divisible by n for each positive integer n
Fun problem. Surely the binomial coefficient based solution is the simplest, but here's a fun visualization similar to Hugo's idea. Not very rigorous as a proof but I felt the idea was worth sharing. For p = 3, consider the following (infinite) list of infinite sequences
s_1 = 001001001001001001001001001001...
s_2 = 000000001000000001000000001000...
s_3 = 000000000000000000000000001000...
s_4 = 000000000000000000000000000000...
s_5 = ...
Where (s_i)_j = 1 p^i | j. For each interval [a, b], the maximal m such that p^m divides a*(a+1)*...(b-1)*b is the sum of all 1's seen in the "columns" from a to b, that is, the sum of (s_i)_j for i \in \N, j \in [a, b]. Now, observe that all the s_i are periodic and _are_lexicographically_minimal_among_their_rotation_classes_, so that the first k columns contain the _least_possible_number_ of 1's among all contiguous sequences of columns of this length. Thus, if p^m | product([1, k]), we have p^m | product([a+1, a+k]) for all a. Now, repeat this argument for all primes p
Roberto, that's right. You see that in terms of prime factorization, the problem is more manageable, ie, you can really generalize many of the arguments you make while experimenting with numerical numbers.
Dear Tridib
Hi,
the K multiple consecutive integers should divide k!,
Here is a sketch of the proof :
It is enough to prove that the multiple of K consecutive integers should divide K
and consequently k! obviously K consecutive integers includes (k-1) ,(k-2),
....(2), consecutive integers ,i.e,
If M = (N+1)(N+2).....(N+k) is divisible b 2 , 3 , ...., k-1 and k and hence
M is divisible by k! .
Now to prove our claim:Let M = (N+1)(N+2).....(N+K)
we have 2 cases :if k >=N , then K is one of the factors (N+1)(N+2).....(N+K)
because N
@Issam: You reproduce an error which many of the contributors to this thread (including me) also made. If n is divisible by i and by j it need not to be divisible by
the produkt i j. If one writes (as my books do) a|b for 'a divides b' then the general rule is
a|b and c|d implies a*c | b*d
hence
a|b and c|b implies a*c | b*b but not (in general) a*c | b.
In 9 consecutive positive integers is one N | 9, one .N | 6 and one N | 3 .. (4 factors '3')
In 9 consecutive positive integers is one N | 8, one .N | 4 and two N | 2 ...(7 factors '2')
In 9 consecutive positive integers is one N | 5, and one .N | 7
9!=3×3×2×2×2×7×2×3×5×2×2×3×2×1= 2×2×2×2×2×2×2× 3×3×3×3× 5× 7 =
= 2**7 × 3**4 × 5 × 7.
So,: the product of 9 consecutive positive integers is divisible by 9! ?
("is one" = "is at least one")
-------
Why somebody see the problem in : (8×7×6) / (3×2×1) =8×7
My question is:
Can somebody find product of k consecutive positive integers not divisible by k! .....?
(With a little computer program).
@Issam. Thanks for your comments.
I am not sure how (a+1)k is a factor of M. Anyhow, proving that the product of any consecutive 'k' integers by k is not a problem. But there is no guarantee that after you divide by k, you can confidently say that what is left is divisible by (k-1). And also note what Ulrich has mentioned above.
@Hugo, you can't write such a program :). And, yes, you gotta break things down to prime factors. Once you do that, argument becomes easier, as I have sketched in one of my entries above.
Oh Hugo: If you would have scanned the discussion so far you would have noticed hat it contains a valid proof for "Any product of k consecutive positive integers is divisible by k!". So nobody has the chance to find a counter example, with or without a computer program. What some people tried to achieve in addition (I thought you would be among them) is to find a direct proof, i.e. one based on divisibility arguments and not taking the detour over Pascal's triangle or something equivalent. So far, nobody (in this thread) was successful with such an attempt. Explicit positive examples can't help (we k n o w that they all work !!!!!!).
Dear All
Here is the concrete proof of the argument :
The k consecutive integers are (N+K) (N+K-1)...(N+2) (N+1)
= (N+K) (N+K-1)...(N+2) (N+1)N!/N! = (N+K)!/N! = K!(N+K)!/N!K! = K! .C
where C = (N+K)!/N!K! is an integer , the well known binomial coeifficient.
This proves that K! divides the k consecutive integers .
best
@Issam: Patrick stated this in his (the) first contribution to this thread.
@Ulrich:
So what , this elementary proof is available in many NT papers .
It is enough to reach the end . Of course , don't agree with the satement :
[So far, nobody (in this thread) was successful with such an attempt.]
regards
@Issam: "this elementary proof" What elementary proof?
"available in many NT papers" An example?
"don't agree with ..." reasons ?
I would like to mention an easy generalization of what we (i.e. those who followed the thread) know about our problem:
We know: Given non-negative integers n, k1, k2 such that k1+k2 = n, the term n!/(k1!*k2!) is integer.
Generalization:
Given non-negative integers n,k1,...kp such that k1+...+kp = n, the term
n!/(k1!*...*kp!) is integer.
Reason: In essentially the same way as the terms n!/(k1!*k2!) are related to the
expansion of (a1+a2)^n (binomial theorem)
the terms n!/(k1!*...*kp!) are related to the expansion of (a1+....+ap)^n (multinomial theorem, perfectly covered by Wikipedia).
An alternative, nice (as I see it), argument for the 'integervaluedness' of n!/(k1!*...*kp!) is by basic group theory:
Consider any set with just n elements. Partition it in subsets of just k1, ... kp elements. The bijections of the whole set form a group of n! elements. In this group the bijections which leave invariant the p subsets from our partition form a subgroup. This subgroup obviously has k1!*...*kp! elements. The number of elements of a subgroup, however, always divides the order of the whole group.
Ulrich: Did you look at my comment? I think it's one way to prove this without a "Pascal detour". If it's hard to believe in its current form, I can try to fill in the details later this week.
@Ville: Please understand that I read only finished proposals and no attempts where 'details have to be filled in'. But I'll be glad to read your proof if you have given it such a form that you are convinced that it proves what it is expected to prove.
Ulrich: Fair enough, I didn't exactly bother reading the whole discussion myself.
Ulrich & whoever cares: I have a clearer version of my argument in http://villesalo.com/ACStaSP.pdf. If you feel I omitted something or something does not make sense, I'm open for suggestions (also I'm not sure that's the best possible title).
@Ville, it's quite an extensive effort :). Thanks.
Title seems appropriate. However, I left the question here, it wasn't my conjecture. I just wanted to know if this can be solved from first principal, without using binomial theorem or other big theorems (meaning only from divisibility argument ).
@Ville: Your argument is flawed yet on a syntactical level: In the first equation in the proof to Lemma 3 you work with the set { m : p^m | j } which obviously depends on j as a parameter. When you write a max in front of it, the maximum is formed over m at fixed j. So you don't define an m but an m_j from the very beginning. Obviously it depends on j in a non-trivial manner.
Nevertheless you understand your first equation as 'for all j ...' and introduce an m_j later and relate it to your (as I argued non-existing) m.
There could be a way for me to find out what you had in mind, and my feeling is that the idea in the background may be sound. However, my view is that it is your task to show that this is actually the case.
Well { m : p^m | j } does not define the variable m (in fact when m is the left side of set-builder notation, it is always a free variable, and could be changed to any other free variable). You may have become confused because I use m many times for different things (although I do always state this clearly). I have now changed the other uses of m to be m' and m''. It's less ambiguous, but not as pretty.
Well, there is a proof which is elementary. I will post it later today once I get a chance.
Tridib: I interpret your argument as splitting [1, k] into segments {i*p+1, i*p+2, ..., (i+1)*p} all of which contain a single factor p when you take their product. However, what do you do with numbers like p^2?
"If k is a multiple of p, then there will be exactly m such sets, each containing a multiple of p." More concretely, this is where I get lost. You seem to be saying that if m is maximal such that p^m|k! (this was assumed earlier), and k=np for some n (k is a multiple of p), then k=mp (because you split [1,k] into segments of length p and you got m of them). This is of course not true, did I misunderstand something or did you confuse some of k, k!, p^m and mp here?
But, in any case it seems to me that you sidestep the main issue, my whole articlet was about handling the p^i factors for various i, and you seem to somehow do without even mentioning them, so you understand I'm a bit skeptical :P
Oh, and just FYI, my proof is elementary too, in every sense of the word :) I do introduce some objects besides numbers (sequences), but believe it or not, I did this to make the argument easier to read (but perhaps only if you're used to such objects).
@Ville:You are completely right with your defense. Your gentle addition of primes should not be necessary assuming an informed reader. Sorry for my erroneous remark. I have to admit that the proof of Lemma 3 is too cryptic for me, so that I gave up before I was convinced. ( especially understanding the logical structure of the phrase involving and the phrase "By the prime number therorem...".
Consider k = 11.
{1,2,3,4,5,6,7,8,9,10,11} is the sequence. Consider the prime 3. Then you can split this sequence into 4 sub-sequence: {1,2,3},{4,5,6},{7,8,9},{10,11} . So 3 has 3 multiples in it, one from each sub- sequence, except the last one.
Similarly, if you consider the prime 5, then you can split up the sequence into three sub-sequences, [1..5],[6....10],[11], each containing a multiple of 5, except the last one, and similarly for 7, 11 and 2.
So p= 3, m = 3 , p= 5, m= 2, etc. Is it clear now ? There is no issue with p^2 or any power of p. Also, when I assumed m to be maximal, I did it , keeping in mind the prime factorization of k! . The result, namely p^m | k! => p^m | ( the product of k consecutive positive integers) holds for any m.
Consider k = 9, and again consider p= 3. Then 3^3 |9! And m=3 is maximum. What I am saying is p^m | k!, where m is maximum, then p must appear in the sequence {1,...k} exactly m number of times and no more. Since p
@Ville, I am not putting forward my argument to replace yours. There is no question of sidestepping anything in your argument. My argument is completely different from yours.
Actually, the product of k consecutive integers (can have some negative factors) is divisible by k!
Let (n+1)(n+2)...(n+k)=m be the product of k arbitrary integers. If there is a zero factor, then m is divisible by k! If there is no zero factor, then all factors are negative or all of them are positive.
Without loss of generality, we may assume that all factors are positive Clearly, m=(n+k)!/n!,Now, m!/k!=(n+k)!/[n!k!], which is the binomial coefficient (n+k) choose k. An ordinary binomial coefficient is always an integer. Therefore m is divisible by k!
@Severino, looking back in this discussion you will find that your insight was communicated several times. The discussion developed than in another direction in which you perhaps are interested too.
if we take k=2 then two consucutive integer must divisble be 2 ( at leat one of them is even integer) if k=3 then three consucutive integer must have one is multiple of three and one is multiple of two so it will divisibel by 6=3| similarily it will divisible by factorial 4,5,, and so on.
if we take k=2 then two consucutive integer must divisble be 2 ( at leat one of them is even integer) if k=3 then three consucutive integer must have one is multiple of three and one is multiple of two so it will divisibel by 6=3| similarily it will divisible by factorial 4,5,, and so on.
@Jitendra: try to make this a mathematical argument and you will see that is is not easy! Common sense arguments like your's are nevertheless suitable as first steps.
yes
it uses a couple of lemmas from elementary number theory
first one is
floor((a+b)/c) >= floor(a/c) + floor(b/c)
for positive integers a, b, c
(in fact, the difference is at most 1,
which is easy to prove from the definition of the floor function)
second one is that the power of a prime p in n factorial is
sum(m >= 0) floor(n / p^m)
(which is a finite sum)
then the original problem follows,
since the power of a prime p in the product of k consecutive integers
(we take those integers to be from n+1 up through n+k,
so the product is (n+k) factorial / n factorial)
is
sum(m >= 0) floor((n+k)/p^m) - sum(m >= 0) floor(n/p^m),
which is always more than
(using the first lemma)
sum(m >= 0) floor(k/p^m),
the power of p in k factorial
since for every prime p, the power of p in k factorial is never more than the power of p in the product,
k factorial always divides the product
Ah, i apologize - the people who answered about binomial coefficients were correct also; i did not see those posts before i answered (it was my first day in town) - but i thought a simple proof would be of interest
Christopher: I think the gist of my 4 page pdf from earlier is what you wrote, at least on a first glance. The difference is that instead of stating "the number of p-factors in n is sum(m >= 0) floor(n / p^m)", I state a complicated fact about certain binary sequences, which I think amounts to the same thing... Perhaps I should change the name "A complicated solution to a simple problem" to "A complicated explanation of a simple solution to a simple problem".
Thanks for clearing this up, perhaps number theory is not my thing :P
Ok, ville, sorry about that - i just found the pdf (i'm still new here and did not think to look for one earlier) - your proof seems to be correct, and provides a way to prove the second lemma that i just stated without proof (there are, of course, other proofs in various number theory books)
Yes it is true and can be proved by logic.If you take the the consecutive numbers as n,n+1,n+2.......n+k-1 then the result will be [k! (C(n+k-1,n-1))]
n(n+1)........(n+k-1)=
{(n+k-1)(n+k-2).....n.(n-1)(n-2)......1}/{(n-1)(n-2)......1}=(n+k-1)! /(n-1)!=(n+k-1)!k! /(n-1)!k!=k!{C(n+k-1,n-1}which is the multiple of k!
@Sujata, looking back in this discussion you will find that your insight was communicated several times. The discussion developed than in another direction in which you perhaps are interested too.
It is true, the result of such a division is the binomial coefficient (n,k) where $n$ is the largest element of those $k$ consecutive integer numbers. And as Vemula mentioned, it can be prooved by induction.
Every k'th positive integer is divisible by k. Which means: there are k-1 positive integers not divisible by k, then one which is divisible by k, then k-1 not divisible by k, then one which is divisible by k, ... and so on. Any sequence of k positive adjacent integers therefore has to include one of the integers divisible by k. I think we do not need any induction or computation to be convinced of this.
Richard,
how precisely you bring together all the factors that make up k factorial (or did you read ! in k! as interpunctation?)
- Badges
- Science topic
- Similar topics
- Mathematics