divisibility problem
MoeBlee
have that the cardinality of the set of subsets of cardinality r of a
set of cardinality n is n!/(r!(n-r!)). So r!(n-r)! divides n!, since
the cardinality of the set of subsets of cardinality r of a set of
cardinality n is a natural number greater than zero.
But I'm stumped trying to prove, without appeal to sets and
cardinality but rather by just arithmetic and induction on natural
numbers, that r!(n-r)! divides n!. I've tried induction on r,
induction on n, and induction on n-r, but I can only get the easy base
step.
Any suggestions? Thanks.
MoeBlee
Ray Vickson
You want to prove that C(n,k) = n!/[k!*(n-k)!] is an integer. You can
prove by induction that C(n,k) = C(n-1,k)+C(n-1,k-1) (Pascal's
triangle) and you have known values of C(n,0), C(n,1), etc. So, if C
(n-1,j) is an integer for all integer j, 0 <= j <= n-1, then C(n,k) is
an integer for k <= n-1. Of course, C(n,n) = 1, so the result holds as
well for k = n.
R.G. Vickson
R.G. Vickson
Dave L. Renfro
Off the top of my head . . .
Let s = n-r, so that r + s = n. Then you're looking
at n!/(r!s!). Assume without loss of generality that
r >= s. Then after cancelling s! so as to leave r many
consecutive integer factors on top and r! on the bottom,
we need to show that r! is a factor of the product of
those remaining factors in the numerator. Writing
r! = (2)(3)(4)...(r), it is clear that each of these
factors is also a factor of the numerator, since every
other factor in the numerator is even, every third
factor in the numerator is divisible by 3, every fourth
factor in the numerator is divisible by 4, etc. Of course,
we need more than this, because, for instance, we don't
want to remove a factor of 4 (which we might need when
it's time to cancel 4's) when we're picking an even
factor in the numerator to cancel with 2, and we don't
want to use a number divisible by 6 (if we can help it)
either, because we might need it when we get to picking
a factor in the numerator that is divisible by 6, etc.
I don't know if this leads to anything useful, but I
only had a couple of minutes "free" right now . . .
Dave L. Renfro
quasi
Using The Binomial Theorem (which can be proved by induction), the
coefficient of x^r in the expansion of (x+1)^n is (n!)/(r!*(n-r)!).
But the coefficients of (x+1)^n are obviously positive integers.
quasi
David C. Ullrich
<jazz...@hotmail.com> wrote:
You could do what Vickson said: Show that C(n,k) = C(n-1,k)+C(n-1,k-1)
(by induction or just by adding fractions). Now the fact that C(n,k)
is an integer follows by induction on n + k. That's a purely algebraic
proof, possibly not as direct as you wanted.
I doubt that you're going to be able to show this directly by
finding all the factors of the denominator somehow lurking
in the numerator. If I'm wrong about that that would be
interesting. But assuming this is not just homework, maybe
you should take the point of view that the fact that you
_can_ prove it by thinking about sets and subsets is a
_good_ thing! It happens that people prove algebraic
things by "combinatorial" arguments - after it happens
three times it's a technique instead of a trick, and a
useful one.
Say I asked you to find a closed form for
C(n,0) + C(n,1) + ... + C(n,n).
You look at factorials, look at a few small n,
guess what the answer is and prove it by induction.
Or you think about the fact that C(n,k) is the number
of subsets of blah blah, and the answer's obvious.
That's two.
>Any suggestions? Thanks.
>
>MoeBlee
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
MoeBlee
> You could do what Vickson said: Show that C(n,k) = C(n-1,k)+C(n-1,k-1)
I have that okay.
> Now the fact that C(n,k)
> is an integer follows by induction on n + k.
Would you show me more overtly how you set up that induction?
The base case, where n+k=0, is okay. But how do you set up the
hypothesis and induction step? (I tried some stuff but it didn't seem
to work out.)
MoeBlee
no comment
Hello,
Here is a suggestion, perhaps rather complicated looking, but it will
add a tool to your arsenal.
We need a lemma that I will sketch the proof of later.
Lemma: Let p be a prime, and let w be a positive integer. Then the
largest d such that p^d divides w! is given by
d = {w/p} + [w/p^2] + [w/p^3} + .....,
where [x] is the greatest integer which is less than or equal to x.
Now we show that if a + b = n, then a!b! divides n!.
By the lemma, for any prime p, the largest p^d that divides a!b! is
([a/p] +[a/p^2] + ... + ([b/p] + [b/p^2] + ....)
But it is easy to show that for any m>1, {a/m] + [b/m} <= {(a+b)/m] =
[n/m]. This finishes things, for it shows that for any prime p, the
highest power of p that divides a!b! is less than or equal to the
highest power of p that divides n!.
Now I will sketch a proof of the Lemma. For clarity, I will use p = 3
and n = 100, but the argument is general.
We want the largest d such that 3^d divides 100!. Imagine that every
positive integer less than or equal to 100 has to pay a tax equal to
the number of 3's "in it". So 2 owes 0 dollars in tax, 3, 6, 12, 15,
21, and so on each owe 1 dollar, 9 and 18 and 36 owe 2 dollars, 27 for
example owes 3 dollars, so does 54. And finally 81 owes 4 dollars.
The tax collector collects the tax in a strange way. First she gets
$1 from everybody who owes a dollar. So she gets $1 from each
multiple of 3 less than 100. Altogether she collects [100/3]
dollars. But of course 9, 18, 27, .. still owe money. Now she
collects $1 from everyone who still owes money. So she collects $1
from each multiple of 9, and therefore collects a total of [100/9}
dollars. But 27, 54, 81 still owe money. She collects $1 from each,
for a total of [100/27]. Now everybody but 81 has paid what he owed.
Finally the tax collector collects 1 dollar from the [100/81] people
who still owe money, and the game is over. The tax collector has
collected [100/3] + [100/9] + [100/27] + [100/81} + [100/243} + ....
(Of course the [100/243] is a joke, this number and all subsequent
numbers are 0, the sum that looked iinfinite is quite finite.)
One could repeat the above argument with essentially no change with
any prime p instead of 3, and any positive integer n instead of 100.
PiperAlpha167
You could appeal to the inductive clause of the recursive definition, i.e.,
C(n,k) = C(n-1,k-1) + C(n-1,k)
Then by some direct substitutions:
C(n,k) =
n!/(n-k)!k! =
n(n-1)!/(n-k)!k! =
(n-1)!(k+(n-k))/(n-k)!k! =
(n-1)!k/(n-k)!k! + (n-1)!(n-k)/(n-k)!k! =
(n-1)!/(n-k)!(k-1)! + (n-1)!/(n-k-1)!k! =
C(n-1,k-1) + C(n-1,k)
David C. Ullrich
??? It must be late or something.
We're proving this: If n + k <= N then C(n,k) (defined
by those factorials) is an integer.
If n + k <= 0 we're set. Suppose we know that
if n + k <= N then C(n,k) is an integer.
Suppose that n + k <= N+1.
Then (n-1) + k <= N and (n-1) + (k-1) <= N.
So C(n-1,k) and C(n-1,k-1) are integers. Also
the sum of any two integers is an integer. Hence
C(n,k) is an integer.
(Maybe when I wrote "induction on n + k" you
read "induction on n and k" or something???
It's induction on n + k, where the + is a plus sign.)
Bill Dubuque
>
> I know how to prove that for natural numbers k and n, with k=<n, we
> have that the cardinality of the set of subsets of cardinality k of a
> set of cardinality n is n!/(k!(n-k!)). So k!(n-k)! divides n!, since
> the cardinality of the set of subsets of cardinality k of a set of
> cardinality n is a natural number greater than zero.
>
> But I'm stumped trying to prove, without appeal to sets and cardinality
> but rather by just arithmetic and induction on natural numbers, that
> induction on n-k, but I can only get the easy base step. Suggestions?
Below is an outline of a simple arithmetical inductive proof
that every binomial coefficient (n:k) is integral. I explicitly
devised it to be comprehensible to an elementary school student.
Apparently this proof is little-known, e.g. I've never seen it
in a textbook, newsgroup, etc. The general idea of the proof is
most easily comprehended by applying it to a specific example.
E.g. consider (39:17) = 39!/22!/17! = (23 24 ... 39)/(1 2 ... 17)
When reduced to lowest terms a/b, no prime p > 17 can divide b
else p|b|1 2...17 => p|2 or p|3 or ... p|17 contrary to p > 17.
So to show a/b an integer we need only show that no prime p <= 17
divides the reduced denom b. An example suffices to give the idea.
We'll show that 2 doesn't divide b. The highest power of 2 in the
denom terms is 16<17. Now align the numerator and denom terms mod 16
by shifting the 1st numerator term 23 so it's above its value mod 16,
viz. 23 = 7 (mod 16) so we shift the top left till 23 lies above 7
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
----------- -- -- -- -- -- -- -- -- -- -- -- -----------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2 doesn't divide the reduced denominator of each aligned fraction:
24/8 = 3, 26/10 = 13/5, 28/12 = 7/3, 30/14 = 15/7, 32/16 = 2.
This is true because these fractions c/d satisfy c = d (mod 16),
i.e. c = d + 16k so 2|d => 2|c, 4|d => 4|c, ..., 16|d => 16|c,
i.e. any power of 2 in d is also in c so it cancels on reduction.
Thus to prove 2 doesn't divide the reduced denominator of (39:17)
it suffices to prove the same for the "leftover" fraction composed
of the above non-aligned terms (34 35 ... 39)/(1 2 ... 6) = (39:6).
Being an (n:k) with smaller k = 6 < 17, this follows by induction.
Since the same proof works for any prime p, no prime divides the
reduced denominator of (39:17), therefore (38:17) is an integer. QED
--Bill Dubuque
PiperAlpha167
MoeBlee
> (Maybe when I wrote "induction on n + k" you
> read "induction on n and k" or something???
> It's induction on n + k, where the + is a plus sign.)
I didn't think it was an induction on n and an induction on k. I
thought it was an induction on N where N = n+k. But nevermind that
now. Since you've spelled it out, I see that it's an induction on N
where N >= n+k.
> If n + k <= 0 we're set. Suppose we know that
> if n + k <= N then C(n,k) is an integer.
> Suppose that n + k <= N+1.
>
> Then (n-1) + k <= N and (n-1) + (k-1) <= N.
> So C(n-1,k) and C(n-1,k-1) are integers. Also
> the sum of any two integers is an integer. Hence
> C(n,k) is an integer.
Got it.
(For the constraints of my own problem (it doesn't matter why I have
those constraints; but it's not a homework problem, btw), the only
thing I have to do now is put it all in the form of a divisibility
problem, without mentioning the notion of 'integer'. But hopefully
that should be routine for me to do on my own.)
(And I understand your other comments about the wisdom of set
combinatorial solutions; it's just that, for certain purposes, I
wanted to have this different kind of proof also.)
Thanks,
MoeBlee
P.S. Thanks also to Ray Vickson, Dave L. Renfro, quasi, no comment,
PiperAlpha167, and Bill Dubuque for your comments that were
instructive too.
David C. Ullrich
<jazz...@hotmail.com> wrote:
>On Mar 5, 3:36 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>
>> (Maybe when I wrote "induction on n + k" you
>> read "induction on n and k" or something???
>> It's induction on n + k, where the + is a plus sign.)
>
>I didn't think it was an induction on n and an induction on k. I
>thought it was an induction on N where N = n+k. But nevermind that
>now. Since you've spelled it out, I see that it's an induction on N
>where N >= n+k.
Or simply what's often called "strong induction" on n + k.
>> If n + k <= 0 we're set. Suppose we know that
>> if n + k <= N then C(n,k) is an integer.
>> Suppose that n + k <= N+1.
>>
>> Then (n-1) + k <= N and (n-1) + (k-1) <= N.
>> So C(n-1,k) and C(n-1,k-1) are integers. Also
>> the sum of any two integers is an integer. Hence
>> C(n,k) is an integer.
>
>Got it.
>
>(For the constraints of my own problem (it doesn't matter why I have
>those constraints; but it's not a homework problem, btw), the only
>thing I have to do now is put it all in the form of a divisibility
>problem, without mentioning the notion of 'integer'. But hopefully
>that should be routine for me to do on my own.)
>
>(And I understand your other comments about the wisdom of set
>combinatorial solutions; it's just that, for certain purposes, I
>wanted to have this different kind of proof also.)
>
>Thanks,
>
>MoeBlee
>
>P.S. Thanks also to Ray Vickson, Dave L. Renfro, quasi, no comment,
>PiperAlpha167, and Bill Dubuque for your comments that were
>instructive too.
David C. Ullrich
Bill Dubuque
>MoeBlee <jazz...@hotmail.com> wrote:
>>On Mar 4, 3:30 pm, David C. Ullrich <dullr...@sprynet.com> wrote:
>>
>>> Show that C(n,k) = C(n-1,k)+C(n-1,k-1)
>>
>>
>>Would you show me more overtly how you set up that induction?
>>
>>The base case, where n+k=0, is okay. But how do you set up the hypothesis
>>and induction step? (I tried some stuff but it didn't seem to work out.)
>
> is an integer.
>
> If n + k <= 0 we're set. Suppose we know that if n + k <= N then C(n,k)
> is an integer. Suppose that n + k <= N+1.
>
> Then (n-1) + k <= N and (n-1) + (k-1) <= N. So C(n-1,k) and C(n-1,k-1)
> are integers. Also the sum of any two integers is an integer. Hence
> C(n,k) is an integer.
SIMPLER Induct on n, not n+k, i.e. construct the Pascal triangle by rows,
concluding that all the triangle elts are integral multiples of c = C(1,1).
Each elt is the sum of its above neighbors (possibly 0) and, by induction,
all elts in above row are integral multiples of c, hence so to is the sum.
--Bill Dubuque