Mixing
Proof of $sum_{k=0}^m binom{n}{k}(-1)^k = (-1)^m binom{n-1}{m}$ for $n > m geq 0$
$begingroup$
Let $n > m geq 0$ be integers.
How can one prove the following equation?
$$sum_{k=0}^m binom{n}{k}(-1)^k = (-1)^m binom{n-1}{m}$$
According to our script we have to use the following: $(X setminus { n }) cup ({n} setminus X)$ and the following sets:
$G$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is even.
$U$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is odd.
I wasn't able to find a proof for this equation on stackexchange Math, nor was I able to find it on Google and I also don't know how to use the equation above to prove the following inequalities for an even $m$:
$$sum_{j=1}^{m} (-1)^{j+1} sum_{|I| = j} |A_I| leq left| bigcup_{i=1}^n A_i right| leq sum_{j=1}^{m+1} (-1)^{j+1} sum_{|I| = j} |A_I|$$
combinatorics summation proof-writing binomial-coefficients
edited Jan 11 at 10:27
darij grinberg
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
$endgroup$
add a comment |
$begingroup$
Let $n > m geq 0$ be integers.
How can one prove the following equation?
$$sum_{k=0}^m binom{n}{k}(-1)^k = (-1)^m binom{n-1}{m}$$
According to our script we have to use the following: $(X setminus { n }) cup ({n} setminus X)$ and the following sets:
$G$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is even.
$U$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is odd.
I wasn't able to find a proof for this equation on stackexchange Math, nor was I able to find it on Google and I also don't know how to use the equation above to prove the following inequalities for an even $m$:
$$sum_{j=1}^{m} (-1)^{j+1} sum_{|I| = j} |A_I| leq left| bigcup_{i=1}^n A_i right| leq sum_{j=1}^{m+1} (-1)^{j+1} sum_{|I| = j} |A_I|$$
combinatorics summation proof-writing binomial-coefficients
edited Jan 11 at 10:27
darij grinberg
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
$endgroup$
add a comment |
$begingroup$
Let $n > m geq 0$ be integers.
How can one prove the following equation?
$$sum_{k=0}^m binom{n}{k}(-1)^k = (-1)^m binom{n-1}{m}$$
According to our script we have to use the following: $(X setminus { n }) cup ({n} setminus X)$ and the following sets:
$G$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is even.
$U$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is odd.
I wasn't able to find a proof for this equation on stackexchange Math, nor was I able to find it on Google and I also don't know how to use the equation above to prove the following inequalities for an even $m$:
$$sum_{j=1}^{m} (-1)^{j+1} sum_{|I| = j} |A_I| leq left| bigcup_{i=1}^n A_i right| leq sum_{j=1}^{m+1} (-1)^{j+1} sum_{|I| = j} |A_I|$$
combinatorics summation proof-writing binomial-coefficients
edited Jan 11 at 10:27
darij grinberg
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
$endgroup$
Let $n > m geq 0$ be integers.
How can one prove the following equation?
$$sum_{k=0}^m binom{n}{k}(-1)^k = (-1)^m binom{n-1}{m}$$
According to our script we have to use the following: $(X setminus { n }) cup ({n} setminus X)$ and the following sets:
$G$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is even.
$U$ is the set of subsets ${a_1,...,a_k}$ of $[n]$ where $k leq m$ is odd.
I wasn't able to find a proof for this equation on stackexchange Math, nor was I able to find it on Google and I also don't know how to use the equation above to prove the following inequalities for an even $m$:
$$sum_{j=1}^{m} (-1)^{j+1} sum_{|I| = j} |A_I| leq left| bigcup_{i=1}^n A_i right| leq sum_{j=1}^{m+1} (-1)^{j+1} sum_{|I| = j} |A_I|$$
combinatorics summation proof-writing binomial-coefficients
combinatorics summation proof-writing binomial-coefficients
edited Jan 11 at 10:27
darij grinberg
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
edited Jan 11 at 10:27
darij grinberg
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
edited Jan 11 at 10:27
darij grinberg
10.9k33162
edited Jan 11 at 10:27
darij grinberg
10.9k33162
edited Jan 11 at 10:27
darij grinberg
10.9k33162
10.9k33162
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
asked Jan 11 at 6:36
NotEinsteinNotEinstein
1844
1844
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).
As for the inequality: I assume that your $A_1, A_2, ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $bigcaplimits_{i in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = bigcuplimits_{i in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
geq
0
geq
sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
end{equation}
(here, I have subtracted your inequality from $left|Sright|$).
In other words, you want to prove that for each nonnegative integer $k$, the number
$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$
has the same sign as $left(-1right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s in S$, let $cleft(sright)$ denote the number of $i in left{1,2,ldots,nright}$ satisfying $s in A_i$ (in other words, it counts how many of your sets contain $s$). Then,
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
= sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright|
= left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 1}{m}
end{equation}
(by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $left(-1right)^m$, because each of the binomial coefficients $dbinom{cleft(sright) - 1}{m}$ is nonnegative (indeed, each $s in S$ satisfies $cleft(sright) geq 1$ and thus $cleft(sright) - 1 geq 0$). Hence, the left hand side must have the same sign as $left(-1right)^m$ as well. This proves the claim. Let me know if you need more hints.
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
$endgroup$
add a comment |
$begingroup$
Rewrite $binom nk$ to $binom{n-1}{k-1}+binom{n-1}k$, and your sum will telescope.
answered Jan 11 at 7:48
ArthurArthur
114k7115197
$endgroup$
add a comment |
$begingroup$
Answer based on your hint: Suppose that a subset $X$ of $[n]={1,2,ldots,n}$ is given. Then for each $X$, we can define $X'$ as $X' = Xcup{n}$ if $nnotin X$ or $X'=Xsetminus {n}$ if $nin X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'={X';|;Xin S}$.
Now, the given equation is equivalent to
$$
sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle m}binom{n}{j}=|I_1|-|I_2|=(-1)^m binom{n-1}{m}.
$$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Yne X'$ for all $X$. Since $Y'ne X''=X$ for all $Xin I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $nnotin Y$ and $|Y|=m$. The number of such $Y$ is $binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1setminus I_2'$ is the set of all $X$ for which $Xne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $nnotin X$. The number of such $X$ is equal to $binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$ for even $m$ case.
answered Jan 11 at 9:07
SongSong
12k629
$endgroup$
add a comment |
$begingroup$
There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of ${1,2,dots,m}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.
For each set $S$ which does not contain $1$, pair it with the set $Scup {1}$. Note that the sizes of $S$ and $Scup {1}$ have opposite parities, so they cancel each other in your sum and can be ignored.
Which sets are not paired with anything? The only reason $Scup {1}$ would not exist was if $|S|=m$, in which case $Scup {1}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^mbinom{n-1}m$.
To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $sum_{j=1}^m (-1)^{j+1} sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $jle m$, there are $binom{k}{j}$ ways to choose $I$ so that $|I|le m$ and $xin A_I$. Therefore, the element $x$ is counted
$$
sum_{j=1}^{min(k,m)}(-1)^{j+1}binom{k}{j}=binom{k}0+sum_{j=0}^{min(k,m)}(-1)^{j+1}binom{k}{j}=1-(-1)^{min(k,m)}binom{k-1}{min(k,m)}
$$
Note that if $k=0$, then $x$ is counted $1-(-1)^0binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $mge k>0$, then $x$ is counted once in $bigcup_i A_i$, so $1-(-1)^kbinom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
$endgroup$
add a comment |
$begingroup$
$$displaystyle sum^{m}_{k=0}(-1)^{k}cdot binom{n}{k}=$$
Coeff. of $x^{m}$ in
$$bigg[binom{n}{0}-binom{n}{1}x+cdots +(-1)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$
Coeff. of $x^{m}$ in $displaystyle (1-x)^ncdot bigg(frac{1-x^{m+1}}{1-x}bigg).$
Coeff. of $x^{m}$ in $(1-x)^{n-1}cdot (1-x^{m+1}).$
So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ displaystyle = (-1)^{m}cdot binom{n-1}{m}.$
edited Jan 11 at 7:44
Arthur
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
$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%2f3069537%2fproof-of-sum-k-0m-binomnk-1k-1m-binomn-1m-for-n-m-g%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).
As for the inequality: I assume that your $A_1, A_2, ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $bigcaplimits_{i in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = bigcuplimits_{i in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
geq
0
geq
sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
end{equation}
(here, I have subtracted your inequality from $left|Sright|$).
In other words, you want to prove that for each nonnegative integer $k$, the number
$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$
has the same sign as $left(-1right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s in S$, let $cleft(sright)$ denote the number of $i in left{1,2,ldots,nright}$ satisfying $s in A_i$ (in other words, it counts how many of your sets contain $s$). Then,
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
= sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright|
= left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 1}{m}
end{equation}
(by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $left(-1right)^m$, because each of the binomial coefficients $dbinom{cleft(sright) - 1}{m}$ is nonnegative (indeed, each $s in S$ satisfies $cleft(sright) geq 1$ and thus $cleft(sright) - 1 geq 0$). Hence, the left hand side must have the same sign as $left(-1right)^m$ as well. This proves the claim. Let me know if you need more hints.
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
$endgroup$
add a comment |
$begingroup$
As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).
As for the inequality: I assume that your $A_1, A_2, ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $bigcaplimits_{i in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = bigcuplimits_{i in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
geq
0
geq
sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
end{equation}
(here, I have subtracted your inequality from $left|Sright|$).
In other words, you want to prove that for each nonnegative integer $k$, the number
$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$
has the same sign as $left(-1right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s in S$, let $cleft(sright)$ denote the number of $i in left{1,2,ldots,nright}$ satisfying $s in A_i$ (in other words, it counts how many of your sets contain $s$). Then,
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
= sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright|
= left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 1}{m}
end{equation}
(by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $left(-1right)^m$, because each of the binomial coefficients $dbinom{cleft(sright) - 1}{m}$ is nonnegative (indeed, each $s in S$ satisfies $cleft(sright) geq 1$ and thus $cleft(sright) - 1 geq 0$). Hence, the left hand side must have the same sign as $left(-1right)^m$ as well. This proves the claim. Let me know if you need more hints.
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
$endgroup$
add a comment |
$begingroup$
As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).
As for the inequality: I assume that your $A_1, A_2, ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $bigcaplimits_{i in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = bigcuplimits_{i in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
geq
0
geq
sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
end{equation}
(here, I have subtracted your inequality from $left|Sright|$).
In other words, you want to prove that for each nonnegative integer $k$, the number
$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$
has the same sign as $left(-1right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s in S$, let $cleft(sright)$ denote the number of $i in left{1,2,ldots,nright}$ satisfying $s in A_i$ (in other words, it counts how many of your sets contain $s$). Then,
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
= sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright|
= left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 1}{m}
end{equation}
(by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $left(-1right)^m$, because each of the binomial coefficients $dbinom{cleft(sright) - 1}{m}$ is nonnegative (indeed, each $s in S$ satisfies $cleft(sright) geq 1$ and thus $cleft(sright) - 1 geq 0$). Hence, the left hand side must have the same sign as $left(-1right)^m$ as well. This proves the claim. Let me know if you need more hints.
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
$endgroup$
As for the equation: This is a well-known fact which I think deserves a name ("alternating hockey-stick identity"?). I give three proofs in UMN Fall 2018 Math 5705 homework set #2 (Exercise 4).
As for the inequality: I assume that your $A_1, A_2, ldots, A_n$ are $n$ finite sets, and that your $A_I$ means $bigcaplimits_{i in I} A_i$. Then, your inequality is the famous Bonferroni inequality. Let me give a hint to the proof. First of all, let $S = bigcuplimits_{i in I} A_i$ (so that all $A_i$ are subsets of $S$). Then, your inequality becomes
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
geq
0
geq
sum_{j=0}^{m+1} left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
end{equation}
(here, I have subtracted your inequality from $left|Sright|$).
In other words, you want to prove that for each nonnegative integer $k$, the number
$sum_{j=0}^k left(-1right)^j sum_{left|Iright| = j} left|A_Iright|$
has the same sign as $left(-1right)^k$ (that is, it is nonnegative when $k$ is even, and it is nonpositive when $k$ is odd). To do so, let us define one more notation: For each $s in S$, let $cleft(sright)$ denote the number of $i in left{1,2,ldots,nright}$ satisfying $s in A_i$ (in other words, it counts how many of your sets contain $s$). Then,
begin{equation}
sum_{j=0}^m left(-1right)^j sum_{left|Iright| = j} left|A_Iright|
= sum_{left|Iright| leq m} left(-1right)^{left|Iright|} left|A_Iright|
= left(-1right)^m sum_{s in S} dbinom{cleft(sright) - 1}{m}
end{equation}
(by Theorem 3.45 in my Notes on the combinatorial fundamentals of algebra, version of 10th of January 2019, but you can prove this yourself -- this is where the preceding equation is helpful). The right hand side of this equality has the same sign as $left(-1right)^m$, because each of the binomial coefficients $dbinom{cleft(sright) - 1}{m}$ is nonnegative (indeed, each $s in S$ satisfies $cleft(sright) geq 1$ and thus $cleft(sright) - 1 geq 0$). Hence, the left hand side must have the same sign as $left(-1right)^m$ as well. This proves the claim. Let me know if you need more hints.
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
answered Jan 11 at 10:37
darij grinbergdarij grinberg
10.9k33162
10.9k33162
add a comment |
add a comment |
$begingroup$
Rewrite $binom nk$ to $binom{n-1}{k-1}+binom{n-1}k$, and your sum will telescope.
answered Jan 11 at 7:48
ArthurArthur
114k7115197
$endgroup$
add a comment |
$begingroup$
Rewrite $binom nk$ to $binom{n-1}{k-1}+binom{n-1}k$, and your sum will telescope.
answered Jan 11 at 7:48
ArthurArthur
114k7115197
$endgroup$
add a comment |
$begingroup$
Rewrite $binom nk$ to $binom{n-1}{k-1}+binom{n-1}k$, and your sum will telescope.
answered Jan 11 at 7:48
ArthurArthur
114k7115197
$endgroup$
Rewrite $binom nk$ to $binom{n-1}{k-1}+binom{n-1}k$, and your sum will telescope.
answered Jan 11 at 7:48
ArthurArthur
114k7115197
answered Jan 11 at 7:48
ArthurArthur
114k7115197
answered Jan 11 at 7:48
ArthurArthur
114k7115197
answered Jan 11 at 7:48
ArthurArthur
114k7115197
114k7115197
add a comment |
add a comment |
$begingroup$
Answer based on your hint: Suppose that a subset $X$ of $[n]={1,2,ldots,n}$ is given. Then for each $X$, we can define $X'$ as $X' = Xcup{n}$ if $nnotin X$ or $X'=Xsetminus {n}$ if $nin X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'={X';|;Xin S}$.
Now, the given equation is equivalent to
$$
sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle m}binom{n}{j}=|I_1|-|I_2|=(-1)^m binom{n-1}{m}.
$$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Yne X'$ for all $X$. Since $Y'ne X''=X$ for all $Xin I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $nnotin Y$ and $|Y|=m$. The number of such $Y$ is $binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1setminus I_2'$ is the set of all $X$ for which $Xne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $nnotin X$. The number of such $X$ is equal to $binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$ for even $m$ case.
answered Jan 11 at 9:07
SongSong
12k629
$endgroup$
add a comment |
$begingroup$
Answer based on your hint: Suppose that a subset $X$ of $[n]={1,2,ldots,n}$ is given. Then for each $X$, we can define $X'$ as $X' = Xcup{n}$ if $nnotin X$ or $X'=Xsetminus {n}$ if $nin X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'={X';|;Xin S}$.
Now, the given equation is equivalent to
$$
sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle m}binom{n}{j}=|I_1|-|I_2|=(-1)^m binom{n-1}{m}.
$$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Yne X'$ for all $X$. Since $Y'ne X''=X$ for all $Xin I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $nnotin Y$ and $|Y|=m$. The number of such $Y$ is $binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1setminus I_2'$ is the set of all $X$ for which $Xne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $nnotin X$. The number of such $X$ is equal to $binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$ for even $m$ case.
answered Jan 11 at 9:07
SongSong
12k629
$endgroup$
add a comment |
$begingroup$
Answer based on your hint: Suppose that a subset $X$ of $[n]={1,2,ldots,n}$ is given. Then for each $X$, we can define $X'$ as $X' = Xcup{n}$ if $nnotin X$ or $X'=Xsetminus {n}$ if $nin X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'={X';|;Xin S}$.
Now, the given equation is equivalent to
$$
sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle m}binom{n}{j}=|I_1|-|I_2|=(-1)^m binom{n-1}{m}.
$$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Yne X'$ for all $X$. Since $Y'ne X''=X$ for all $Xin I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $nnotin Y$ and $|Y|=m$. The number of such $Y$ is $binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1setminus I_2'$ is the set of all $X$ for which $Xne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $nnotin X$. The number of such $X$ is equal to $binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$ for even $m$ case.
answered Jan 11 at 9:07
SongSong
12k629
$endgroup$
Answer based on your hint: Suppose that a subset $X$ of $[n]={1,2,ldots,n}$ is given. Then for each $X$, we can define $X'$ as $X' = Xcup{n}$ if $nnotin X$ or $X'=Xsetminus {n}$ if $nin X$. Note that $(X')'=X$ and thus $(X,X')$ partitions the family of all subsets of $[n]$. We denote $S'={X';|;Xin S}$.
Now, the given equation is equivalent to
$$
sum_{jtext{ even},jle m}binom{n}{j}-sum_{jtext{ odd},jle m}binom{n}{j}=|I_1|-|I_2|=(-1)^m binom{n-1}{m}.
$$ Let $I_1$ denotes the set of all $X$ for which $|X|$ is even and $le m$ and $I_2$ the set of all $Y$ for which $|Y|$ is odd and $le m$. We denote by $X$ the member of $I_1$ and by $Y$ that of $I_2$. Since $|I_1|$ is the number of $X$'s, we can count it by counting the corresponding $X'in I_1'$. We can see that $|X'|$ and $|X|$ are different only by $1$, and hence $|X'|$ is odd. Now, suppose that $m$ is odd. Then, since $|X|<m$ (cannot be equal), it holds that $|X'|le m$. So $I_2$ contains $I_1'$ and $|I_1|-|I_2|=-|I_2setminus I_1'|$ corresponds to $(-1)$ times the number of $Y$ such that $Yne X'$ for all $X$. Since $Y'ne X''=X$ for all $Xin I_1$, it is equivalent to $|Y'|=|Y|+1=m+1$ and it follows that $nnotin Y$ and $|Y|=m$. The number of such $Y$ is $binom{n-1}{m}$ and this shows $|I_1|-|I_2| = -binom{n-1}{m}$.
Conversely, suppose $m$ is even. Then, since $|Y|<m$, we must have $|Y'|le m$. This shows $I_1$ contains $I_2'$. And the difference $I_1setminus I_2'$ is the set of all $X$ for which $Xne Y'$ for all $Y$. This is equivalent to $|X'|=|X|+1=m+1$, i.e. $|X|=m$ and $nnotin X$. The number of such $X$ is equal to $binom{n-1}{m}$ and hence this proves $|I_1|-|I_2| =|I_1setminus I_2'|= binom{n-1}{m}$ for even $m$ case.
answered Jan 11 at 9:07
SongSong
12k629
answered Jan 11 at 9:07
SongSong
12k629
answered Jan 11 at 9:07
SongSong
12k629
answered Jan 11 at 9:07
SongSong
12k629
12k629
add a comment |
add a comment |
$begingroup$
There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of ${1,2,dots,m}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.
For each set $S$ which does not contain $1$, pair it with the set $Scup {1}$. Note that the sizes of $S$ and $Scup {1}$ have opposite parities, so they cancel each other in your sum and can be ignored.
Which sets are not paired with anything? The only reason $Scup {1}$ would not exist was if $|S|=m$, in which case $Scup {1}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^mbinom{n-1}m$.
To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $sum_{j=1}^m (-1)^{j+1} sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $jle m$, there are $binom{k}{j}$ ways to choose $I$ so that $|I|le m$ and $xin A_I$. Therefore, the element $x$ is counted
$$
sum_{j=1}^{min(k,m)}(-1)^{j+1}binom{k}{j}=binom{k}0+sum_{j=0}^{min(k,m)}(-1)^{j+1}binom{k}{j}=1-(-1)^{min(k,m)}binom{k-1}{min(k,m)}
$$
Note that if $k=0$, then $x$ is counted $1-(-1)^0binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $mge k>0$, then $x$ is counted once in $bigcup_i A_i$, so $1-(-1)^kbinom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
$endgroup$
add a comment |
$begingroup$
There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of ${1,2,dots,m}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.
For each set $S$ which does not contain $1$, pair it with the set $Scup {1}$. Note that the sizes of $S$ and $Scup {1}$ have opposite parities, so they cancel each other in your sum and can be ignored.
Which sets are not paired with anything? The only reason $Scup {1}$ would not exist was if $|S|=m$, in which case $Scup {1}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^mbinom{n-1}m$.
To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $sum_{j=1}^m (-1)^{j+1} sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $jle m$, there are $binom{k}{j}$ ways to choose $I$ so that $|I|le m$ and $xin A_I$. Therefore, the element $x$ is counted
$$
sum_{j=1}^{min(k,m)}(-1)^{j+1}binom{k}{j}=binom{k}0+sum_{j=0}^{min(k,m)}(-1)^{j+1}binom{k}{j}=1-(-1)^{min(k,m)}binom{k-1}{min(k,m)}
$$
Note that if $k=0$, then $x$ is counted $1-(-1)^0binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $mge k>0$, then $x$ is counted once in $bigcup_i A_i$, so $1-(-1)^kbinom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
$endgroup$
add a comment |
$begingroup$
There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of ${1,2,dots,m}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.
For each set $S$ which does not contain $1$, pair it with the set $Scup {1}$. Note that the sizes of $S$ and $Scup {1}$ have opposite parities, so they cancel each other in your sum and can be ignored.
Which sets are not paired with anything? The only reason $Scup {1}$ would not exist was if $|S|=m$, in which case $Scup {1}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^mbinom{n-1}m$.
To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $sum_{j=1}^m (-1)^{j+1} sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $jle m$, there are $binom{k}{j}$ ways to choose $I$ so that $|I|le m$ and $xin A_I$. Therefore, the element $x$ is counted
$$
sum_{j=1}^{min(k,m)}(-1)^{j+1}binom{k}{j}=binom{k}0+sum_{j=0}^{min(k,m)}(-1)^{j+1}binom{k}{j}=1-(-1)^{min(k,m)}binom{k-1}{min(k,m)}
$$
Note that if $k=0$, then $x$ is counted $1-(-1)^0binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $mge k>0$, then $x$ is counted once in $bigcup_i A_i$, so $1-(-1)^kbinom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
$endgroup$
There is a nice combinatorial proof of this identity using a sign-reversing involution. You summation counts subsets of ${1,2,dots,m}$ of size $m$ or fewer, except subsets with even size are counted positively and those with odd size are counted negatively.
For each set $S$ which does not contain $1$, pair it with the set $Scup {1}$. Note that the sizes of $S$ and $Scup {1}$ have opposite parities, so they cancel each other in your sum and can be ignored.
Which sets are not paired with anything? The only reason $Scup {1}$ would not exist was if $|S|=m$, in which case $Scup {1}$ would be too big and would not be counted. Therefore, the number of unpaired sets is $binom{n-1}m$, and these sets all have parity $(-1)^m$ in your sum, so the sum is $(-1)^mbinom{n-1}m$.
To prove your inequalities, consider the number of times a particular element $x$ is counted in the sum $sum_{j=1}^m (-1)^{j+1} sum_{|I|=j} |A_i|$. Suppose $x$ is contained in $k$ of the sets, $A_i$. As long a $jle m$, there are $binom{k}{j}$ ways to choose $I$ so that $|I|le m$ and $xin A_I$. Therefore, the element $x$ is counted
$$
sum_{j=1}^{min(k,m)}(-1)^{j+1}binom{k}{j}=binom{k}0+sum_{j=0}^{min(k,m)}(-1)^{j+1}binom{k}{j}=1-(-1)^{min(k,m)}binom{k-1}{min(k,m)}
$$
Note that if $k=0$, then $x$ is counted $1-(-1)^0binom{-1}0=0$ times. This is the correct number, since $k=0$ implies $x$ is not in the union of the $A_i$. If $mge k>0$, then $x$ is counted once in $bigcup_i A_i$, so $1-(-1)^kbinom{k-1}{k}=0$ is the correct count for $x$. Otherwise, we have $k>0$ and $k>m$, in which case $x$ is counted once, so $1-(-1)^{m}binom{k-1}{m} $ is either an overestimate or underestimate for the count of $x$, depending on the parity of $m$.
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
edited Jan 12 at 1:03
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
answered Jan 11 at 17:09
Mike EarnestMike Earnest
22.4k12051
22.4k12051
add a comment |
add a comment |
$begingroup$
$$displaystyle sum^{m}_{k=0}(-1)^{k}cdot binom{n}{k}=$$
Coeff. of $x^{m}$ in
$$bigg[binom{n}{0}-binom{n}{1}x+cdots +(-1)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$
Coeff. of $x^{m}$ in $displaystyle (1-x)^ncdot bigg(frac{1-x^{m+1}}{1-x}bigg).$
Coeff. of $x^{m}$ in $(1-x)^{n-1}cdot (1-x^{m+1}).$
So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ displaystyle = (-1)^{m}cdot binom{n-1}{m}.$
edited Jan 11 at 7:44
Arthur
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
$endgroup$
add a comment |
$begingroup$
$$displaystyle sum^{m}_{k=0}(-1)^{k}cdot binom{n}{k}=$$
Coeff. of $x^{m}$ in
$$bigg[binom{n}{0}-binom{n}{1}x+cdots +(-1)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$
Coeff. of $x^{m}$ in $displaystyle (1-x)^ncdot bigg(frac{1-x^{m+1}}{1-x}bigg).$
Coeff. of $x^{m}$ in $(1-x)^{n-1}cdot (1-x^{m+1}).$
So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ displaystyle = (-1)^{m}cdot binom{n-1}{m}.$
edited Jan 11 at 7:44
Arthur
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
$endgroup$
add a comment |
$begingroup$
$$displaystyle sum^{m}_{k=0}(-1)^{k}cdot binom{n}{k}=$$
Coeff. of $x^{m}$ in
$$bigg[binom{n}{0}-binom{n}{1}x+cdots +(-1)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$
Coeff. of $x^{m}$ in $displaystyle (1-x)^ncdot bigg(frac{1-x^{m+1}}{1-x}bigg).$
Coeff. of $x^{m}$ in $(1-x)^{n-1}cdot (1-x^{m+1}).$
So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ displaystyle = (-1)^{m}cdot binom{n-1}{m}.$
edited Jan 11 at 7:44
Arthur
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
$endgroup$
$$displaystyle sum^{m}_{k=0}(-1)^{k}cdot binom{n}{k}=$$
Coeff. of $x^{m}$ in
$$bigg[binom{n}{0}-binom{n}{1}x+cdots +(-1)^nbinom{n}{n}x^n bigg](x^m+x^{m-1}+x^{m-2}+cdots +x+1).$$
Coeff. of $x^{m}$ in $displaystyle (1-x)^ncdot bigg(frac{1-x^{m+1}}{1-x}bigg).$
Coeff. of $x^{m}$ in $(1-x)^{n-1}cdot (1-x^{m+1}).$
So coeff. of $x^{m}$ in $(1-x)^{n-1}$ is $ displaystyle = (-1)^{m}cdot binom{n-1}{m}.$
edited Jan 11 at 7:44
Arthur
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
edited Jan 11 at 7:44
Arthur
114k7115197
edited Jan 11 at 7:44
Arthur
114k7115197
edited Jan 11 at 7:44
Arthur
114k7115197
114k7115197
answered Jan 11 at 7:21
DXTDXT
5,6842630
answered Jan 11 at 7:21
DXTDXT
5,6842630
answered Jan 11 at 7:21
DXTDXT
5,6842630
5,6842630
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%2f3069537%2fproof-of-sum-k-0m-binomnk-1k-1m-binomn-1m-for-n-m-g%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
