Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-09-15 17:36:12

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Need a Hint

Ok last question of the night.

I am trying to prove that for n>=k>=1 the following holds:

C(n+1,k)=C(n,k)+C(n, k-1)

Now Ive set this problem by organizing my givens by using the definition of a combination and set a goal:

Givens:

n>=k>=1
C(n,k)= n!/[k!(n-k)!]
C(n,k-1)=n!/[(k-1)!(n-k+1)!]

Goal:

(n+1)!/[k!(n-k+1)!]  (which equals C(n+1,k))

Now from here, Im stuck. I working it out algebraically but that didnt really work. Are my givens correct? And if so, is there anything Im over looking as far as a given? Any hints on how to proceed?

Offline

#2 2007-09-16 01:55:58

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Need a Hint

You're correct so far. From here, you just need to add up your two fractions.
You'll need to fiddle with them a bit to give them the same denominator, but once you've done that everything should fall into place.


Why did the vector cross the road?
It wanted to be normal.

Offline

#3 2007-09-16 03:12:02

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need a Hint

This is a combinatorial problem.  So while you can use algebra to prove it, you can also you a combinatorial proof.  A combinatorial proof consists of counting the same thing in two different ways.  Since it is the same thing, the counting methods must be equal.

By definition, C(n+1, k) is the number of ways to choose k objects from a set of n+1 objects.

Take n+1 objects and fix one of them, call it x.  We first count the number of subsets of size k which contain x, and then the number of subsets of size k which don't contain x.  Since the two are mutually exclusive, adding them will yield the number of ways to choose k objects from n+1 objects.  So in the first case, where the subset contains x, we now have n objects to choose from (we lost x), and we need to choose k-1 of them.  This is C(n, k-1).  In the second case, we again have n objects to choose from since the sets may not contain x, but we need to choose k of them.  This is C(n, k).

Therefore, C(n+1) = C(n, k-1) + C(n, k)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#4 2007-09-16 05:17:25

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Re: Need a Hint

mathsyperson wrote:

You're correct so far. From here, you just need to add up your two fractions.
You'll need to fiddle with them a bit to give them the same denominator, but once you've done that everything should fall into place.

Heres what I got when I tried that, I got stuck because perhaps theres a property that Im missing that allows me to cancel things. But in adding the two givens and setting a common denominator yields:

n!{[(k-1)!(n-k+1)!+k!(n-k)! / [k!(n-k)!(k-1)!(n-k+1)!]}


Ricky, what you wrote doesnt seem all too clear to me at least in writing it mathematically.

Offline

#5 2007-09-16 06:30:25

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Need a Hint

That's correct, but there's an easier way of doing it. Try to alter the two given fractions so that their denominators are both k! (n-k+1)!.


Why did the vector cross the road?
It wanted to be normal.

Offline

#6 2007-09-16 06:38:40

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need a Hint

Ricky, what you wrote doesnt seem all too clear to me at least in writing it mathematically.

Clear as in understandable, or clear as in rigorous?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2007-09-16 06:49:52

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Re: Need a Hint

Ricky wrote:

Ricky, what you wrote doesnt seem all too clear to me at least in writing it mathematically.

Clear as in understandable, or clear as in rigorous?

Implementing it rigorously.

Offline

#8 2007-09-16 06:56:51

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need a Hint

Hmm, what exactly do you not find rigorous about it?  Here are the statements:

1. Number of combinations of choosing k out of n objects is C(n, k)
2. Number of such choices which contain a specific element x: C(n-1, k-1)
3. Number of such choices which don't contain a specific element x: C(n-1, k)

x can not be both in and out of a set, so (2) and (3) are mutually exclusive.  As x must be either in or out of a set, the sum of these will result in the total of all the choices.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#9 2007-09-16 07:31:06

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Re: Need a Hint

Ricky wrote:

Hmm, what exactly do you not find rigorous about it?  Here are the statements:

1. Number of combinations of choosing k out of n objects is C(n, k)
2. Number of such choices which contain a specific element x: C(n-1, k-1)
3. Number of such choices which don't contain a specific element x: C(n-1, k)

x can not be both in and out of a set, so (2) and (3) are mutually exclusive.  As x must be either in or out of a set, the sum of these will result in the total of all the choices.

Nevermind, I had to google combinatorial proof and double counting. I thought you were giving me instructions on how to follow through algebraically. But now I have another question, whats the difference between bijective proof and double counting? They seem to be very related.

Offline

#10 2007-09-16 08:12:06

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Re: Need a Hint

mathsyperson wrote:

That's correct, but there's an easier way of doing it. Try to alter the two given fractions so that their denominators are both k! (n-k+1)!.

OK I did the following:

Using the fact that k!=k(k-1)! and that (n-k+1)! = (n-k+1)(n-k)! I was able to get a common denominator and then have n!(n+1) on the numerator which equals the other side.

Last edited by MarkusD (2007-09-16 08:12:31)

Offline

#11 2007-09-16 08:47:22

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need a Hint

They are quite similar, the difference lies in where you make the comparison.  In a double counting proof, you make the comparison after counting each way, at the end.  In a bijective proof, you relate two elements of each counting technique each step of the way.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

Board footer

Powered by FluxBB