nCk is a natural number


by jackbauer
Tags: natural, number
jackbauer
jackbauer is offline
#1
Oct29-05, 04:23 PM
P: 10
I have to prove that for 0<=k<=n that nCk(n choose k) is a natural number. I try by induction but i end up with n-m/m+1 must be a natural number which i don't know how to prove, is there another way besides induction? Could someone help me out? Thanks, Jack
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Muzza
Muzza is offline
#2
Oct29-05, 04:31 PM
P: 696
nCk is the number of subsets of cardinality k of, say, {1, 2, ..., n}, which is clearly a natural number (and if this is not your definition of nCk, prove that "your" definition is equivalent to "my" formulation).
Tide
Tide is offline
#3
Oct29-05, 04:50 PM
Sci Advisor
HW Helper
P: 3,149
A third approach is to observe that in

[tex]\binom {n}{r} = \frac {n \times (n-1) \times \cdot \cdot \cdot \times (n-r+1)}{r \times (r-1) \cdot \cdot \cdot \times 1}[/tex]

the numerator is a product of r successive integers. Therefore, at least one factor is divisible by r, r -1, r - 2 etc. so the ratio is a natural number.

matt grime
matt grime is offline
#4
Oct30-05, 05:07 AM
Sci Advisor
HW Helper
P: 9,398

nCk is a natural number


You know that there is an easy way to write nCk as the sum of two "smaller" combinations, right? Cos then it is inductively a trivial proof.
Tide
Tide is offline
#5
Oct30-05, 06:15 AM
Sci Advisor
HW Helper
P: 3,149
Quote Quote by matt grime
You know that there is an easy way to write nCk as the sum of two "smaller" combinations, right? Cos then it is inductively a trivial proof.
It looks like we've pinned down all the permutations of proofs for this one! ;)
jackbauer
jackbauer is offline
#6
Oct30-05, 11:20 AM
P: 10
Thanks for all the suggestions guys, could i just ask what is the simpler way of expressing nCr matt? Thanks
Moo Of Doom
Moo Of Doom is offline
#7
Oct30-05, 03:24 PM
P: 367
[tex]\binom {n}{r} = \binom {n-1}{r-1}+\binom{n-1}{r}[/tex]
So long as [tex]1 \leq r \leq n-1[/tex]. For the cases where this doesn't hold, it's trivial to prove nCr is in N.
ComputerGeek
ComputerGeek is offline
#8
Oct31-05, 07:45 AM
P: 534
Quote Quote by Tide
A third approach is to observe that in
[tex]\binom {n}{r} = \frac {n \times (n-1) \times \cdot \cdot \cdot \times (n-r+1)}{r \times (r-1) \cdot \cdot \cdot \times 1}[/tex]
the numerator is a product of r successive integers. Therefore, at least one factor is divisible by r, r -1, r - 2 etc. so the ratio is a natural number.
I thought that
[tex]\binom{n}{r} = \frac{n!}{r!(n-r)!}[/tex]
shmoe
shmoe is offline
#9
Oct31-05, 08:08 AM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by ComputerGeek
I thought that
[tex]\binom{n}{r} = \frac{n!}{r!(n-r)!}[/tex]
This is the same. Tide has just cancelled the common factors of n! and (n-r)!.

jackbauer- you should compare the [itex]\binom {n}{r} = \binom {n-1}{r-1}+\binom{n-1}{r}[/itex] expression with Pascal's triangle if you're familiar with it.
soulflyfgm
soulflyfgm is offline
#10
Nov18-05, 02:31 PM
P: 28
How would u prove it using induction? any ideas? hints? thx u
shmoe
shmoe is offline
#11
Nov18-05, 02:42 PM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by soulflyfgm
How would u prove it using induction? any ideas? hints? thx u
See the identity in Moo Of Doom's post.
soulflyfgm
soulflyfgm is offline
#12
Nov18-05, 03:47 PM
P: 28
Quote Quote by shmoe
See the identity in Moo Of Doom's post.
ok...then what would I take as my induction hypothesis?....plz help..i will apriciate if some one could help me start this proof by induction staring the first steps.. thank you so much
shmoe
shmoe is offline
#13
Nov18-05, 04:32 PM
Sci Advisor
HW Helper
P: 1,996
Do induction on n. Read the thread in the probability section for more ideas.
soulflyfgm
soulflyfgm is offline
#14
Nov18-05, 05:35 PM
P: 28
i am trying to prove that it would be a natural number. am i right in this prove?

nCr is n element of N for every o<= r<= n.
Suppose that a given r, all the nCr are nutural numbers
then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.

can some one tell me if this prove is correct or can some one help me make it better?
thank you so much
fourier jr
fourier jr is offline
#15
Nov18-05, 06:45 PM
P: 943
i recently saw an extremely slick proof of this, but i can't remember where. i think it was a book in the school library. anyway now i'm tortured. the proof said multiply the numerator & denominator by the same thing, then you get [some expression]. end of proof.
soulflyfgm
soulflyfgm is offline
#16
Nov18-05, 07:53 PM
P: 28
the problem is that i have to proove this by induction....can some one plz review wat i post before and tell me if that prove is right ...thx so much
robert Ihnot
robert Ihnot is offline
#17
Nov19-05, 12:04 AM
PF Gold
P: 1,059
This problem has come up in this forum over and over again, but I can not now find any references. It is not, as a general rule, easy to prove it by induction. Other methods are better. But using the form as shown by soulflyfgm it can be done. This is similar to using pascal's triangle as a way of obtaining the terms.
shmoe
shmoe is offline
#18
Nov19-05, 08:50 AM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by Tide
A third approach is to observe that in
[tex]\binom {n}{r} = \frac {n \times (n-1) \times \cdot \cdot \cdot \times (n-r+1)}{r \times (r-1) \cdot \cdot \cdot \times 1}[/tex]
the numerator is a product of r successive integers. Therefore, at least one factor is divisible by r, r -1, r - 2 etc. so the ratio is a natural number.
Unfortunately you can't pair them up easily to cancel terms as you may have terms in the numerator pulling "double duty" and being the only term in the numerator divisble by multiple terms in the denominator. Consider 7C3=(7*6*5)/(1*2*3), the 2 and the 3 both go to the 6.

Do you have an easy way to fix this? You could consider primes one at a time. You can count the number of times a prime p appears in a sequence of r numbers. if [] is the greatest integer function, 1*2*3*...*r will be divisible by p to the power [r/p]+[r/p^2]+[r/p^3]+... and no higher power. Any sequence of r integers, no matter where you start, will be divisible by p to this power (possible higher). More generally any sequence of m integers will have at least [m/k] multiples of k in it. So you end up with an integer.



soulflyfgm:{n+1}Cr = nCr + nC{r-1} doesn't hold for all values of r.


Register to reply

Related Discussions
Natural number Precalculus Mathematics Homework 35
Natural Log of negative number Calculus 3
Is it true for all n, Natural number? Linear & Abstract Algebra 10
natural number Engineering, Comp Sci, & Technology Homework 2
Help solving log (natural number) equation Precalculus Mathematics Homework 3