Mixing
Combinatorial proof of Negative Binomial Identity
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof.
I am eager to learna similar argument for the proof of negative binomial series: $$(1+x)^-n= sum_k=0^infty (-1)^k binomn+k-1k x^k.$$
I found that the quantity $binomn+k-1k$ has the combinatorial interpretation that "the number of ways to distributing $k$ indistinguishable balls into $n$ distinguishable boxes without any restriction."
I tried to use that fact, but could not find the right trick. Do any of you know a way to go through this?
combinatorics permutations binomial-coefficients binomial-theorem
asked Jul 18 at 19:22
Bumblebee
9,33812449
add a comment |Â
up vote
4
down vote
favorite
For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof.
I am eager to learna similar argument for the proof of negative binomial series: $$(1+x)^-n= sum_k=0^infty (-1)^k binomn+k-1k x^k.$$
I found that the quantity $binomn+k-1k$ has the combinatorial interpretation that "the number of ways to distributing $k$ indistinguishable balls into $n$ distinguishable boxes without any restriction."
I tried to use that fact, but could not find the right trick. Do any of you know a way to go through this?
combinatorics permutations binomial-coefficients binomial-theorem
asked Jul 18 at 19:22
Bumblebee
9,33812449
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof.
I am eager to learna similar argument for the proof of negative binomial series: $$(1+x)^-n= sum_k=0^infty (-1)^k binomn+k-1k x^k.$$
I found that the quantity $binomn+k-1k$ has the combinatorial interpretation that "the number of ways to distributing $k$ indistinguishable balls into $n$ distinguishable boxes without any restriction."
I tried to use that fact, but could not find the right trick. Do any of you know a way to go through this?
combinatorics permutations binomial-coefficients binomial-theorem
asked Jul 18 at 19:22
Bumblebee
9,33812449
For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof.
I am eager to learna similar argument for the proof of negative binomial series: $$(1+x)^-n= sum_k=0^infty (-1)^k binomn+k-1k x^k.$$
I found that the quantity $binomn+k-1k$ has the combinatorial interpretation that "the number of ways to distributing $k$ indistinguishable balls into $n$ distinguishable boxes without any restriction."
I tried to use that fact, but could not find the right trick. Do any of you know a way to go through this?
combinatorics permutations binomial-coefficients binomial-theorem
asked Jul 18 at 19:22
Bumblebee
9,33812449
edited Jul 18 at 19:34
asked Jul 18 at 19:22
Bumblebee
9,33812449
asked Jul 18 at 19:22
Bumblebee
9,33812449
asked Jul 18 at 19:22
Bumblebee
9,33812449
9,33812449
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34
add a comment |Â
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
down vote
accepted
$binomn+k-1k$ is the number of ways to place $k$ indistinguishable into $n$ boxes. Consider $k$ stars
begineqnarray*
underbrace** cdots *_ k text stars
endeqnarray*
insert $n-1$ bars to form $n$ boxes
begineqnarray*
underbrace** _ k_1 text stars mid underbrace*** _ k_2 text stars mid cdots mid underbrace*_ k_n text stars \
sum_i=1^n k_i=k.
endeqnarray*
This is the same as picking the terms from
begineqnarray*
(1+x+cdots+x^k_1+cdots) (1+x+cdots+x^k_2+cdots) cdots (1+x+cdots+x^k_n+cdots)
endeqnarray*
So
begineqnarray*
frac1(1-x)^n =sum_k=0^infty binomn+k-1k x^k .
endeqnarray*
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
add a comment |Â
up vote
1
down vote
Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x mapsto -x$ substitution and call it a day.
Interpret the left hand side as $$(1+x)^-n = (1 - x+x^2 - x^3 + cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^k$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^textnumber of odd integers in our way$. More precisely, the coefficient of $x^k$ is $$sum_a_1 + a_2 + cdots + a_n = k, a_i ge 0 (-1)^textnumber of a_i's text that are odd$$ But this is precisely $$#n-texttuples with even number of odds-#n-texttuples with odd number of odds$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k #n-texttuples adding to k = (-1)^k binomn+k-1k$$
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
$binomn+k-1k$ is the number of ways to place $k$ indistinguishable into $n$ boxes. Consider $k$ stars
begineqnarray*
underbrace** cdots *_ k text stars
endeqnarray*
insert $n-1$ bars to form $n$ boxes
begineqnarray*
underbrace** _ k_1 text stars mid underbrace*** _ k_2 text stars mid cdots mid underbrace*_ k_n text stars \
sum_i=1^n k_i=k.
endeqnarray*
This is the same as picking the terms from
begineqnarray*
(1+x+cdots+x^k_1+cdots) (1+x+cdots+x^k_2+cdots) cdots (1+x+cdots+x^k_n+cdots)
endeqnarray*
So
begineqnarray*
frac1(1-x)^n =sum_k=0^infty binomn+k-1k x^k .
endeqnarray*
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
add a comment |Â
up vote
5
down vote
accepted
$binomn+k-1k$ is the number of ways to place $k$ indistinguishable into $n$ boxes. Consider $k$ stars
begineqnarray*
underbrace** cdots *_ k text stars
endeqnarray*
insert $n-1$ bars to form $n$ boxes
begineqnarray*
underbrace** _ k_1 text stars mid underbrace*** _ k_2 text stars mid cdots mid underbrace*_ k_n text stars \
sum_i=1^n k_i=k.
endeqnarray*
This is the same as picking the terms from
begineqnarray*
(1+x+cdots+x^k_1+cdots) (1+x+cdots+x^k_2+cdots) cdots (1+x+cdots+x^k_n+cdots)
endeqnarray*
So
begineqnarray*
frac1(1-x)^n =sum_k=0^infty binomn+k-1k x^k .
endeqnarray*
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
$binomn+k-1k$ is the number of ways to place $k$ indistinguishable into $n$ boxes. Consider $k$ stars
begineqnarray*
underbrace** cdots *_ k text stars
endeqnarray*
insert $n-1$ bars to form $n$ boxes
begineqnarray*
underbrace** _ k_1 text stars mid underbrace*** _ k_2 text stars mid cdots mid underbrace*_ k_n text stars \
sum_i=1^n k_i=k.
endeqnarray*
This is the same as picking the terms from
begineqnarray*
(1+x+cdots+x^k_1+cdots) (1+x+cdots+x^k_2+cdots) cdots (1+x+cdots+x^k_n+cdots)
endeqnarray*
So
begineqnarray*
frac1(1-x)^n =sum_k=0^infty binomn+k-1k x^k .
endeqnarray*
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
$binomn+k-1k$ is the number of ways to place $k$ indistinguishable into $n$ boxes. Consider $k$ stars
begineqnarray*
underbrace** cdots *_ k text stars
endeqnarray*
insert $n-1$ bars to form $n$ boxes
begineqnarray*
underbrace** _ k_1 text stars mid underbrace*** _ k_2 text stars mid cdots mid underbrace*_ k_n text stars \
sum_i=1^n k_i=k.
endeqnarray*
This is the same as picking the terms from
begineqnarray*
(1+x+cdots+x^k_1+cdots) (1+x+cdots+x^k_2+cdots) cdots (1+x+cdots+x^k_n+cdots)
endeqnarray*
So
begineqnarray*
frac1(1-x)^n =sum_k=0^infty binomn+k-1k x^k .
endeqnarray*
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
edited Jul 18 at 19:40
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
answered Jul 18 at 19:37
Donald Splutterwit
21.3k21243
21.3k21243
add a comment |Â
add a comment |Â
up vote
1
down vote
Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x mapsto -x$ substitution and call it a day.
Interpret the left hand side as $$(1+x)^-n = (1 - x+x^2 - x^3 + cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^k$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^textnumber of odd integers in our way$. More precisely, the coefficient of $x^k$ is $$sum_a_1 + a_2 + cdots + a_n = k, a_i ge 0 (-1)^textnumber of a_i's text that are odd$$ But this is precisely $$#n-texttuples with even number of odds-#n-texttuples with odd number of odds$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k #n-texttuples adding to k = (-1)^k binomn+k-1k$$
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
add a comment |Â
up vote
1
down vote
Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x mapsto -x$ substitution and call it a day.
Interpret the left hand side as $$(1+x)^-n = (1 - x+x^2 - x^3 + cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^k$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^textnumber of odd integers in our way$. More precisely, the coefficient of $x^k$ is $$sum_a_1 + a_2 + cdots + a_n = k, a_i ge 0 (-1)^textnumber of a_i's text that are odd$$ But this is precisely $$#n-texttuples with even number of odds-#n-texttuples with odd number of odds$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k #n-texttuples adding to k = (-1)^k binomn+k-1k$$
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x mapsto -x$ substitution and call it a day.
Interpret the left hand side as $$(1+x)^-n = (1 - x+x^2 - x^3 + cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^k$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^textnumber of odd integers in our way$. More precisely, the coefficient of $x^k$ is $$sum_a_1 + a_2 + cdots + a_n = k, a_i ge 0 (-1)^textnumber of a_i's text that are odd$$ But this is precisely $$#n-texttuples with even number of odds-#n-texttuples with odd number of odds$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k #n-texttuples adding to k = (-1)^k binomn+k-1k$$
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
Here is the same solution, but painfully obfuscated by childishly refusing to just make the $x mapsto -x$ substitution and call it a day.
Interpret the left hand side as $$(1+x)^-n = (1 - x+x^2 - x^3 + cdots)^n$$ When expanding this product out, we choose one monomial $x^j$ from each of the $n$ factors; if $j$ is even, this comes with a $+$ sign, and if $j$ is odd, this comes with a $-$ sign. Thus, the coefficient of $x^k$ in the expanded product is the number of ways to write $k$ as a sum of $n$ nonnegative integers, where each way is weighted by $(-1)^textnumber of odd integers in our way$. More precisely, the coefficient of $x^k$ is $$sum_a_1 + a_2 + cdots + a_n = k, a_i ge 0 (-1)^textnumber of a_i's text that are odd$$ But this is precisely $$#n-texttuples with even number of odds-#n-texttuples with odd number of odds$$ Finally, note that $k$ is even iff there are an even number of odds among the $a_i$'s. Thus, the number is just $$(-1)^k #n-texttuples adding to k = (-1)^k binomn+k-1k$$
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
edited Jul 18 at 20:25
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
answered Jul 18 at 19:55
Sameer Kailasa
5,32121743
5,32121743
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855911%2fcombinatorial-proof-of-negative-binomial-identity%23new-answer', 'question_page');
);
Post as a guest
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
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
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
There's a combinatorial proof for the formal power series. By writing $|x|lt1$, you're making this about the convergence of actual power series, which is a whole different question and seems unlikely to be susceptible to combinatorial proofs. Would a combinatorial proof for the formal power series be good enough?
– joriki
Jul 18 at 19:32
@joriki: That would be more than fantastic. I'll remove the convergent condition to make this much better as you suggested.
– Bumblebee
Jul 18 at 19:34