Mixing
Is there some way to prove $nbinom nr=(r+1)binom n{r+1}+rbinom nr$ using generating functions?
$begingroup$
I have to prove that $$n{nchoose{r}}=(r+1){nchoose{r+1}}+r{nchoose{r}}$$
I can prove this combinatorially as follows, we have $n$ people, we want to choose $r$ people and a leader who could be within the $r$-group or outside the $r$-group but among the $n$ people. The number of such possible groups is obviously $n{nchoose{r}}$. Or we could simply choose $r+1$ people for the case when the leader is not within the group and then among them I can choose one of those $(r+1)$ to be the leader (which accounts for the $(r+1){nchoose{r+1}}$) and for the cases when the leader is withing the group, I choose $r$ people and then among those $r$ people I choose one of them as the leader (which accounts for the $r{nchoose{r}}$).
But I am curious if there is a proof using generating functions. I am new to using generating functions and even a hint would help (if the solution is possible) because I am just not getting how to begin.
combinatorics binomial-coefficients generating-functions
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
$endgroup$
add a comment |
$begingroup$
I have to prove that $$n{nchoose{r}}=(r+1){nchoose{r+1}}+r{nchoose{r}}$$
I can prove this combinatorially as follows, we have $n$ people, we want to choose $r$ people and a leader who could be within the $r$-group or outside the $r$-group but among the $n$ people. The number of such possible groups is obviously $n{nchoose{r}}$. Or we could simply choose $r+1$ people for the case when the leader is not within the group and then among them I can choose one of those $(r+1)$ to be the leader (which accounts for the $(r+1){nchoose{r+1}}$) and for the cases when the leader is withing the group, I choose $r$ people and then among those $r$ people I choose one of them as the leader (which accounts for the $r{nchoose{r}}$).
But I am curious if there is a proof using generating functions. I am new to using generating functions and even a hint would help (if the solution is possible) because I am just not getting how to begin.
combinatorics binomial-coefficients generating-functions
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
$endgroup$
add a comment |
$begingroup$
I have to prove that $$n{nchoose{r}}=(r+1){nchoose{r+1}}+r{nchoose{r}}$$
I can prove this combinatorially as follows, we have $n$ people, we want to choose $r$ people and a leader who could be within the $r$-group or outside the $r$-group but among the $n$ people. The number of such possible groups is obviously $n{nchoose{r}}$. Or we could simply choose $r+1$ people for the case when the leader is not within the group and then among them I can choose one of those $(r+1)$ to be the leader (which accounts for the $(r+1){nchoose{r+1}}$) and for the cases when the leader is withing the group, I choose $r$ people and then among those $r$ people I choose one of them as the leader (which accounts for the $r{nchoose{r}}$).
But I am curious if there is a proof using generating functions. I am new to using generating functions and even a hint would help (if the solution is possible) because I am just not getting how to begin.
combinatorics binomial-coefficients generating-functions
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
$endgroup$
I have to prove that $$n{nchoose{r}}=(r+1){nchoose{r+1}}+r{nchoose{r}}$$
I can prove this combinatorially as follows, we have $n$ people, we want to choose $r$ people and a leader who could be within the $r$-group or outside the $r$-group but among the $n$ people. The number of such possible groups is obviously $n{nchoose{r}}$. Or we could simply choose $r+1$ people for the case when the leader is not within the group and then among them I can choose one of those $(r+1)$ to be the leader (which accounts for the $(r+1){nchoose{r+1}}$) and for the cases when the leader is withing the group, I choose $r$ people and then among those $r$ people I choose one of them as the leader (which accounts for the $r{nchoose{r}}$).
But I am curious if there is a proof using generating functions. I am new to using generating functions and even a hint would help (if the solution is possible) because I am just not getting how to begin.
combinatorics binomial-coefficients generating-functions
combinatorics binomial-coefficients generating-functions
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
edited Jan 14 at 16:11
Martin Sleziak
44.8k10118272
44.8k10118272
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
asked Jan 14 at 3:16
Shubhraneel PalShubhraneel Pal
46439
46439
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^ntag{1}
end{align*}
Given a generating function $A(x)$ we have
begin{align*}
A(x)&=sum_{j=0}^infty a_j x^jqquadqquad A^{prime}(x)=sum_{j=0}^infty ja_jx^{j-1}
end{align*}
from which we derive by comparing coefficients
begin{align*}
r a_r&=color{blue}{r[x^r]A(x)=[x^{r-1}]A^{prime}(x)}tag{2}
end{align*}
Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity
begin{align*}
color{blue}{(r+1)}&color{blue}{binom{n}{r+1}+rbinom{n}{r}}\
&=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^ntag{3}\
&=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}tag{4}\
&=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}tag{5}\
&=n[x^r](1+x)^{n-1}(1+x)tag{6}\
&=n[x^r](1+x)^n\
&,,color{blue}{=nbinom{n}{r}}tag{7}
end{align*}
and the claim follows.
Comment:
In (3) we apply (1) twice.
In (4) we apply (2) twice.
In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (6) we use the linearity of the coefficient of operator.
In (7) we select the coefficient of $x^r$.
Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial
identity
begin{align*}
color{blue}{(r+1)binom{n}{r+1}}&=(r+1)frac{n(n-1)cdots(n-r+1)(n-r)}{(r+1)rcdots 2cdot 1}\
&=frac{n(n-1)cdots(n-r+1)}{r(r-1)cdots2cdot 1}(n-r)\
&,,color{blue}{=binom{n}{r}(n-r)}
end{align*}
to derive
begin{align*}
(r+1)binom{n}{r+1}+rbinom{n}{r}=(n-r)binom{n}{r}+rbinom{n}{r}=nbinom{n}{r}
end{align*}
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
$endgroup$
add a comment |
$begingroup$
There are several generating function approaches.
We could take the generating function of both sides with respect to $r$, and try to prove that
$$
sum_{r ge 0} left(n binom nrright) x^r = sum_{r ge 0} left((r+1) binom{n}{r+1} + r binom nrright)x^r.
$$
To prove this, we want closed forms for both sides, which start with the generating function
$$
(1+x)^n = sum_{r ge 0} binom nr x^r.
$$
On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.
We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.
Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with
$$
sum_{n ge 0} sum_{rge 0} binom nr x^r y^n = sum_{n ge 0}(1+x)^n y^n = frac{1}{1-(1+x)y}.
$$
Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n binom nr$, or $r binom nr$, or $(r+1)binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
$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%2f3072810%2fis-there-some-way-to-prove-n-binom-nr-r1-binom-nr1r-binom-nr-using-gene%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^ntag{1}
end{align*}
Given a generating function $A(x)$ we have
begin{align*}
A(x)&=sum_{j=0}^infty a_j x^jqquadqquad A^{prime}(x)=sum_{j=0}^infty ja_jx^{j-1}
end{align*}
from which we derive by comparing coefficients
begin{align*}
r a_r&=color{blue}{r[x^r]A(x)=[x^{r-1}]A^{prime}(x)}tag{2}
end{align*}
Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity
begin{align*}
color{blue}{(r+1)}&color{blue}{binom{n}{r+1}+rbinom{n}{r}}\
&=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^ntag{3}\
&=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}tag{4}\
&=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}tag{5}\
&=n[x^r](1+x)^{n-1}(1+x)tag{6}\
&=n[x^r](1+x)^n\
&,,color{blue}{=nbinom{n}{r}}tag{7}
end{align*}
and the claim follows.
Comment:
In (3) we apply (1) twice.
In (4) we apply (2) twice.
In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (6) we use the linearity of the coefficient of operator.
In (7) we select the coefficient of $x^r$.
Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial
identity
begin{align*}
color{blue}{(r+1)binom{n}{r+1}}&=(r+1)frac{n(n-1)cdots(n-r+1)(n-r)}{(r+1)rcdots 2cdot 1}\
&=frac{n(n-1)cdots(n-r+1)}{r(r-1)cdots2cdot 1}(n-r)\
&,,color{blue}{=binom{n}{r}(n-r)}
end{align*}
to derive
begin{align*}
(r+1)binom{n}{r+1}+rbinom{n}{r}=(n-r)binom{n}{r}+rbinom{n}{r}=nbinom{n}{r}
end{align*}
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
$endgroup$
add a comment |
$begingroup$
Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^ntag{1}
end{align*}
Given a generating function $A(x)$ we have
begin{align*}
A(x)&=sum_{j=0}^infty a_j x^jqquadqquad A^{prime}(x)=sum_{j=0}^infty ja_jx^{j-1}
end{align*}
from which we derive by comparing coefficients
begin{align*}
r a_r&=color{blue}{r[x^r]A(x)=[x^{r-1}]A^{prime}(x)}tag{2}
end{align*}
Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity
begin{align*}
color{blue}{(r+1)}&color{blue}{binom{n}{r+1}+rbinom{n}{r}}\
&=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^ntag{3}\
&=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}tag{4}\
&=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}tag{5}\
&=n[x^r](1+x)^{n-1}(1+x)tag{6}\
&=n[x^r](1+x)^n\
&,,color{blue}{=nbinom{n}{r}}tag{7}
end{align*}
and the claim follows.
Comment:
In (3) we apply (1) twice.
In (4) we apply (2) twice.
In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (6) we use the linearity of the coefficient of operator.
In (7) we select the coefficient of $x^r$.
Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial
identity
begin{align*}
color{blue}{(r+1)binom{n}{r+1}}&=(r+1)frac{n(n-1)cdots(n-r+1)(n-r)}{(r+1)rcdots 2cdot 1}\
&=frac{n(n-1)cdots(n-r+1)}{r(r-1)cdots2cdot 1}(n-r)\
&,,color{blue}{=binom{n}{r}(n-r)}
end{align*}
to derive
begin{align*}
(r+1)binom{n}{r+1}+rbinom{n}{r}=(n-r)binom{n}{r}+rbinom{n}{r}=nbinom{n}{r}
end{align*}
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
$endgroup$
add a comment |
$begingroup$
Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^ntag{1}
end{align*}
Given a generating function $A(x)$ we have
begin{align*}
A(x)&=sum_{j=0}^infty a_j x^jqquadqquad A^{prime}(x)=sum_{j=0}^infty ja_jx^{j-1}
end{align*}
from which we derive by comparing coefficients
begin{align*}
r a_r&=color{blue}{r[x^r]A(x)=[x^{r-1}]A^{prime}(x)}tag{2}
end{align*}
Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity
begin{align*}
color{blue}{(r+1)}&color{blue}{binom{n}{r+1}+rbinom{n}{r}}\
&=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^ntag{3}\
&=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}tag{4}\
&=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}tag{5}\
&=n[x^r](1+x)^{n-1}(1+x)tag{6}\
&=n[x^r](1+x)^n\
&,,color{blue}{=nbinom{n}{r}}tag{7}
end{align*}
and the claim follows.
Comment:
In (3) we apply (1) twice.
In (4) we apply (2) twice.
In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (6) we use the linearity of the coefficient of operator.
In (7) we select the coefficient of $x^r$.
Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial
identity
begin{align*}
color{blue}{(r+1)binom{n}{r+1}}&=(r+1)frac{n(n-1)cdots(n-r+1)(n-r)}{(r+1)rcdots 2cdot 1}\
&=frac{n(n-1)cdots(n-r+1)}{r(r-1)cdots2cdot 1}(n-r)\
&,,color{blue}{=binom{n}{r}(n-r)}
end{align*}
to derive
begin{align*}
(r+1)binom{n}{r+1}+rbinom{n}{r}=(n-r)binom{n}{r}+rbinom{n}{r}=nbinom{n}{r}
end{align*}
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
$endgroup$
Another variation with generating functions is based upon the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance
begin{align*}
binom{n}{r}=[x^r](1+x)^ntag{1}
end{align*}
Given a generating function $A(x)$ we have
begin{align*}
A(x)&=sum_{j=0}^infty a_j x^jqquadqquad A^{prime}(x)=sum_{j=0}^infty ja_jx^{j-1}
end{align*}
from which we derive by comparing coefficients
begin{align*}
r a_r&=color{blue}{r[x^r]A(x)=[x^{r-1}]A^{prime}(x)}tag{2}
end{align*}
Equipped with (1) and (2) we obtain starting with the right-hand side of OPs identity
begin{align*}
color{blue}{(r+1)}&color{blue}{binom{n}{r+1}+rbinom{n}{r}}\
&=(r+1)[x^{r+1}](1+x)^n+r[x^r](1+x)^ntag{3}\
&=[x^r]n(1+x)^{n-1}+[x^{r-1}]n(1+x)^{n-1}tag{4}\
&=[x^r]n(1+x)^{n-1}+[x^r]xn(1+x)^{n-1}tag{5}\
&=n[x^r](1+x)^{n-1}(1+x)tag{6}\
&=n[x^r](1+x)^n\
&,,color{blue}{=nbinom{n}{r}}tag{7}
end{align*}
and the claim follows.
Comment:
In (3) we apply (1) twice.
In (4) we apply (2) twice.
In (5) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (6) we use the linearity of the coefficient of operator.
In (7) we select the coefficient of $x^r$.
Note: When looking for an algebraic proof besides the combinatorial one which you already gave, we can also go the easy way by recalling the binomial
identity
begin{align*}
color{blue}{(r+1)binom{n}{r+1}}&=(r+1)frac{n(n-1)cdots(n-r+1)(n-r)}{(r+1)rcdots 2cdot 1}\
&=frac{n(n-1)cdots(n-r+1)}{r(r-1)cdots2cdot 1}(n-r)\
&,,color{blue}{=binom{n}{r}(n-r)}
end{align*}
to derive
begin{align*}
(r+1)binom{n}{r+1}+rbinom{n}{r}=(n-r)binom{n}{r}+rbinom{n}{r}=nbinom{n}{r}
end{align*}
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
edited Jan 14 at 21:57
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
answered Jan 14 at 15:26
Markus ScheuerMarkus Scheuer
61.6k457146
61.6k457146
add a comment |
add a comment |
$begingroup$
There are several generating function approaches.
We could take the generating function of both sides with respect to $r$, and try to prove that
$$
sum_{r ge 0} left(n binom nrright) x^r = sum_{r ge 0} left((r+1) binom{n}{r+1} + r binom nrright)x^r.
$$
To prove this, we want closed forms for both sides, which start with the generating function
$$
(1+x)^n = sum_{r ge 0} binom nr x^r.
$$
On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.
We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.
Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with
$$
sum_{n ge 0} sum_{rge 0} binom nr x^r y^n = sum_{n ge 0}(1+x)^n y^n = frac{1}{1-(1+x)y}.
$$
Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n binom nr$, or $r binom nr$, or $(r+1)binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
add a comment |
$begingroup$
There are several generating function approaches.
We could take the generating function of both sides with respect to $r$, and try to prove that
$$
sum_{r ge 0} left(n binom nrright) x^r = sum_{r ge 0} left((r+1) binom{n}{r+1} + r binom nrright)x^r.
$$
To prove this, we want closed forms for both sides, which start with the generating function
$$
(1+x)^n = sum_{r ge 0} binom nr x^r.
$$
On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.
We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.
Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with
$$
sum_{n ge 0} sum_{rge 0} binom nr x^r y^n = sum_{n ge 0}(1+x)^n y^n = frac{1}{1-(1+x)y}.
$$
Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n binom nr$, or $r binom nr$, or $(r+1)binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
add a comment |
$begingroup$
There are several generating function approaches.
We could take the generating function of both sides with respect to $r$, and try to prove that
$$
sum_{r ge 0} left(n binom nrright) x^r = sum_{r ge 0} left((r+1) binom{n}{r+1} + r binom nrright)x^r.
$$
To prove this, we want closed forms for both sides, which start with the generating function
$$
(1+x)^n = sum_{r ge 0} binom nr x^r.
$$
On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.
We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.
Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with
$$
sum_{n ge 0} sum_{rge 0} binom nr x^r y^n = sum_{n ge 0}(1+x)^n y^n = frac{1}{1-(1+x)y}.
$$
Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n binom nr$, or $r binom nr$, or $(r+1)binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
There are several generating function approaches.
We could take the generating function of both sides with respect to $r$, and try to prove that
$$
sum_{r ge 0} left(n binom nrright) x^r = sum_{r ge 0} left((r+1) binom{n}{r+1} + r binom nrright)x^r.
$$
To prove this, we want closed forms for both sides, which start with the generating function
$$
(1+x)^n = sum_{r ge 0} binom nr x^r.
$$
On the left, this generating function is only multiplied by a constant (independent of $r$); on the right, the $r^{text{th}}$ term of the sum is multiplied by $r$, which requires taking some derivatives.
We could theoretically also take the generating function of both sides with respect to $n$, but that generating function doesn't have a nice closed form.
Finally, we could take the bivariate generating function of both sides with respect to $r$ and $n$. This requires starting with
$$
sum_{n ge 0} sum_{rge 0} binom nr x^r y^n = sum_{n ge 0}(1+x)^n y^n = frac{1}{1-(1+x)y}.
$$
Then we need to take some derivatives with respect to $x$ or with respect to $y$ to transform this into the generating function for $n binom nr$, or $r binom nr$, or $(r+1)binom n{r+1}$. Once we've done that, we can prove the identity you want by proving that it holds for the corresponding generating functions.
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 14 at 3:33
Misha LavrovMisha Lavrov
46.3k656107
46.3k656107
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%2f3072810%2fis-there-some-way-to-prove-n-binom-nr-r1-binom-nr1r-binom-nr-using-gene%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
