How to prove a binomial identity?
- Thread starter KrabLord
- Start date
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
You want to choose r objects from k+1 objects.
Suppose you number the k+1 objects 1, 2, 3,...,k+1
Lets concentrate on the 1st object. Either we choose the first object or we don't choose it.
Suppose we do choose the 1st object: So we need to choose an additional r-1 objects from k objects (we can't pick the 1st object again!)
Suppose we do not choose the 1st object: So we need to choose r objects from k objects (the objects we are picking from is 2,3,4,...k+1).
Therefore (k+1)Cr = kC(r-1) + kCr
Alternative you can just use the definition for kC(r-1) and kCr, get a .common denominator and note that it equals (k+1)Cr
Suppose you number the k+1 objects 1, 2, 3,...,k+1
Lets concentrate on the 1st object. Either we choose the first object or we don't choose it.
Suppose we do choose the 1st object: So we need to choose an additional r-1 objects from k objects (we can't pick the 1st object again!)
Suppose we do not choose the 1st object: So we need to choose r objects from k objects (the objects we are picking from is 2,3,4,...k+1).
Therefore (k+1)Cr = kC(r-1) + kCr
Alternative you can just use the definition for kC(r-1) and kCr, get a .common denominator and note that it equals (k+1)Cr
topsquark
Senior Member
- Joined
- Aug 27, 2012
- Messages
- 2,393
You need to let us know what you've been able to do so far.
Since I don't know where you are with this I'll start you off:
[math]\left ( \begin{matrix} k \\ r - 1 \end{matrix} \right ) + \left ( \begin{matrix} k \\ r \end{matrix} \right ) = \left ( \begin{matrix} k + 1 \\ r \end{matrix} \right ) [/math]
You need to show:
[math] \dfrac{k!}{(r - 1)!(k - (r - 1))!} + \dfrac{k!}{r!(k - r)!} = \dfrac{(k + 1)!}{r!((k + 1) - r)!}[/math]
Give this a try and let us know what you can do with this.
-Dan
Since I don't know where you are with this I'll start you off:
[math]\left ( \begin{matrix} k \\ r - 1 \end{matrix} \right ) + \left ( \begin{matrix} k \\ r \end{matrix} \right ) = \left ( \begin{matrix} k + 1 \\ r \end{matrix} \right ) [/math]
You need to show:
[math] \dfrac{k!}{(r - 1)!(k - (r - 1))!} + \dfrac{k!}{r!(k - r)!} = \dfrac{(k + 1)!}{r!((k + 1) - r)!}[/math]
Give this a try and let us know what you can do with this.
-Dan
KrabLord
New member
- Joined
- Jul 27, 2019
- Messages
- 38
When you say “let’s concentrate on the first object,” what are you referring to?
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
To be more clear, lets call the k+1 objects the 1st object, the 2nd object, the 3rd object,..., the (k+1)st object.
Now either we choose the 1st object or we do not choose the 1st object. I am just breaking up (k+1)Cr combinations into to two disjoint sets--those that include the 1st object and those that do not include the 1st object. Is this clear?
KrabLord
New member
- Joined
- Jul 27, 2019
- Messages
- 38
I’m confused as to why your reasoning implies the conclusion. This is due to my lack of understanding of what it means to select objects. I can’t translate your reasoning into mathematical notation.
KrabLord
New member
- Joined
- Jul 27, 2019
- Messages
- 38
also, I am lost as to how the denominator can be rearranged to yield (k+1)Cr. If you can walk me through that, I’d be very grateful!
KrabLord
New member
- Joined
- Jul 27, 2019
- Messages
- 38
actually, I figured out how to rearrange the denominator to prove the identity, but I am still very interested in understanding your reasoning!! Thank you!
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
In how many ways can you choose r objects from k+1 objects if you must choose the 1st object?
In how many ways can you choose r objects from k+1 objects if you will not choose the 1st object?
Please answer these questions. If you have any questions/problems then please ask.
In how many ways can you choose r objects from k+1 objects if you will not choose the 1st object?
Please answer these questions. If you have any questions/problems then please ask.
D
Deleted member 4993
Guest
Jomo,
Can you please rephrase that question?
I do not see a way to choose any more object/s, if I do not choose the 1st object?
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
Here is better wording.
If in the end you want to choose r objects from k+1 objects, then in how many ways can you do this if you must choose the 1st object?
If in the end you want to choose r objects from k+1 objects, then in how many ways can you do this if you will not choose the 1st object?
If in the end you want to choose r objects from k+1 objects, then in how many ways can you do this if you must choose the 1st object?
If in the end you want to choose r objects from k+1 objects, then in how many ways can you do this if you will not choose the 1st object?
KrabLord
New member
- Joined
- Jul 27, 2019
- Messages
- 38
I know the answers are r - 1 and r, respectively, but I fail entirely to understand why that’s the case. Is it because 0 <= r < k+1 ? if so, why?
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
Not sure how you know the answer but don't know why
The answers are to be in the form of aCb (the number of ways to choose b objects from a objects)
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
You goal is to compute how many ways you can pick r objects from from k+1 objects.
Imagine the k+1 objects in a line and numbered 1 through k+1
Now some of these combinations will include object number 1 and some will not include objects number 1. I hope that you see that the number way to include object number 1 plus the number of way to exclude object number 1 will equal rC(k+1)
Suppose you are going to choose number 1. So there is no decision to be made with object number 1 as you ARE choosing number 1. So what decisions do you have to make? Since your goal is to pick r objects and you already picked 1, then you must pick r-1 more objects. Now where are you going to choose the r-1 objects from? The answer is from object number 2, from object number 3, ..., object number k+1, which is k objects. So you need to choose r-1 objects from k or (n-1)Ck
Now suppose you are NOT going to choose object number 1. So there is no decision to be made with object number 1 as you are NOT choosing number 1. So what decisions do you have to make? Since your goal is to pick r objects and you so far picked none, then you must pick r objects. Now where are you going to choose the r objects from? The answer is from object number 2, from object number 3, ..., object number k+1, which is k objects. So you need to choose r objects from k or rCk
As a result of all this we get rC(k+1) = (n-1)Ck + rCk
Imagine the k+1 objects in a line and numbered 1 through k+1
Now some of these combinations will include object number 1 and some will not include objects number 1. I hope that you see that the number way to include object number 1 plus the number of way to exclude object number 1 will equal rC(k+1)
Suppose you are going to choose number 1. So there is no decision to be made with object number 1 as you ARE choosing number 1. So what decisions do you have to make? Since your goal is to pick r objects and you already picked 1, then you must pick r-1 more objects. Now where are you going to choose the r-1 objects from? The answer is from object number 2, from object number 3, ..., object number k+1, which is k objects. So you need to choose r-1 objects from k or (n-1)Ck
Now suppose you are NOT going to choose object number 1. So there is no decision to be made with object number 1 as you are NOT choosing number 1. So what decisions do you have to make? Since your goal is to pick r objects and you so far picked none, then you must pick r objects. Now where are you going to choose the r objects from? The answer is from object number 2, from object number 3, ..., object number k+1, which is k objects. So you need to choose r objects from k or rCk
As a result of all this we get rC(k+1) = (n-1)Ck + rCk
It seems to me that we have ignored Dan's very cogent advice.
There are two very distinct issue: (1) why does a binomial coefficient give the number of distinct ways to select r objects from k distinct objects without regard to order, and (2) how to show algebraically that a certain relationship exists among three different binomial coefficients.
The first issue needs to be demonstrated by a proof by induction. Moreover, it requires a fair amount of explanation about the meaning of what is being demonstrated.
The second issue simply takes a bit of algebra plus a clear understanding of factorial notation.
[MATH]\text {PROVE: } 1 \le r \le n \text { and } k,\ r \in \mathbb Z \implies \dbinom{k}{r - 1} + \dbinom{k}{r} = \dbinom{k + 1}{r}.[/MATH]
As topsquark implied, binomial coefficients are well defined fractions, and we know that to add fractions we need equal common denominators.
[MATH]\dbinom{k}{r - 1} + \dbinom{k}{r} = \dfrac{k!}{(r - 1)! * \{k - (r - 1)\}}+ \dfrac{k!}{r! * (k - r)!} =[/MATH]
[MATH]\dfrac{k!}{(r - 1)! * (k + 1 - r)!} + \dfrac{k!}{r! * (k - r)!} =[/MATH]
[MATH]\dfrac{r * k!}{r * (r - 1)! * (k + 1 - r)!} + \dfrac{(k + 1 - r) * k!}{r! * (k + 1 - r) * (k - r)!} = [/MATH]
[MATH]\dfrac{r * k!}{r! * (k + 1 - r)!} + \dfrac{(k + 1 - r) * k!}{r! * (k + 1 - r)!}.[/MATH]
Now do the addition and simplify. What do you get? Does that look like a binomial coefficient?
There are two very distinct issue: (1) why does a binomial coefficient give the number of distinct ways to select r objects from k distinct objects without regard to order, and (2) how to show algebraically that a certain relationship exists among three different binomial coefficients.
The first issue needs to be demonstrated by a proof by induction. Moreover, it requires a fair amount of explanation about the meaning of what is being demonstrated.
The second issue simply takes a bit of algebra plus a clear understanding of factorial notation.
[MATH]\text {PROVE: } 1 \le r \le n \text { and } k,\ r \in \mathbb Z \implies \dbinom{k}{r - 1} + \dbinom{k}{r} = \dbinom{k + 1}{r}.[/MATH]
As topsquark implied, binomial coefficients are well defined fractions, and we know that to add fractions we need equal common denominators.
[MATH]\dbinom{k}{r - 1} + \dbinom{k}{r} = \dfrac{k!}{(r - 1)! * \{k - (r - 1)\}}+ \dfrac{k!}{r! * (k - r)!} =[/MATH]
[MATH]\dfrac{k!}{(r - 1)! * (k + 1 - r)!} + \dfrac{k!}{r! * (k - r)!} =[/MATH]
[MATH]\dfrac{r * k!}{r * (r - 1)! * (k + 1 - r)!} + \dfrac{(k + 1 - r) * k!}{r! * (k + 1 - r) * (k - r)!} = [/MATH]
[MATH]\dfrac{r * k!}{r! * (k + 1 - r)!} + \dfrac{(k + 1 - r) * k!}{r! * (k + 1 - r)!}.[/MATH]
Now do the addition and simplify. What do you get? Does that look like a binomial coefficient?