Mixing
Prove that $sum_{k=0}^{m}frac{binom{m}{k}}{binom{n}{k}}=frac{n+1}{n+1-m}$
$begingroup$
Prove that $sum_{k=0}^{m}dfrac{binom{m}{k}}{binom{n}{k}}=dfrac{n+1}{n+1-m}$.
We know, n > m. From the right side. we have $dfrac{n+1}{n+1-m}=dfrac{1}{1-dfrac{m}{n+1}}$. since n > m. $0<dfrac{m}{n+1}<1$. Then
$dfrac{1}{1-dfrac{m}{n+1}}=1+dfrac{m}{n+1}+(dfrac{m}{n+1})^2+...$
I don't know what to do next? Did I choose the right path?
combinatorics summation binomial-coefficients
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
$endgroup$
add a comment |
$begingroup$
Prove that $sum_{k=0}^{m}dfrac{binom{m}{k}}{binom{n}{k}}=dfrac{n+1}{n+1-m}$.
We know, n > m. From the right side. we have $dfrac{n+1}{n+1-m}=dfrac{1}{1-dfrac{m}{n+1}}$. since n > m. $0<dfrac{m}{n+1}<1$. Then
$dfrac{1}{1-dfrac{m}{n+1}}=1+dfrac{m}{n+1}+(dfrac{m}{n+1})^2+...$
I don't know what to do next? Did I choose the right path?
combinatorics summation binomial-coefficients
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
$endgroup$
1
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
1
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17
add a comment |
$begingroup$
Prove that $sum_{k=0}^{m}dfrac{binom{m}{k}}{binom{n}{k}}=dfrac{n+1}{n+1-m}$.
We know, n > m. From the right side. we have $dfrac{n+1}{n+1-m}=dfrac{1}{1-dfrac{m}{n+1}}$. since n > m. $0<dfrac{m}{n+1}<1$. Then
$dfrac{1}{1-dfrac{m}{n+1}}=1+dfrac{m}{n+1}+(dfrac{m}{n+1})^2+...$
I don't know what to do next? Did I choose the right path?
combinatorics summation binomial-coefficients
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
$endgroup$
Prove that $sum_{k=0}^{m}dfrac{binom{m}{k}}{binom{n}{k}}=dfrac{n+1}{n+1-m}$.
We know, n > m. From the right side. we have $dfrac{n+1}{n+1-m}=dfrac{1}{1-dfrac{m}{n+1}}$. since n > m. $0<dfrac{m}{n+1}<1$. Then
$dfrac{1}{1-dfrac{m}{n+1}}=1+dfrac{m}{n+1}+(dfrac{m}{n+1})^2+...$
I don't know what to do next? Did I choose the right path?
combinatorics summation binomial-coefficients
combinatorics summation binomial-coefficients
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
edited Jan 14 at 15:15
Martin Sleziak
44.7k10118272
44.7k10118272
asked Oct 18 '13 at 5:49
jin hajin ha
1216
asked Oct 18 '13 at 5:49
jin hajin ha
1216
asked Oct 18 '13 at 5:49
jin hajin ha
1216
1216
1
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
1
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17
add a comment |
1
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
1
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17
1
1
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
1
1
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Here's a probabilistic proof.
We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).
Then $$P(W |k) = frac{{m choose k}}{{n choose k}} [kle m]$$
and
$$P(W) = sum_{k} P(W |k) P(k) =frac{1}{n+1} sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{1} $$
Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then
$$P(W)=frac{1}{r+1}=frac{1}{n-m+1} tag{2}$$
Equating (1) and (2) we get the desired result.
A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.
Summing over all the positions of the orange ball, we have
$$C= sum_{k=0}^m {n-k choose m-k} ={n choose m}sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{3}$$
(for last equality see Isomorphism's answer).
On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 choose m}$ arrangements. Hence
$$C={n+1 choose m} ={n choose m} frac{n+1}{n-m+1} tag{4}$$
(again, for last equality see Isomorphism's answer).
Equating (3) and (4) we get the desired result.
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
$endgroup$
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
add a comment |
$begingroup$
You can solve your problem by following these steps:
1) First show that $$ dfrac{binom{m}{k}}{binom{n}{k}} = dfrac{binom{n-k}{m-k}}{binom{n}{m}}.$$
2) Now show that $$ binom{n}{m}cdotdfrac{n+1}{n+1-m} = binom{n+1}{m}.$$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4)Now prove the relation: $$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4a) You can prove this relation in various ways. One of them is to write $binom{n-m}{0}$ as $binom{n-m+1}{0}$ and then repeatedly use the relation $binom{x}{r}+binom{x}{r-1} = binom{x+1}{r}$. Another method is induction.
Best of luck!
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
$endgroup$
add a comment |
$begingroup$
Using the Heaviside Method for Partial Fractions, we get
$$
begin{align}
sum_{k=0}^mfrac{binom{m}{k}}{binom{n}{k}}
&=1+sum_{k=1}^mfrac{m(m-1)(m-2)dots(m-k+1)}{n(n-1)(n-2)dots(n-k+1)}tag{1}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{k-1}binom{k-1}{j}}{n-j}tag{2}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{3}\
&=1+msum_{j=0}^{m-1}sum_{k=j+1}^mfrac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{4}\[6pt]
&=1+frac{m}{n-m+1}tag{5}\[6pt]
&=frac{n+1}{n-m+1}tag{6}
end{align}
$$
Explanation:
$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $binom{m-1}{k-1}binom{k-1}{j}=binom{m-1}{j}binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $sumlimits_{k=j+1}^m(-1)^{k-j-1}binom{m-j-1}{k-j-1}=0^{m-j-1}=big[j=m-1big]$
$(6)$: addition
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f530642%2fprove-that-sum-k-0m-frac-binommk-binomnk-fracn1n1-m%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here's a probabilistic proof.
We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).
Then $$P(W |k) = frac{{m choose k}}{{n choose k}} [kle m]$$
and
$$P(W) = sum_{k} P(W |k) P(k) =frac{1}{n+1} sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{1} $$
Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then
$$P(W)=frac{1}{r+1}=frac{1}{n-m+1} tag{2}$$
Equating (1) and (2) we get the desired result.
A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.
Summing over all the positions of the orange ball, we have
$$C= sum_{k=0}^m {n-k choose m-k} ={n choose m}sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{3}$$
(for last equality see Isomorphism's answer).
On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 choose m}$ arrangements. Hence
$$C={n+1 choose m} ={n choose m} frac{n+1}{n-m+1} tag{4}$$
(again, for last equality see Isomorphism's answer).
Equating (3) and (4) we get the desired result.
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
$endgroup$
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
add a comment |
$begingroup$
Here's a probabilistic proof.
We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).
Then $$P(W |k) = frac{{m choose k}}{{n choose k}} [kle m]$$
and
$$P(W) = sum_{k} P(W |k) P(k) =frac{1}{n+1} sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{1} $$
Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then
$$P(W)=frac{1}{r+1}=frac{1}{n-m+1} tag{2}$$
Equating (1) and (2) we get the desired result.
A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.
Summing over all the positions of the orange ball, we have
$$C= sum_{k=0}^m {n-k choose m-k} ={n choose m}sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{3}$$
(for last equality see Isomorphism's answer).
On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 choose m}$ arrangements. Hence
$$C={n+1 choose m} ={n choose m} frac{n+1}{n-m+1} tag{4}$$
(again, for last equality see Isomorphism's answer).
Equating (3) and (4) we get the desired result.
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
$endgroup$
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
add a comment |
$begingroup$
Here's a probabilistic proof.
We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).
Then $$P(W |k) = frac{{m choose k}}{{n choose k}} [kle m]$$
and
$$P(W) = sum_{k} P(W |k) P(k) =frac{1}{n+1} sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{1} $$
Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then
$$P(W)=frac{1}{r+1}=frac{1}{n-m+1} tag{2}$$
Equating (1) and (2) we get the desired result.
A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.
Summing over all the positions of the orange ball, we have
$$C= sum_{k=0}^m {n-k choose m-k} ={n choose m}sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{3}$$
(for last equality see Isomorphism's answer).
On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 choose m}$ arrangements. Hence
$$C={n+1 choose m} ={n choose m} frac{n+1}{n-m+1} tag{4}$$
(again, for last equality see Isomorphism's answer).
Equating (3) and (4) we get the desired result.
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
$endgroup$
Here's a probabilistic proof.
We have $n$ balls in a bag, $m$ are white, $r=n-m$ are red. We do the following experiment: we draw a random integer $k$, uniformly distributed in $0 dots n$, and then we pick randomly $k$ balls (without replacement). Let $W$ be the event that all balls are white (more precisely, that no ball is red).
Then $$P(W |k) = frac{{m choose k}}{{n choose k}} [kle m]$$
and
$$P(W) = sum_{k} P(W |k) P(k) =frac{1}{n+1} sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{1} $$
Alternatively, our experiment is equivalent to: produce a random permutation of the $n$ balls, then check if the first $k$ balls ($k$ drawn as before) are white. Which is the same as saying: place a random bar in between the $n$ balls ($n+1$ positions) and check if it falls before the first red ball. Which is the same as thinking the bar as a new additional red ball, and looking if this one is the first red ball among the total $r+1$ red balls. Then
$$P(W)=frac{1}{r+1}=frac{1}{n-m+1} tag{2}$$
Equating (1) and (2) we get the desired result.
A similar alternative combinatorial way: We have $n+1$ balls, $m$ white, $r=n-m$ red, and one orange, otherwise undistinguishable. Let's $C$ count the number of ways of placing the balls in $n+1$ cells (numbered from $0$ to $n$) so that no red ball is before the orange one.
Summing over all the positions of the orange ball, we have
$$C= sum_{k=0}^m {n-k choose m-k} ={n choose m}sum_{k=0}^m frac{{m choose k}}{{n choose k}} tag{3}$$
(for last equality see Isomorphism's answer).
On the other side, we can consider the orange-red balls as a group (considering the orange distinguishable and placing it first, is the same as condiring the group undistinguishable), which gives ${n+1 choose m}$ arrangements. Hence
$$C={n+1 choose m} ={n choose m} frac{n+1}{n-m+1} tag{4}$$
(again, for last equality see Isomorphism's answer).
Equating (3) and (4) we get the desired result.
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
edited Oct 20 '13 at 21:02
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
answered Oct 19 '13 at 1:28
leonbloyleonbloy
41.1k645107
41.1k645107
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
add a comment |
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
This is a great proof! In the final displayed equation, $n-1$ should be $n+1$, no? It's just a typo, not a mathematical error.
$endgroup$
– Steve Kass
Oct 19 '13 at 1:59
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
$begingroup$
Typo fixed, thanks!
$endgroup$
– leonbloy
Oct 19 '13 at 2:13
add a comment |
$begingroup$
You can solve your problem by following these steps:
1) First show that $$ dfrac{binom{m}{k}}{binom{n}{k}} = dfrac{binom{n-k}{m-k}}{binom{n}{m}}.$$
2) Now show that $$ binom{n}{m}cdotdfrac{n+1}{n+1-m} = binom{n+1}{m}.$$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4)Now prove the relation: $$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4a) You can prove this relation in various ways. One of them is to write $binom{n-m}{0}$ as $binom{n-m+1}{0}$ and then repeatedly use the relation $binom{x}{r}+binom{x}{r-1} = binom{x+1}{r}$. Another method is induction.
Best of luck!
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
$endgroup$
add a comment |
$begingroup$
You can solve your problem by following these steps:
1) First show that $$ dfrac{binom{m}{k}}{binom{n}{k}} = dfrac{binom{n-k}{m-k}}{binom{n}{m}}.$$
2) Now show that $$ binom{n}{m}cdotdfrac{n+1}{n+1-m} = binom{n+1}{m}.$$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4)Now prove the relation: $$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4a) You can prove this relation in various ways. One of them is to write $binom{n-m}{0}$ as $binom{n-m+1}{0}$ and then repeatedly use the relation $binom{x}{r}+binom{x}{r-1} = binom{x+1}{r}$. Another method is induction.
Best of luck!
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
$endgroup$
add a comment |
$begingroup$
You can solve your problem by following these steps:
1) First show that $$ dfrac{binom{m}{k}}{binom{n}{k}} = dfrac{binom{n-k}{m-k}}{binom{n}{m}}.$$
2) Now show that $$ binom{n}{m}cdotdfrac{n+1}{n+1-m} = binom{n+1}{m}.$$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4)Now prove the relation: $$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4a) You can prove this relation in various ways. One of them is to write $binom{n-m}{0}$ as $binom{n-m+1}{0}$ and then repeatedly use the relation $binom{x}{r}+binom{x}{r-1} = binom{x+1}{r}$. Another method is induction.
Best of luck!
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
$endgroup$
You can solve your problem by following these steps:
1) First show that $$ dfrac{binom{m}{k}}{binom{n}{k}} = dfrac{binom{n-k}{m-k}}{binom{n}{m}}.$$
2) Now show that $$ binom{n}{m}cdotdfrac{n+1}{n+1-m} = binom{n+1}{m}.$$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4)Now prove the relation: $$ sum_{k=0}^mbinom{n-k}{m-k} = binom{n+1}{m}.$$
4a) You can prove this relation in various ways. One of them is to write $binom{n-m}{0}$ as $binom{n-m+1}{0}$ and then repeatedly use the relation $binom{x}{r}+binom{x}{r-1} = binom{x+1}{r}$. Another method is induction.
Best of luck!
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
answered Oct 18 '13 at 6:12
IsomorphismIsomorphism
3,1421439
3,1421439
add a comment |
add a comment |
$begingroup$
Using the Heaviside Method for Partial Fractions, we get
$$
begin{align}
sum_{k=0}^mfrac{binom{m}{k}}{binom{n}{k}}
&=1+sum_{k=1}^mfrac{m(m-1)(m-2)dots(m-k+1)}{n(n-1)(n-2)dots(n-k+1)}tag{1}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{k-1}binom{k-1}{j}}{n-j}tag{2}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{3}\
&=1+msum_{j=0}^{m-1}sum_{k=j+1}^mfrac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{4}\[6pt]
&=1+frac{m}{n-m+1}tag{5}\[6pt]
&=frac{n+1}{n-m+1}tag{6}
end{align}
$$
Explanation:
$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $binom{m-1}{k-1}binom{k-1}{j}=binom{m-1}{j}binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $sumlimits_{k=j+1}^m(-1)^{k-j-1}binom{m-j-1}{k-j-1}=0^{m-j-1}=big[j=m-1big]$
$(6)$: addition
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
$endgroup$
add a comment |
$begingroup$
Using the Heaviside Method for Partial Fractions, we get
$$
begin{align}
sum_{k=0}^mfrac{binom{m}{k}}{binom{n}{k}}
&=1+sum_{k=1}^mfrac{m(m-1)(m-2)dots(m-k+1)}{n(n-1)(n-2)dots(n-k+1)}tag{1}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{k-1}binom{k-1}{j}}{n-j}tag{2}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{3}\
&=1+msum_{j=0}^{m-1}sum_{k=j+1}^mfrac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{4}\[6pt]
&=1+frac{m}{n-m+1}tag{5}\[6pt]
&=frac{n+1}{n-m+1}tag{6}
end{align}
$$
Explanation:
$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $binom{m-1}{k-1}binom{k-1}{j}=binom{m-1}{j}binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $sumlimits_{k=j+1}^m(-1)^{k-j-1}binom{m-j-1}{k-j-1}=0^{m-j-1}=big[j=m-1big]$
$(6)$: addition
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
$endgroup$
add a comment |
$begingroup$
Using the Heaviside Method for Partial Fractions, we get
$$
begin{align}
sum_{k=0}^mfrac{binom{m}{k}}{binom{n}{k}}
&=1+sum_{k=1}^mfrac{m(m-1)(m-2)dots(m-k+1)}{n(n-1)(n-2)dots(n-k+1)}tag{1}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{k-1}binom{k-1}{j}}{n-j}tag{2}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{3}\
&=1+msum_{j=0}^{m-1}sum_{k=j+1}^mfrac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{4}\[6pt]
&=1+frac{m}{n-m+1}tag{5}\[6pt]
&=frac{n+1}{n-m+1}tag{6}
end{align}
$$
Explanation:
$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $binom{m-1}{k-1}binom{k-1}{j}=binom{m-1}{j}binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $sumlimits_{k=j+1}^m(-1)^{k-j-1}binom{m-j-1}{k-j-1}=0^{m-j-1}=big[j=m-1big]$
$(6)$: addition
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
$endgroup$
Using the Heaviside Method for Partial Fractions, we get
$$
begin{align}
sum_{k=0}^mfrac{binom{m}{k}}{binom{n}{k}}
&=1+sum_{k=1}^mfrac{m(m-1)(m-2)dots(m-k+1)}{n(n-1)(n-2)dots(n-k+1)}tag{1}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{k-1}binom{k-1}{j}}{n-j}tag{2}\
&=1+msum_{k=1}^msum_{j=0}^{k-1}frac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{3}\
&=1+msum_{j=0}^{m-1}sum_{k=j+1}^mfrac{(-1)^{k-j-1}binom{m-1}{j}binom{m-j-1}{k-j-1}}{n-j}tag{4}\[6pt]
&=1+frac{m}{n-m+1}tag{5}\[6pt]
&=frac{n+1}{n-m+1}tag{6}
end{align}
$$
Explanation:
$(1)$: break out the $k=0$ term and expand numerator and denominator
$(2)$: apply the Heaviside Method to the fraction in the sum
$(3)$: $binom{m-1}{k-1}binom{k-1}{j}=binom{m-1}{j}binom{m-j-1}{k-j-1}$
$(4)$: switch the order of summation
$(5)$: $sumlimits_{k=j+1}^m(-1)^{k-j-1}binom{m-j-1}{k-j-1}=0^{m-j-1}=big[j=m-1big]$
$(6)$: addition
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
edited Oct 19 '13 at 0:13
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
answered Oct 18 '13 at 7:31
robjohn♦robjohn
268k27308633
268k27308633
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f530642%2fprove-that-sum-k-0m-frac-binommk-binomnk-fracn1n1-m%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Since the sum $1+dfrac{m}{n+1}+left(dfrac{m}{n+1}right)^2+...$ has infinite terms and the left hand side of your original equation has only finite terms, there is no hope equating the two, term by term. Do you have any other strategy?
$endgroup$
– Isomorphism
Oct 18 '13 at 6:00
1
$begingroup$
If $m > n$, then the left hand side is infinite, since the denominator of the last $m - n$ terms becomes $0$.
$endgroup$
– Lucian
Oct 18 '13 at 6:17