Mixing
How to prove binomial coefficient $ {2^n choose k} $ is even number?
$begingroup$
Prove:
${2^n choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.
I have tried induction but was unable to get any useful results.
combinatorics binomial-coefficients
asked Jan 25 at 22:55
SladSlad
155
$endgroup$
add a comment |
$begingroup$
Prove:
${2^n choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.
I have tried induction but was unable to get any useful results.
combinatorics binomial-coefficients
asked Jan 25 at 22:55
SladSlad
155
$endgroup$
1
$begingroup$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09
add a comment |
$begingroup$
Prove:
${2^n choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.
I have tried induction but was unable to get any useful results.
combinatorics binomial-coefficients
asked Jan 25 at 22:55
SladSlad
155
$endgroup$
Prove:
${2^n choose k}$ (for integers $k$ & $n$ : $0<k<2^n$) is even number.
I have tried induction but was unable to get any useful results.
combinatorics binomial-coefficients
combinatorics binomial-coefficients
asked Jan 25 at 22:55
SladSlad
155
asked Jan 25 at 22:55
SladSlad
155
edited Jan 26 at 7:55
Slad
asked Jan 25 at 22:55
SladSlad
155
asked Jan 25 at 22:55
SladSlad
155
asked Jan 25 at 22:55
SladSlad
155
155
1
$begingroup$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09
add a comment |
1
$begingroup$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09
1
1
$begingroup$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09
$begingroup$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09
add a comment |
7 Answers
7
active
oldest
votes
$begingroup$
We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $pmod{2}$, then $(x+1)^{2^n} equiv x^{2^n} + 1 pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = left[(x+1)^{2^n} right]^2 equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 equiv x^{2^{n+1}} + 1 pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = sum_{k=0}^{2^n} binom{2^n}{k} x^k$. Therefore, if $sum_{k=0}^{2^n} binom{2^n}{k} x^k equiv x^{2^n} + 1 pmod{2}$, then by comparing coefficients, we must have $binom{2^n}{k} equiv 0 pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(mathbb{Z} / 2 mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $mathbb{Z} to mathbb{Z}$, then just knowing that $f(n) equiv g(n) pmod{2}$ for every $n in mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $pmod{2}$. For example, $n^2 + n equiv 0 pmod{2}$ for every $n in mathbb{Z}$, yet we do not have $x^2 + x equiv 0 pmod{2}$ formally as a polynomial identity.)
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
$endgroup$
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
add a comment |
$begingroup$
There is a proof by induction using the Vandermonde identity:
$$
binom{2^n}k=sum_{i=0}^k binom{2^{n-1}}ibinom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
$endgroup$
add a comment |
$begingroup$
Provided that you already know $binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$binom{2^n}{k}=frac{(2^n)(2^n-1)cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.
We have $k!=k(k-1)(k-2)cdots 3cdot 2 cdot 1$. At most $frac{k}{2}$ of these numbers are divisible by $2$. At most $frac{k}{4}$ of them are divisible by $4$. At most $frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than
$$frac{k}{2}+frac{k}{4}+frac{k}{8}+cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.
edited Jan 26 at 0:24
darij grinberg
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
$endgroup$
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
add a comment |
$begingroup$
Let $n,k$ be integers, $0lt klt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|binom Sk|=binom{2^n}k$. We show that $binom Sk$ has an even number of elements by defining a fixed-point-free involution $varphi:binom Sktobinom Sk$.
For $iin[n]={1,dots,n}$, let $varphi_i:Sto S$ be the involution which flips the $i^text{th}$ bit; and for $Xinbinom Sk$, let $varphi_i[X]={varphi_i(x):xin X}inbinom Sk$.
If $Xinbinom Sk$, since $emptysetne Xne S$, there is some $iin[n]$ such that $varphi_i[X]ne X$; let $i(X)$ be the least such $i$.
Finally, define $varphi:binom Sktobinom Sk$ by setting $varphi(X)=varphi_{i(X)}[X]$. It is easy to see that $varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0lt klt p^n$.
answered Jan 26 at 11:28
bofbof
52.5k558121
$endgroup$
add a comment |
$begingroup$
The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $mathbb{N}=left{ 0,1,2,ldotsright} $.
Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
$dbinom{n}{m}=dfrac{n}{m}cdotdbinom{n-1}{m-1}$.
Proof of Lemma 1. We have
begin{align*}
dbinom{n}{m} & =dfrac{ncdotleft( n-1right) cdotcdotscdotleft(
n-m+1right) }{m!} left( text{by the definition of
}dbinom{n}{m}right) \
& =dfrac{ncdotleft( left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) right) }{mcdotleft( m-1right)
!}\
& qquadqquadleft(
begin{array}
[c]{c}
text{since}\
ncdotleft( n-1right) cdotcdotscdotleft( n-m+1right) =ncdotleft(
left( n-1right) cdotleft( n-2right) cdotcdotscdotleft(
n-m+1right) right) \
text{and }m!=mcdotleft( m-1right) !
end{array}
right) \
& =dfrac{n}{m}cdotdfrac{left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) }{left( m-1right) !}\
& =dfrac{n}{m}cdotunderbrace{dfrac{left( n-1right) cdotleft(
n-2right) cdotcdotscdotleft( left( n-1right) -left( m-1right)
+1right) }{left( m-1right) !}}_{substack{=dbinom{n-1}{m-1}
\text{(since this is how }dbinom{n-1}{m-1}text{ is defined)}}}\
& qquadqquadleft( text{since }n-m=left( n-1right) -left(
m-1right) right) \
& =dfrac{n}{m}cdotdbinom{n-1}{m-1}.
end{align*}
Thus, Lemma 1 is proven. $blacksquare$
Lemma 2. Let $x$, $y$ and $z$ be three integers such that $xmid yz$ and
$gcdleft( x,yright) =1$. Then, $xmid z$.
Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$blacksquare$
Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
$p^{alpha}$ is a power of $p$.
Proof of Lemma 3. Let $d$ be a positive divisor of $p^{alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $qmid d$
(since the prime factorization of $d$ contains $q$). Hence, $qmid dmid
p^{alpha}$ (since $d$ is a divisor of $p^{alpha}$). Thus, the prime
factorization of $p^{alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $underbrace{ppcdots p}
_{alphatext{ times}}$, we thus conclude that the prime factorization
$underbrace{ppcdots p}_{alphatext{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $blacksquare$
Lemma 4. Let $p$ be a prime number. Let $alphainmathbb{N}$. Let $u$ be
an integer such that $u$ is not divisible by $p$. Then, $gcdleft(
u,p^{alpha}right) =1$.
Proof of Lemma 4. The integer $gcdleft( u,p^{alpha}right) $ is a
positive divisor of $p^{alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $gcdleft( u,p^{alpha}right) =p^{beta}$ for some
$betainmathbb{N}$. Consider this $beta$. If $beta>0$, then $pmid
p^{beta}=gcdleft( u,p^{alpha}right) mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $beta>0$,
and thus we must have $beta=0$. Hence, $p^{beta}=p^{0}=1$ and $gcdleft(
u,p^{alpha}right) =p^{beta}=1$. This proves Lemma 4. $blacksquare$
Theorem 5. Let $p$ be a prime number. Let $alphainmathbb{N}$ and let
$k$ be an integer such that $0<k<p^{alpha}$. Then, $dbinom{p^{alpha}}{k}$
is divisible by $p$.
Your claim follows from Theorem 5 (applied to $p=2$ and $alpha=n$), since your $k$ satisfies $0 < k < n leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $dbinom{p^{alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 3 (applied to $u=dbinom{p^{alpha}}{k}$)
that $gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$.
Applying Lemma 1 to $n=p^{alpha}$ and $m=k$, we obtain $dbinom{p^{alpha}
}{k}=dfrac{p^{alpha}}{k}cdotdbinom{p^{alpha}-1}{k-1}$, so that
$kdbinom{p^{alpha}}{k}=p^{alpha}dbinom{p^{alpha}-1}{k-1}$. Thus,
$p^{alpha}mid kdbinom{p^{alpha}}{k}=dbinom{p^{alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{alpha}$, $y=dbinom{p^{alpha}}{k}$ and $z=k$) yields
$p^{alpha}mid k$ (since $gcdleft( p^{alpha},dbinom{p^{alpha}}
{k}right) =gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$). Since
$k$ is positive, this yields $kgeq p^{alpha}$; but this contradicts
$k<p^{alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $blacksquare$
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
$endgroup$
add a comment |
$begingroup$
The solution is immediate using Lucas's theorem since
$${2^n choose k} = prod_{i=0}^n{m_i choose k_i} mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
answered Jan 26 at 10:33
mbjoembjoe
2361110
$endgroup$
add a comment |
$begingroup$
More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0lt klt p^n$, then the binomial coefficient $binom{p^n}k$ is divisible by $p$.
Let $nu_p(m)$ denote the highest exponent $nu$ such that $p^nu$ divides $m$. Let $h=p^n-k$. Since
$$nu_pleft(binom{p^n}kright)=nu_pleft(frac{p^n!}{h!k!}right)=nu_p(p^n!)-nu_p(h!)-nu_p(k!),$$
it will suffice to show that $nu_p(p^n!)-nu_p(h!)-nu_p(k!)ge1.$
In view of Legendre's formula
$$nu_p(m!)=sum_{i=1}^inftyleftlfloorfrac m{p^i}rightrfloor,$$
this is the same as showing that
$$sum_{i=1}^inftyleft(leftlfloorfrac{p^n}{p^i}rightrfloor-leftlfloorfrac h{p^i}rightrfloor-leftlfloorfrac k{p^i}rightrfloorright)ge1.tag1$$
Now, every term of the series is nonnegative, since $lfloor x+yrfloorgelfloor xrfloor+lfloor yrfloor$ for all real $x,y$.
Since the $i=n$ term is
$$leftlfloorfrac{p^n}{p^n}rightrfloor-leftlfloorfrac h{p^n}rightrfloor-leftlfloorfrac k{p^n}rightrfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
answered Jan 28 at 6:17
bofbof
52.5k558121
$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%2f3087700%2fhow-to-prove-binomial-coefficient-2n-choose-k-is-even-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
7 Answers
7
active
oldest
votes
7 Answers
7
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $pmod{2}$, then $(x+1)^{2^n} equiv x^{2^n} + 1 pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = left[(x+1)^{2^n} right]^2 equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 equiv x^{2^{n+1}} + 1 pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = sum_{k=0}^{2^n} binom{2^n}{k} x^k$. Therefore, if $sum_{k=0}^{2^n} binom{2^n}{k} x^k equiv x^{2^n} + 1 pmod{2}$, then by comparing coefficients, we must have $binom{2^n}{k} equiv 0 pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(mathbb{Z} / 2 mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $mathbb{Z} to mathbb{Z}$, then just knowing that $f(n) equiv g(n) pmod{2}$ for every $n in mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $pmod{2}$. For example, $n^2 + n equiv 0 pmod{2}$ for every $n in mathbb{Z}$, yet we do not have $x^2 + x equiv 0 pmod{2}$ formally as a polynomial identity.)
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
$endgroup$
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
add a comment |
$begingroup$
We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $pmod{2}$, then $(x+1)^{2^n} equiv x^{2^n} + 1 pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = left[(x+1)^{2^n} right]^2 equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 equiv x^{2^{n+1}} + 1 pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = sum_{k=0}^{2^n} binom{2^n}{k} x^k$. Therefore, if $sum_{k=0}^{2^n} binom{2^n}{k} x^k equiv x^{2^n} + 1 pmod{2}$, then by comparing coefficients, we must have $binom{2^n}{k} equiv 0 pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(mathbb{Z} / 2 mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $mathbb{Z} to mathbb{Z}$, then just knowing that $f(n) equiv g(n) pmod{2}$ for every $n in mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $pmod{2}$. For example, $n^2 + n equiv 0 pmod{2}$ for every $n in mathbb{Z}$, yet we do not have $x^2 + x equiv 0 pmod{2}$ formally as a polynomial identity.)
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
$endgroup$
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
add a comment |
$begingroup$
We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $pmod{2}$, then $(x+1)^{2^n} equiv x^{2^n} + 1 pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = left[(x+1)^{2^n} right]^2 equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 equiv x^{2^{n+1}} + 1 pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = sum_{k=0}^{2^n} binom{2^n}{k} x^k$. Therefore, if $sum_{k=0}^{2^n} binom{2^n}{k} x^k equiv x^{2^n} + 1 pmod{2}$, then by comparing coefficients, we must have $binom{2^n}{k} equiv 0 pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(mathbb{Z} / 2 mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $mathbb{Z} to mathbb{Z}$, then just knowing that $f(n) equiv g(n) pmod{2}$ for every $n in mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $pmod{2}$. For example, $n^2 + n equiv 0 pmod{2}$ for every $n in mathbb{Z}$, yet we do not have $x^2 + x equiv 0 pmod{2}$ formally as a polynomial identity.)
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
$endgroup$
We can prove by induction on $n$ that if you treat $(x+1)^{2^n}$ formally as a polynomial in $x$ and reduce each coefficient $pmod{2}$, then $(x+1)^{2^n} equiv x^{2^n} + 1 pmod{2}$. For $n=0$, this is trivial to check. For the inductive step, $(x+1)^{2^{n+1}} = left[(x+1)^{2^n} right]^2 equiv (x^{2^n}+1)^2 = x^{2^{n+1}} + 2 x^{2^n} + 1 equiv x^{2^{n+1}} + 1 pmod{2}$.
On the other hand, by the binomial theorem, $(x+1)^{2^n} = sum_{k=0}^{2^n} binom{2^n}{k} x^k$. Therefore, if $sum_{k=0}^{2^n} binom{2^n}{k} x^k equiv x^{2^n} + 1 pmod{2}$, then by comparing coefficients, we must have $binom{2^n}{k} equiv 0 pmod{2}$ for $0 < k < 2^n$. (And then, since $2^n > n$ for $n ge 0$, this implies the desired result.)
(Note that in this argument, it is important to treat the expressions formally as polynomials - or as elements of $(mathbb{Z} / 2 mathbb{Z})[x]$ if you're familiar with that notation. Otherwise, if we treated them as functions $mathbb{Z} to mathbb{Z}$, then just knowing that $f(n) equiv g(n) pmod{2}$ for every $n in mathbb{Z}$ is not sufficient to conclude that the coefficients of $f$ are congruent to the corresponding coefficients of $g$ $pmod{2}$. For example, $n^2 + n equiv 0 pmod{2}$ for every $n in mathbb{Z}$, yet we do not have $x^2 + x equiv 0 pmod{2}$ formally as a polynomial identity.)
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
answered Jan 25 at 23:21
Daniel ScheplerDaniel Schepler
9,1191721
9,1191721
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
add a comment |
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
$begingroup$
This solution is very closely related to Mike Earnest's solution, in that one common way to prove the Vandermonde identity is to expand both sides of $(1+x)^{m+n} = (1+x)^n (1+x)^m$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:23
add a comment |
$begingroup$
There is a proof by induction using the Vandermonde identity:
$$
binom{2^n}k=sum_{i=0}^k binom{2^{n-1}}ibinom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
$endgroup$
add a comment |
$begingroup$
There is a proof by induction using the Vandermonde identity:
$$
binom{2^n}k=sum_{i=0}^k binom{2^{n-1}}ibinom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
$endgroup$
add a comment |
$begingroup$
There is a proof by induction using the Vandermonde identity:
$$
binom{2^n}k=sum_{i=0}^k binom{2^{n-1}}ibinom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
$endgroup$
There is a proof by induction using the Vandermonde identity:
$$
binom{2^n}k=sum_{i=0}^k binom{2^{n-1}}ibinom{2^{n-1}}{k-i},
$$
You can verify all of the summands are even using the induction hypothesis, as long as $n>1$. You then just need the base case $n=1$.
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
answered Jan 25 at 23:20
Mike EarnestMike Earnest
25.4k22151
25.4k22151
add a comment |
add a comment |
$begingroup$
Provided that you already know $binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$binom{2^n}{k}=frac{(2^n)(2^n-1)cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.
We have $k!=k(k-1)(k-2)cdots 3cdot 2 cdot 1$. At most $frac{k}{2}$ of these numbers are divisible by $2$. At most $frac{k}{4}$ of them are divisible by $4$. At most $frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than
$$frac{k}{2}+frac{k}{4}+frac{k}{8}+cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.
edited Jan 26 at 0:24
darij grinberg
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
$endgroup$
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
add a comment |
$begingroup$
Provided that you already know $binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$binom{2^n}{k}=frac{(2^n)(2^n-1)cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.
We have $k!=k(k-1)(k-2)cdots 3cdot 2 cdot 1$. At most $frac{k}{2}$ of these numbers are divisible by $2$. At most $frac{k}{4}$ of them are divisible by $4$. At most $frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than
$$frac{k}{2}+frac{k}{4}+frac{k}{8}+cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.
edited Jan 26 at 0:24
darij grinberg
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
$endgroup$
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
add a comment |
$begingroup$
Provided that you already know $binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$binom{2^n}{k}=frac{(2^n)(2^n-1)cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.
We have $k!=k(k-1)(k-2)cdots 3cdot 2 cdot 1$. At most $frac{k}{2}$ of these numbers are divisible by $2$. At most $frac{k}{4}$ of them are divisible by $4$. At most $frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than
$$frac{k}{2}+frac{k}{4}+frac{k}{8}+cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.
edited Jan 26 at 0:24
darij grinberg
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
$endgroup$
Provided that you already know $binom{2^n}{k}$ is an integer, it suffices to show the numerator has more factors of $2$ than the denominator. We have:
$$binom{2^n}{k}=frac{(2^n)(2^n-1)cdots(2^n-k+1)}{k!}.$$
There are at least $n$ factors of $2$ in the numerator because $2^n$ is a factor. So now we need to count the number of factors of $2$ in the denominator, $k!$.
We have $k!=k(k-1)(k-2)cdots 3cdot 2 cdot 1$. At most $frac{k}{2}$ of these numbers are divisible by $2$. At most $frac{k}{4}$ of them are divisible by $4$. At most $frac{k}{8}$ of them are divisible by $8$. And so on. Each number that is divisible by $2$ contributes a factor of $2$, each number that is divisible by $4$ contributes an additional factor of $2$, each number that is divisible by $8$ contributes a third factor of $2$, and so on. So the number of factors of $2$ in $k!$ is no more than
$$frac{k}{2}+frac{k}{4}+frac{k}{8}+cdots = k.$$
Since $k<n$, the denominator has strictly fewer factors of $2$ than the numerator.
edited Jan 26 at 0:24
darij grinberg
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
edited Jan 26 at 0:24
darij grinberg
11.2k33167
edited Jan 26 at 0:24
darij grinberg
11.2k33167
edited Jan 26 at 0:24
darij grinberg
11.2k33167
11.2k33167
answered Jan 25 at 23:10
kccukccu
10.6k11229
answered Jan 25 at 23:10
kccukccu
10.6k11229
answered Jan 25 at 23:10
kccukccu
10.6k11229
10.6k11229
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
add a comment |
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
$begingroup$
Ah, a proof that actually does use the $k < n$ condition :P
$endgroup$
– darij grinberg
Jan 26 at 0:25
1
1
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
$begingroup$
This post refers to an old version of the question, where the condition was $k < n$ rather than $k < 2^n$.
$endgroup$
– darij grinberg
Feb 10 at 3:30
add a comment |
$begingroup$
Let $n,k$ be integers, $0lt klt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|binom Sk|=binom{2^n}k$. We show that $binom Sk$ has an even number of elements by defining a fixed-point-free involution $varphi:binom Sktobinom Sk$.
For $iin[n]={1,dots,n}$, let $varphi_i:Sto S$ be the involution which flips the $i^text{th}$ bit; and for $Xinbinom Sk$, let $varphi_i[X]={varphi_i(x):xin X}inbinom Sk$.
If $Xinbinom Sk$, since $emptysetne Xne S$, there is some $iin[n]$ such that $varphi_i[X]ne X$; let $i(X)$ be the least such $i$.
Finally, define $varphi:binom Sktobinom Sk$ by setting $varphi(X)=varphi_{i(X)}[X]$. It is easy to see that $varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0lt klt p^n$.
answered Jan 26 at 11:28
bofbof
52.5k558121
$endgroup$
add a comment |
$begingroup$
Let $n,k$ be integers, $0lt klt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|binom Sk|=binom{2^n}k$. We show that $binom Sk$ has an even number of elements by defining a fixed-point-free involution $varphi:binom Sktobinom Sk$.
For $iin[n]={1,dots,n}$, let $varphi_i:Sto S$ be the involution which flips the $i^text{th}$ bit; and for $Xinbinom Sk$, let $varphi_i[X]={varphi_i(x):xin X}inbinom Sk$.
If $Xinbinom Sk$, since $emptysetne Xne S$, there is some $iin[n]$ such that $varphi_i[X]ne X$; let $i(X)$ be the least such $i$.
Finally, define $varphi:binom Sktobinom Sk$ by setting $varphi(X)=varphi_{i(X)}[X]$. It is easy to see that $varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0lt klt p^n$.
answered Jan 26 at 11:28
bofbof
52.5k558121
$endgroup$
add a comment |
$begingroup$
Let $n,k$ be integers, $0lt klt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|binom Sk|=binom{2^n}k$. We show that $binom Sk$ has an even number of elements by defining a fixed-point-free involution $varphi:binom Sktobinom Sk$.
For $iin[n]={1,dots,n}$, let $varphi_i:Sto S$ be the involution which flips the $i^text{th}$ bit; and for $Xinbinom Sk$, let $varphi_i[X]={varphi_i(x):xin X}inbinom Sk$.
If $Xinbinom Sk$, since $emptysetne Xne S$, there is some $iin[n]$ such that $varphi_i[X]ne X$; let $i(X)$ be the least such $i$.
Finally, define $varphi:binom Sktobinom Sk$ by setting $varphi(X)=varphi_{i(X)}[X]$. It is easy to see that $varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0lt klt p^n$.
answered Jan 26 at 11:28
bofbof
52.5k558121
$endgroup$
Let $n,k$ be integers, $0lt klt2^n$.
Let $S$ be the set of all bitstrings of length $n$, and let $binom Sk$ be the set of all $k$-element subsets of $S$, so that $|S|=2^n$ and $|binom Sk|=binom{2^n}k$. We show that $binom Sk$ has an even number of elements by defining a fixed-point-free involution $varphi:binom Sktobinom Sk$.
For $iin[n]={1,dots,n}$, let $varphi_i:Sto S$ be the involution which flips the $i^text{th}$ bit; and for $Xinbinom Sk$, let $varphi_i[X]={varphi_i(x):xin X}inbinom Sk$.
If $Xinbinom Sk$, since $emptysetne Xne S$, there is some $iin[n]$ such that $varphi_i[X]ne X$; let $i(X)$ be the least such $i$.
Finally, define $varphi:binom Sktobinom Sk$ by setting $varphi(X)=varphi_{i(X)}[X]$. It is easy to see that $varphi$ is a fixed-point-free involution.
More generally, a similar argument shows that $binom{p^n}k$ is divisible by p whenever $p$ is a prime number and $n,k$ are integers, $0lt klt p^n$.
answered Jan 26 at 11:28
bofbof
52.5k558121
edited Jan 27 at 1:41
answered Jan 26 at 11:28
bofbof
52.5k558121
answered Jan 26 at 11:28
bofbof
52.5k558121
answered Jan 26 at 11:28
bofbof
52.5k558121
52.5k558121
add a comment |
add a comment |
$begingroup$
The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $mathbb{N}=left{ 0,1,2,ldotsright} $.
Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
$dbinom{n}{m}=dfrac{n}{m}cdotdbinom{n-1}{m-1}$.
Proof of Lemma 1. We have
begin{align*}
dbinom{n}{m} & =dfrac{ncdotleft( n-1right) cdotcdotscdotleft(
n-m+1right) }{m!} left( text{by the definition of
}dbinom{n}{m}right) \
& =dfrac{ncdotleft( left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) right) }{mcdotleft( m-1right)
!}\
& qquadqquadleft(
begin{array}
[c]{c}
text{since}\
ncdotleft( n-1right) cdotcdotscdotleft( n-m+1right) =ncdotleft(
left( n-1right) cdotleft( n-2right) cdotcdotscdotleft(
n-m+1right) right) \
text{and }m!=mcdotleft( m-1right) !
end{array}
right) \
& =dfrac{n}{m}cdotdfrac{left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) }{left( m-1right) !}\
& =dfrac{n}{m}cdotunderbrace{dfrac{left( n-1right) cdotleft(
n-2right) cdotcdotscdotleft( left( n-1right) -left( m-1right)
+1right) }{left( m-1right) !}}_{substack{=dbinom{n-1}{m-1}
\text{(since this is how }dbinom{n-1}{m-1}text{ is defined)}}}\
& qquadqquadleft( text{since }n-m=left( n-1right) -left(
m-1right) right) \
& =dfrac{n}{m}cdotdbinom{n-1}{m-1}.
end{align*}
Thus, Lemma 1 is proven. $blacksquare$
Lemma 2. Let $x$, $y$ and $z$ be three integers such that $xmid yz$ and
$gcdleft( x,yright) =1$. Then, $xmid z$.
Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$blacksquare$
Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
$p^{alpha}$ is a power of $p$.
Proof of Lemma 3. Let $d$ be a positive divisor of $p^{alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $qmid d$
(since the prime factorization of $d$ contains $q$). Hence, $qmid dmid
p^{alpha}$ (since $d$ is a divisor of $p^{alpha}$). Thus, the prime
factorization of $p^{alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $underbrace{ppcdots p}
_{alphatext{ times}}$, we thus conclude that the prime factorization
$underbrace{ppcdots p}_{alphatext{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $blacksquare$
Lemma 4. Let $p$ be a prime number. Let $alphainmathbb{N}$. Let $u$ be
an integer such that $u$ is not divisible by $p$. Then, $gcdleft(
u,p^{alpha}right) =1$.
Proof of Lemma 4. The integer $gcdleft( u,p^{alpha}right) $ is a
positive divisor of $p^{alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $gcdleft( u,p^{alpha}right) =p^{beta}$ for some
$betainmathbb{N}$. Consider this $beta$. If $beta>0$, then $pmid
p^{beta}=gcdleft( u,p^{alpha}right) mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $beta>0$,
and thus we must have $beta=0$. Hence, $p^{beta}=p^{0}=1$ and $gcdleft(
u,p^{alpha}right) =p^{beta}=1$. This proves Lemma 4. $blacksquare$
Theorem 5. Let $p$ be a prime number. Let $alphainmathbb{N}$ and let
$k$ be an integer such that $0<k<p^{alpha}$. Then, $dbinom{p^{alpha}}{k}$
is divisible by $p$.
Your claim follows from Theorem 5 (applied to $p=2$ and $alpha=n$), since your $k$ satisfies $0 < k < n leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $dbinom{p^{alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 3 (applied to $u=dbinom{p^{alpha}}{k}$)
that $gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$.
Applying Lemma 1 to $n=p^{alpha}$ and $m=k$, we obtain $dbinom{p^{alpha}
}{k}=dfrac{p^{alpha}}{k}cdotdbinom{p^{alpha}-1}{k-1}$, so that
$kdbinom{p^{alpha}}{k}=p^{alpha}dbinom{p^{alpha}-1}{k-1}$. Thus,
$p^{alpha}mid kdbinom{p^{alpha}}{k}=dbinom{p^{alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{alpha}$, $y=dbinom{p^{alpha}}{k}$ and $z=k$) yields
$p^{alpha}mid k$ (since $gcdleft( p^{alpha},dbinom{p^{alpha}}
{k}right) =gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$). Since
$k$ is positive, this yields $kgeq p^{alpha}$; but this contradicts
$k<p^{alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $blacksquare$
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
$endgroup$
add a comment |
$begingroup$
The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $mathbb{N}=left{ 0,1,2,ldotsright} $.
Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
$dbinom{n}{m}=dfrac{n}{m}cdotdbinom{n-1}{m-1}$.
Proof of Lemma 1. We have
begin{align*}
dbinom{n}{m} & =dfrac{ncdotleft( n-1right) cdotcdotscdotleft(
n-m+1right) }{m!} left( text{by the definition of
}dbinom{n}{m}right) \
& =dfrac{ncdotleft( left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) right) }{mcdotleft( m-1right)
!}\
& qquadqquadleft(
begin{array}
[c]{c}
text{since}\
ncdotleft( n-1right) cdotcdotscdotleft( n-m+1right) =ncdotleft(
left( n-1right) cdotleft( n-2right) cdotcdotscdotleft(
n-m+1right) right) \
text{and }m!=mcdotleft( m-1right) !
end{array}
right) \
& =dfrac{n}{m}cdotdfrac{left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) }{left( m-1right) !}\
& =dfrac{n}{m}cdotunderbrace{dfrac{left( n-1right) cdotleft(
n-2right) cdotcdotscdotleft( left( n-1right) -left( m-1right)
+1right) }{left( m-1right) !}}_{substack{=dbinom{n-1}{m-1}
\text{(since this is how }dbinom{n-1}{m-1}text{ is defined)}}}\
& qquadqquadleft( text{since }n-m=left( n-1right) -left(
m-1right) right) \
& =dfrac{n}{m}cdotdbinom{n-1}{m-1}.
end{align*}
Thus, Lemma 1 is proven. $blacksquare$
Lemma 2. Let $x$, $y$ and $z$ be three integers such that $xmid yz$ and
$gcdleft( x,yright) =1$. Then, $xmid z$.
Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$blacksquare$
Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
$p^{alpha}$ is a power of $p$.
Proof of Lemma 3. Let $d$ be a positive divisor of $p^{alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $qmid d$
(since the prime factorization of $d$ contains $q$). Hence, $qmid dmid
p^{alpha}$ (since $d$ is a divisor of $p^{alpha}$). Thus, the prime
factorization of $p^{alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $underbrace{ppcdots p}
_{alphatext{ times}}$, we thus conclude that the prime factorization
$underbrace{ppcdots p}_{alphatext{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $blacksquare$
Lemma 4. Let $p$ be a prime number. Let $alphainmathbb{N}$. Let $u$ be
an integer such that $u$ is not divisible by $p$. Then, $gcdleft(
u,p^{alpha}right) =1$.
Proof of Lemma 4. The integer $gcdleft( u,p^{alpha}right) $ is a
positive divisor of $p^{alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $gcdleft( u,p^{alpha}right) =p^{beta}$ for some
$betainmathbb{N}$. Consider this $beta$. If $beta>0$, then $pmid
p^{beta}=gcdleft( u,p^{alpha}right) mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $beta>0$,
and thus we must have $beta=0$. Hence, $p^{beta}=p^{0}=1$ and $gcdleft(
u,p^{alpha}right) =p^{beta}=1$. This proves Lemma 4. $blacksquare$
Theorem 5. Let $p$ be a prime number. Let $alphainmathbb{N}$ and let
$k$ be an integer such that $0<k<p^{alpha}$. Then, $dbinom{p^{alpha}}{k}$
is divisible by $p$.
Your claim follows from Theorem 5 (applied to $p=2$ and $alpha=n$), since your $k$ satisfies $0 < k < n leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $dbinom{p^{alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 3 (applied to $u=dbinom{p^{alpha}}{k}$)
that $gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$.
Applying Lemma 1 to $n=p^{alpha}$ and $m=k$, we obtain $dbinom{p^{alpha}
}{k}=dfrac{p^{alpha}}{k}cdotdbinom{p^{alpha}-1}{k-1}$, so that
$kdbinom{p^{alpha}}{k}=p^{alpha}dbinom{p^{alpha}-1}{k-1}$. Thus,
$p^{alpha}mid kdbinom{p^{alpha}}{k}=dbinom{p^{alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{alpha}$, $y=dbinom{p^{alpha}}{k}$ and $z=k$) yields
$p^{alpha}mid k$ (since $gcdleft( p^{alpha},dbinom{p^{alpha}}
{k}right) =gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$). Since
$k$ is positive, this yields $kgeq p^{alpha}$; but this contradicts
$k<p^{alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $blacksquare$
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
$endgroup$
add a comment |
$begingroup$
The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $mathbb{N}=left{ 0,1,2,ldotsright} $.
Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
$dbinom{n}{m}=dfrac{n}{m}cdotdbinom{n-1}{m-1}$.
Proof of Lemma 1. We have
begin{align*}
dbinom{n}{m} & =dfrac{ncdotleft( n-1right) cdotcdotscdotleft(
n-m+1right) }{m!} left( text{by the definition of
}dbinom{n}{m}right) \
& =dfrac{ncdotleft( left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) right) }{mcdotleft( m-1right)
!}\
& qquadqquadleft(
begin{array}
[c]{c}
text{since}\
ncdotleft( n-1right) cdotcdotscdotleft( n-m+1right) =ncdotleft(
left( n-1right) cdotleft( n-2right) cdotcdotscdotleft(
n-m+1right) right) \
text{and }m!=mcdotleft( m-1right) !
end{array}
right) \
& =dfrac{n}{m}cdotdfrac{left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) }{left( m-1right) !}\
& =dfrac{n}{m}cdotunderbrace{dfrac{left( n-1right) cdotleft(
n-2right) cdotcdotscdotleft( left( n-1right) -left( m-1right)
+1right) }{left( m-1right) !}}_{substack{=dbinom{n-1}{m-1}
\text{(since this is how }dbinom{n-1}{m-1}text{ is defined)}}}\
& qquadqquadleft( text{since }n-m=left( n-1right) -left(
m-1right) right) \
& =dfrac{n}{m}cdotdbinom{n-1}{m-1}.
end{align*}
Thus, Lemma 1 is proven. $blacksquare$
Lemma 2. Let $x$, $y$ and $z$ be three integers such that $xmid yz$ and
$gcdleft( x,yright) =1$. Then, $xmid z$.
Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$blacksquare$
Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
$p^{alpha}$ is a power of $p$.
Proof of Lemma 3. Let $d$ be a positive divisor of $p^{alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $qmid d$
(since the prime factorization of $d$ contains $q$). Hence, $qmid dmid
p^{alpha}$ (since $d$ is a divisor of $p^{alpha}$). Thus, the prime
factorization of $p^{alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $underbrace{ppcdots p}
_{alphatext{ times}}$, we thus conclude that the prime factorization
$underbrace{ppcdots p}_{alphatext{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $blacksquare$
Lemma 4. Let $p$ be a prime number. Let $alphainmathbb{N}$. Let $u$ be
an integer such that $u$ is not divisible by $p$. Then, $gcdleft(
u,p^{alpha}right) =1$.
Proof of Lemma 4. The integer $gcdleft( u,p^{alpha}right) $ is a
positive divisor of $p^{alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $gcdleft( u,p^{alpha}right) =p^{beta}$ for some
$betainmathbb{N}$. Consider this $beta$. If $beta>0$, then $pmid
p^{beta}=gcdleft( u,p^{alpha}right) mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $beta>0$,
and thus we must have $beta=0$. Hence, $p^{beta}=p^{0}=1$ and $gcdleft(
u,p^{alpha}right) =p^{beta}=1$. This proves Lemma 4. $blacksquare$
Theorem 5. Let $p$ be a prime number. Let $alphainmathbb{N}$ and let
$k$ be an integer such that $0<k<p^{alpha}$. Then, $dbinom{p^{alpha}}{k}$
is divisible by $p$.
Your claim follows from Theorem 5 (applied to $p=2$ and $alpha=n$), since your $k$ satisfies $0 < k < n leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $dbinom{p^{alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 3 (applied to $u=dbinom{p^{alpha}}{k}$)
that $gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$.
Applying Lemma 1 to $n=p^{alpha}$ and $m=k$, we obtain $dbinom{p^{alpha}
}{k}=dfrac{p^{alpha}}{k}cdotdbinom{p^{alpha}-1}{k-1}$, so that
$kdbinom{p^{alpha}}{k}=p^{alpha}dbinom{p^{alpha}-1}{k-1}$. Thus,
$p^{alpha}mid kdbinom{p^{alpha}}{k}=dbinom{p^{alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{alpha}$, $y=dbinom{p^{alpha}}{k}$ and $z=k$) yields
$p^{alpha}mid k$ (since $gcdleft( p^{alpha},dbinom{p^{alpha}}
{k}right) =gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$). Since
$k$ is positive, this yields $kgeq p^{alpha}$; but this contradicts
$k<p^{alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $blacksquare$
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
$endgroup$
The following solution (copypasted from my old coursework) is purely
elementary number theory:
We set $mathbb{N}=left{ 0,1,2,ldotsright} $.
Lemma 1. Let $n$ be an integer. Let $m$ be a positive integer. Then,
$dbinom{n}{m}=dfrac{n}{m}cdotdbinom{n-1}{m-1}$.
Proof of Lemma 1. We have
begin{align*}
dbinom{n}{m} & =dfrac{ncdotleft( n-1right) cdotcdotscdotleft(
n-m+1right) }{m!} left( text{by the definition of
}dbinom{n}{m}right) \
& =dfrac{ncdotleft( left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) right) }{mcdotleft( m-1right)
!}\
& qquadqquadleft(
begin{array}
[c]{c}
text{since}\
ncdotleft( n-1right) cdotcdotscdotleft( n-m+1right) =ncdotleft(
left( n-1right) cdotleft( n-2right) cdotcdotscdotleft(
n-m+1right) right) \
text{and }m!=mcdotleft( m-1right) !
end{array}
right) \
& =dfrac{n}{m}cdotdfrac{left( n-1right) cdotleft( n-2right)
cdotcdotscdotleft( n-m+1right) }{left( m-1right) !}\
& =dfrac{n}{m}cdotunderbrace{dfrac{left( n-1right) cdotleft(
n-2right) cdotcdotscdotleft( left( n-1right) -left( m-1right)
+1right) }{left( m-1right) !}}_{substack{=dbinom{n-1}{m-1}
\text{(since this is how }dbinom{n-1}{m-1}text{ is defined)}}}\
& qquadqquadleft( text{since }n-m=left( n-1right) -left(
m-1right) right) \
& =dfrac{n}{m}cdotdbinom{n-1}{m-1}.
end{align*}
Thus, Lemma 1 is proven. $blacksquare$
Lemma 2. Let $x$, $y$ and $z$ be three integers such that $xmid yz$ and
$gcdleft( x,yright) =1$. Then, $xmid z$.
Lemma 2 is a classical result in elementary number theory (see, e.g.,
Proposition 1.2.8 in my 18.781 (Spring 2016): Floor and arithmetic
functions).
$blacksquare$
Lemma 3. Let $p$ be a prime number. Then, every positive divisor of
$p^{alpha}$ is a power of $p$.
Proof of Lemma 3. Let $d$ be a positive divisor of $p^{alpha}$. We must
show that $d$ is a power of $p$.
Assume the contrary. Thus, the prime factorization of $d$ must contain at
least one prime $q$ distinct from $p$. Consider this $q$. Now, $qmid d$
(since the prime factorization of $d$ contains $q$). Hence, $qmid dmid
p^{alpha}$ (since $d$ is a divisor of $p^{alpha}$). Thus, the prime
factorization of $p^{alpha}$ contains the prime $q$ (since $q$ is a prime).
Since this prime factorization is clearly $underbrace{ppcdots p}
_{alphatext{ times}}$, we thus conclude that the prime factorization
$underbrace{ppcdots p}_{alphatext{ times}}$ contains $q$. Hence, $q=p$.
This contradicts the fact that $q$ is distinct from $p$. This contradiction
proves that our assumption was wrong; hence, Lemma 3 is proven. $blacksquare$
Lemma 4. Let $p$ be a prime number. Let $alphainmathbb{N}$. Let $u$ be
an integer such that $u$ is not divisible by $p$. Then, $gcdleft(
u,p^{alpha}right) =1$.
Proof of Lemma 4. The integer $gcdleft( u,p^{alpha}right) $ is a
positive divisor of $p^{alpha}$, and therefore a power of $p$ (by Lemma 3).
In other words, $gcdleft( u,p^{alpha}right) =p^{beta}$ for some
$betainmathbb{N}$. Consider this $beta$. If $beta>0$, then $pmid
p^{beta}=gcdleft( u,p^{alpha}right) mid u$, which contradicts the
assumption that $u$ is not divisible by $p$. Hence, we cannot have $beta>0$,
and thus we must have $beta=0$. Hence, $p^{beta}=p^{0}=1$ and $gcdleft(
u,p^{alpha}right) =p^{beta}=1$. This proves Lemma 4. $blacksquare$
Theorem 5. Let $p$ be a prime number. Let $alphainmathbb{N}$ and let
$k$ be an integer such that $0<k<p^{alpha}$. Then, $dbinom{p^{alpha}}{k}$
is divisible by $p$.
Your claim follows from Theorem 5 (applied to $p=2$ and $alpha=n$), since your $k$ satisfies $0 < k < n leq 2^n$.
Proof of Theorem 5. Assume the contrary. Thus, $dbinom{p^{alpha}}{k}$ is
not divisible by $p$. Hence, Lemma 3 (applied to $u=dbinom{p^{alpha}}{k}$)
that $gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$.
Applying Lemma 1 to $n=p^{alpha}$ and $m=k$, we obtain $dbinom{p^{alpha}
}{k}=dfrac{p^{alpha}}{k}cdotdbinom{p^{alpha}-1}{k-1}$, so that
$kdbinom{p^{alpha}}{k}=p^{alpha}dbinom{p^{alpha}-1}{k-1}$. Thus,
$p^{alpha}mid kdbinom{p^{alpha}}{k}=dbinom{p^{alpha}}{k}k$. Hence, Lemma
2 (applied to $x=p^{alpha}$, $y=dbinom{p^{alpha}}{k}$ and $z=k$) yields
$p^{alpha}mid k$ (since $gcdleft( p^{alpha},dbinom{p^{alpha}}
{k}right) =gcdleft( dbinom{p^{alpha}}{k},p^{alpha}right) =1$). Since
$k$ is positive, this yields $kgeq p^{alpha}$; but this contradicts
$k<p^{alpha}$. This contradiction shows that our assumption was wrong. Thus,
Theorem 5 is proven. $blacksquare$
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
answered Jan 26 at 0:21
darij grinbergdarij grinberg
11.2k33167
11.2k33167
add a comment |
add a comment |
$begingroup$
The solution is immediate using Lucas's theorem since
$${2^n choose k} = prod_{i=0}^n{m_i choose k_i} mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
answered Jan 26 at 10:33
mbjoembjoe
2361110
$endgroup$
add a comment |
$begingroup$
The solution is immediate using Lucas's theorem since
$${2^n choose k} = prod_{i=0}^n{m_i choose k_i} mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
answered Jan 26 at 10:33
mbjoembjoe
2361110
$endgroup$
add a comment |
$begingroup$
The solution is immediate using Lucas's theorem since
$${2^n choose k} = prod_{i=0}^n{m_i choose k_i} mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
answered Jan 26 at 10:33
mbjoembjoe
2361110
$endgroup$
The solution is immediate using Lucas's theorem since
$${2^n choose k} = prod_{i=0}^n{m_i choose k_i} mod 2$$ where $m_i$ are the binary coefficients of $2^n$ and $k_i$ those of $k$, and since $k < 2^n$ then some $k_j$ ($j < n$) is equal to 1 while $m_j = 0$ because the only coefficient of $2^n$ equal to 1 is $m_n$.
answered Jan 26 at 10:33
mbjoembjoe
2361110
answered Jan 26 at 10:33
mbjoembjoe
2361110
answered Jan 26 at 10:33
mbjoembjoe
2361110
answered Jan 26 at 10:33
mbjoembjoe
2361110
2361110
add a comment |
add a comment |
$begingroup$
More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0lt klt p^n$, then the binomial coefficient $binom{p^n}k$ is divisible by $p$.
Let $nu_p(m)$ denote the highest exponent $nu$ such that $p^nu$ divides $m$. Let $h=p^n-k$. Since
$$nu_pleft(binom{p^n}kright)=nu_pleft(frac{p^n!}{h!k!}right)=nu_p(p^n!)-nu_p(h!)-nu_p(k!),$$
it will suffice to show that $nu_p(p^n!)-nu_p(h!)-nu_p(k!)ge1.$
In view of Legendre's formula
$$nu_p(m!)=sum_{i=1}^inftyleftlfloorfrac m{p^i}rightrfloor,$$
this is the same as showing that
$$sum_{i=1}^inftyleft(leftlfloorfrac{p^n}{p^i}rightrfloor-leftlfloorfrac h{p^i}rightrfloor-leftlfloorfrac k{p^i}rightrfloorright)ge1.tag1$$
Now, every term of the series is nonnegative, since $lfloor x+yrfloorgelfloor xrfloor+lfloor yrfloor$ for all real $x,y$.
Since the $i=n$ term is
$$leftlfloorfrac{p^n}{p^n}rightrfloor-leftlfloorfrac h{p^n}rightrfloor-leftlfloorfrac k{p^n}rightrfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
answered Jan 28 at 6:17
bofbof
52.5k558121
$endgroup$
add a comment |
$begingroup$
More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0lt klt p^n$, then the binomial coefficient $binom{p^n}k$ is divisible by $p$.
Let $nu_p(m)$ denote the highest exponent $nu$ such that $p^nu$ divides $m$. Let $h=p^n-k$. Since
$$nu_pleft(binom{p^n}kright)=nu_pleft(frac{p^n!}{h!k!}right)=nu_p(p^n!)-nu_p(h!)-nu_p(k!),$$
it will suffice to show that $nu_p(p^n!)-nu_p(h!)-nu_p(k!)ge1.$
In view of Legendre's formula
$$nu_p(m!)=sum_{i=1}^inftyleftlfloorfrac m{p^i}rightrfloor,$$
this is the same as showing that
$$sum_{i=1}^inftyleft(leftlfloorfrac{p^n}{p^i}rightrfloor-leftlfloorfrac h{p^i}rightrfloor-leftlfloorfrac k{p^i}rightrfloorright)ge1.tag1$$
Now, every term of the series is nonnegative, since $lfloor x+yrfloorgelfloor xrfloor+lfloor yrfloor$ for all real $x,y$.
Since the $i=n$ term is
$$leftlfloorfrac{p^n}{p^n}rightrfloor-leftlfloorfrac h{p^n}rightrfloor-leftlfloorfrac k{p^n}rightrfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
answered Jan 28 at 6:17
bofbof
52.5k558121
$endgroup$
add a comment |
$begingroup$
More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0lt klt p^n$, then the binomial coefficient $binom{p^n}k$ is divisible by $p$.
Let $nu_p(m)$ denote the highest exponent $nu$ such that $p^nu$ divides $m$. Let $h=p^n-k$. Since
$$nu_pleft(binom{p^n}kright)=nu_pleft(frac{p^n!}{h!k!}right)=nu_p(p^n!)-nu_p(h!)-nu_p(k!),$$
it will suffice to show that $nu_p(p^n!)-nu_p(h!)-nu_p(k!)ge1.$
In view of Legendre's formula
$$nu_p(m!)=sum_{i=1}^inftyleftlfloorfrac m{p^i}rightrfloor,$$
this is the same as showing that
$$sum_{i=1}^inftyleft(leftlfloorfrac{p^n}{p^i}rightrfloor-leftlfloorfrac h{p^i}rightrfloor-leftlfloorfrac k{p^i}rightrfloorright)ge1.tag1$$
Now, every term of the series is nonnegative, since $lfloor x+yrfloorgelfloor xrfloor+lfloor yrfloor$ for all real $x,y$.
Since the $i=n$ term is
$$leftlfloorfrac{p^n}{p^n}rightrfloor-leftlfloorfrac h{p^n}rightrfloor-leftlfloorfrac k{p^n}rightrfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
answered Jan 28 at 6:17
bofbof
52.5k558121
$endgroup$
More generally, if $p$ is a prime number, and if $n,k$ are integers such that $0lt klt p^n$, then the binomial coefficient $binom{p^n}k$ is divisible by $p$.
Let $nu_p(m)$ denote the highest exponent $nu$ such that $p^nu$ divides $m$. Let $h=p^n-k$. Since
$$nu_pleft(binom{p^n}kright)=nu_pleft(frac{p^n!}{h!k!}right)=nu_p(p^n!)-nu_p(h!)-nu_p(k!),$$
it will suffice to show that $nu_p(p^n!)-nu_p(h!)-nu_p(k!)ge1.$
In view of Legendre's formula
$$nu_p(m!)=sum_{i=1}^inftyleftlfloorfrac m{p^i}rightrfloor,$$
this is the same as showing that
$$sum_{i=1}^inftyleft(leftlfloorfrac{p^n}{p^i}rightrfloor-leftlfloorfrac h{p^i}rightrfloor-leftlfloorfrac k{p^i}rightrfloorright)ge1.tag1$$
Now, every term of the series is nonnegative, since $lfloor x+yrfloorgelfloor xrfloor+lfloor yrfloor$ for all real $x,y$.
Since the $i=n$ term is
$$leftlfloorfrac{p^n}{p^n}rightrfloor-leftlfloorfrac h{p^n}rightrfloor-leftlfloorfrac k{p^n}rightrfloor=1-0-0=1,$$
the inequality $(1)$ follows and everything is fine.
answered Jan 28 at 6:17
bofbof
52.5k558121
answered Jan 28 at 6:17
bofbof
52.5k558121
answered Jan 28 at 6:17
bofbof
52.5k558121
answered Jan 28 at 6:17
bofbof
52.5k558121
52.5k558121
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%2f3087700%2fhow-to-prove-binomial-coefficient-2n-choose-k-is-even-number%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$
It even works for $0 < k < 2^n$.
$endgroup$
– Daniel Schepler
Jan 25 at 23:09