Can n choose k be proven as a natural number without using induction?

  • Thread starter jackbauer
  • Start date
  • Tags
    Natural
In summary, JacknCk 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).A third approach is to observe that in\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}the numerator is a product of r successive integers. Therefore
  • #1
jackbauer
10
0
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
 
Physics news on Phys.org
  • #2
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).
 
  • #3
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.
 
Last edited:
  • #4
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.
 
  • #5
matt grime said:
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! ;)
 
  • #6
Thanks for all the suggestions guys, could i just ask what is the simpler way of expressing nCr matt? Thanks
 
  • #7
[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.
 
  • #8
Tide said:
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]
 
  • #9
ComputerGeek said:
I thought that
[tex]\binom{n}{r} = \frac{n!}{r!(n-r)!}[/tex]

This is the same. Tide has just canceled 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.
 
  • #10
How would u prove it using induction? any ideas? hints? thanks u
 
  • #11
soulflyfgm said:
How would u prove it using induction? any ideas? hints? thanks u

See the identity in Moo Of Doom's post.
 
  • #12
shmoe said:
See the identity in Moo Of Doom's post.

ok...then what would I take as my induction hypothesis?...please help..i will apriciate if some one could help me start this proof by induction staring the first steps.. thank you so much
 
  • #13
Do induction on n. Read the thread in the probability section for more ideas.
 
  • #14
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
 
  • #15
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. :grumpy: the proof said multiply the numerator & denominator by the same thing, then you get [some expression]. end of proof.
 
  • #16
the problem is that i have to proove this by induction...can some one please review wat i post before and tell me if that prove is right ...thx so much
 
  • #17
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.
 
  • #18
Tide said:
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.
 
  • #19
proof

shmoe said:
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.


do u think this prove is correct

Let P(n) be the statement that for any n in the natural numbers N, nCr is an element of N for every r with 0<= r<= n
nCr = n!/(r!(n-r)!)
0Cr = o!/(r!(0-r)!) = 0
so P(0)E(belongs) in N (natural numbers)
Suppose P(n) is a natural number of any N
then since {n+1}Cr = nCr + nC{r-1} is true ( already proved it algebraically and i will add it to this part) so 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 review this prove and tell me if its right? thank you so much for ur help
 

1. Can n choose k be proven as a natural number without using induction?

Yes, it is possible to prove that n choose k is a natural number without using induction. There are several methods that can be used, such as combinatorial arguments, algebraic proofs, and graph theory proofs.

2. How is induction typically used to prove that n choose k is a natural number?

Induction is a common method used in mathematics to prove that a statement holds true for all natural numbers. In the case of n choose k, induction is often used to show that the formula for calculating n choose k always results in a natural number.

3. Are there any disadvantages to using induction to prove that n choose k is a natural number?

While induction is a powerful tool in mathematics, it is not always the most efficient method for proving statements. It can be time-consuming and may not provide the most intuitive explanation for why a statement is true.

4. Can you provide an example of a combinatorial proof for n choose k being a natural number?

One example of a combinatorial proof is the "stars and bars" method, which is often used to prove the formula for n choose k. This method involves representing the selection of k objects from a set of n objects as the placement of k stars in between (or "bars") n-1 objects. The number of ways this can be done is always a natural number.

5. What other mathematical concepts are related to proving that n choose k is a natural number?

Some related concepts include the binomial theorem, Pascal's triangle, and the fundamental principle of counting. These concepts are often used in conjunction with combinatorial arguments to prove that n choose k is a natural number.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
882
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Precalculus Mathematics Homework Help
Replies
5
Views
892
Replies
13
Views
1K
  • Math Proof Training and Practice
Replies
10
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
769
Back
Top