Proving combination is a natural number by induction

In summary, the conversation discusses proving that nCr, where r<=n, is a natural number using induction. The conversation references Pascal's triangle and the process of constructing it, as well as the algebraic manipulations needed to prove the statement. The inductive hypothesis is stated and the need for a minor detail to be addressed is mentioned. The speaker is advised to write out a full proof using their current understanding.
  • #1
Kariege
15
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
  • #2
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!
 
  • #3
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.
 
  • #4
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?
 
  • #5
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?
 
  • #6
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.
 
  • #7
I tried manipulating it but then I ended up nowhere. Could you guide me a little bit?
 
  • #8
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.
 
  • #9
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 Kariege

What is the concept of induction in mathematics?

Induction is a mathematical proof technique used to prove statements about all natural numbers. It involves two steps: the base case, where the statement is proven to be true for the first natural number, and the induction step, where it is shown that if the statement holds true for one natural number, it also holds true for the next natural number.

How do you use induction to prove that a combination is a natural number?

To prove that a combination is a natural number using induction, we first show that it is true for the smallest possible value, usually 0 or 1. Then, we assume that the statement is true for some arbitrary natural number k, and use this assumption to prove that it is also true for the next natural number, k+1. This shows that the statement is true for all natural numbers, including combinations.

Can induction be used to prove statements about real numbers?

No, induction can only be used to prove statements about natural numbers. This is because real numbers are infinite and continuous, whereas natural numbers are discrete and finite. Induction relies on being able to increment by 1, which is not possible with real numbers.

What are the limitations of using induction to prove statements?

Induction can only be used to prove statements that are true for all natural numbers. It cannot be used for statements that are only true for some natural numbers, or for statements about other types of numbers. Additionally, it is not a standalone proof technique and must be supported by other mathematical tools and principles.

Can induction be used to prove statements about infinite sets?

Yes, induction can be used to prove statements about infinite sets as long as the sets are well-ordered. A well-ordered set is a set where every non-empty subset has a least element. Natural numbers are an example of a well-ordered set, but real numbers are not. Therefore, induction cannot be used to prove statements about real numbers, but it can be used for certain infinite sets.

Similar threads

Replies
2
Views
1K
Replies
3
Views
2K
Replies
7
Views
2K
  • General Math
Replies
10
Views
1K
Replies
5
Views
2K
  • General Math
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
338
  • General Math
Replies
7
Views
3K
Replies
8
Views
2K
Back
Top