Proving combination is a natural number by induction

Click For Summary

Discussion Overview

The discussion revolves around proving that the binomial coefficient nCr, where r ≤ n, is a natural number using mathematical induction. Participants explore various approaches to formulate the proof and clarify the concept of induction itself.

Discussion Character

  • Exploratory
  • Technical explanation
  • Homework-related
  • Mathematical reasoning

Main Points Raised

  • Some participants express uncertainty about how to start the induction proof and seek guidance on formulating a mathematical statement.
  • Others suggest considering Pascal's triangle as a potential method to approach the proof.
  • One participant proposes proving divisibility, specifically that n! is divisible by r!(n-r)!, as a way to establish the natural number status of nCr.
  • There are discussions about the construction of Pascal's triangle and its relevance to the proof.
  • Participants inquire about the inductive hypothesis and the necessary steps to complete the proof, with some confusion about what constitutes a proper hypothesis.
  • Clarifications are made regarding the inductive hypothesis and the inductive step, with emphasis on the need to demonstrate that if one case holds, the next must also hold.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best approach to the proof, and multiple competing views on how to structure the induction argument remain. There is ongoing uncertainty about the formulation of the inductive hypothesis.

Contextual Notes

Some participants express that induction is a foreign concept to them, indicating a potential gap in understanding the method itself. There are also mentions of minor details that need to be clarified in the proof process.

Kariege
Messages
15
Reaction score
0
Hi,
I've seen on on several sites that you can prove that nCr, where r<=n, is a natural number. I'm not sure how to do this by induction.
So I need help on this proof. How do I write this as a mathematical statement at the start of the induction proof?

Thank you
 
Mathematics news on Phys.org
Kariege said:
Hi,
I've seen on on several sites that you can prove that nCr, where r<=n, is a natural number. I'm not sure how to do this by induction.
So I need help on this proof. How do I write this as a mathematical statement at the start of the induction proof?

Thank you

You could start by thinking about Pascal's triangle. I hope this isn't homework!
 
I'm not sure how to link this to Pascal's triangle to help me to prove. But I'm thinking about proving divisibility, like n! is divisible by r!(n-r)!, or r!(n-r)! is a multiple of n!.I've been wondering how to set up the statement mathematically.
This is not homework. I just want to know how you're supposed to prove this because induction is quite a foreign concept to me and I've only been able to prove some of the easy ones like formula for series.
 
Kariege said:
I'm not sure how to link this to Pascal's triangle to help me to prove. But I'm thinking about proving divisibility, like n! is divisible by r!(n-r)!, or r!(n-r)! is a multiple of n!.I've been wondering how to set up the statement mathematically.
This is not homework. I just want to know how you're supposed to prove this because induction is quite a foreign concept to me and I've only been able to prove some of the easy ones like formula for series.

How do you construct Pascal's Triangle?
 
you add the two numbers above. so it's nCk=(n-1)C(k-1) + (n-1)Ck.
Then it's (n-1)!/[(k-1)!(n-k)!] + (n-1)!/[k!(n-k-1)!] = nCk
Am I on the right track?
 
Kariege said:
you add the two numbers above. so it's nCk=(n-1)C(k-1) + (n-1)Ck.
Then it's (n-1)!/[(k-1)!(n-k)!] + (n-1)!/[k!(n-k-1)!] = nCk
Am I on the right track?

Yes, right on track. You need to think about induction now.
 
I tried manipulating it but then I ended up nowhere. Could you guide me a little bit?
 
Kariege said:
I tried manipulating it but then I ended up nowhere. Could you guide me a little bit?

Can you state your inductive hypothesis?

There is no algebra or any calculations required.
 
Is it (n-1)C(k-1) must be a natural number and (n-1)Ck must also be a natural number?
 
  • #10
Kariege said:
Is it (n-1)C(k-1) must be a natural number and (n-1)Ck must also be a natural number?

That's not a hypothesis! But, that is the argument. The inductive hypothesis is:

Assume ##\binom{n-1}{k}## is a whole number for some ##n## and every ##k##.

And, the inductive step is to show that this implies that:

##\binom{n}{k}## is a whole number for every ##k##.

There is a minor detail to iron out. Can you see what it is?

Also, you would benefit from writing out a full proof by induction using what you have.
 
  • Like
Likes   Reactions: Kariege

Similar threads

Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Is there any way to simplify my proof by induction?
  • · Replies 13 ·
Replies
13
Views
2K
MHB Solve Prove by Induction: 3^2n+1 + 2^n-1 Divisible by 7
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad [ASK] Mathematical Induction: Prove 7^n-2^n is divisible by 5.
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Theorems that can't be proved by induction
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Proof by induction of block diagonal decomposition of a matrix
  • · Replies 4 ·
Replies
4
Views
2K
MHB Proving Divisibility by 6 Using Mathematical Induction
  • · Replies 7 ·
Replies
7
Views
4K
Graduate Ramanujan Summation, Variations of
  • · Replies 7 ·
Replies
7
Views
2K
Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
9K