Mixing
algebraic derivation of sum of binomial coefficients
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I've seen the standard combinatorial and algebraic proofs that $sum_k=0^n n choose k=2^n$, where the algebraic proof uses induction and Pascal's identity: $$nchoose k+nchoose k+1=n+1choose k+1$$
My question is: is there any algebraic proof of the sum $sum_k=0^n n choose k=2^n$ that doesn't use that identity and induction? More specifically, is there some factoring trick (or some other method) that would allow you to directly show that, for example, $frac4!4!0!+frac4!3!1!+frac4!2!2!+frac4!1!3!+frac4!4!0!=2^4$ (that would generalize to other values of n)?
(My first thought was to just 'unwind' the inductive proof, but that just leads to $1+1+...+1$ with $2^n$ terms, which isn't very enlightening.)
binomial-coefficients
asked Jul 24 at 8:01
nhg
61
add a comment |Â
up vote
1
down vote
favorite
I've seen the standard combinatorial and algebraic proofs that $sum_k=0^n n choose k=2^n$, where the algebraic proof uses induction and Pascal's identity: $$nchoose k+nchoose k+1=n+1choose k+1$$
My question is: is there any algebraic proof of the sum $sum_k=0^n n choose k=2^n$ that doesn't use that identity and induction? More specifically, is there some factoring trick (or some other method) that would allow you to directly show that, for example, $frac4!4!0!+frac4!3!1!+frac4!2!2!+frac4!1!3!+frac4!4!0!=2^4$ (that would generalize to other values of n)?
(My first thought was to just 'unwind' the inductive proof, but that just leads to $1+1+...+1$ with $2^n$ terms, which isn't very enlightening.)
binomial-coefficients
asked Jul 24 at 8:01
nhg
61
2
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I've seen the standard combinatorial and algebraic proofs that $sum_k=0^n n choose k=2^n$, where the algebraic proof uses induction and Pascal's identity: $$nchoose k+nchoose k+1=n+1choose k+1$$
My question is: is there any algebraic proof of the sum $sum_k=0^n n choose k=2^n$ that doesn't use that identity and induction? More specifically, is there some factoring trick (or some other method) that would allow you to directly show that, for example, $frac4!4!0!+frac4!3!1!+frac4!2!2!+frac4!1!3!+frac4!4!0!=2^4$ (that would generalize to other values of n)?
(My first thought was to just 'unwind' the inductive proof, but that just leads to $1+1+...+1$ with $2^n$ terms, which isn't very enlightening.)
binomial-coefficients
asked Jul 24 at 8:01
nhg
61
I've seen the standard combinatorial and algebraic proofs that $sum_k=0^n n choose k=2^n$, where the algebraic proof uses induction and Pascal's identity: $$nchoose k+nchoose k+1=n+1choose k+1$$
My question is: is there any algebraic proof of the sum $sum_k=0^n n choose k=2^n$ that doesn't use that identity and induction? More specifically, is there some factoring trick (or some other method) that would allow you to directly show that, for example, $frac4!4!0!+frac4!3!1!+frac4!2!2!+frac4!1!3!+frac4!4!0!=2^4$ (that would generalize to other values of n)?
(My first thought was to just 'unwind' the inductive proof, but that just leads to $1+1+...+1$ with $2^n$ terms, which isn't very enlightening.)
binomial-coefficients
asked Jul 24 at 8:01
nhg
61
asked Jul 24 at 8:01
nhg
61
asked Jul 24 at 8:01
nhg
61
asked Jul 24 at 8:01
nhg
61
61
2
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04
add a comment |Â
2
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04
2
2
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
Combinatorial argument:
$displaystylebinom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.
$$000,|,001,010,100,|,011,101,110,|,111$$
answered Jul 24 at 8:06
Yves Daoust
111k665203
add a comment |Â
up vote
0
down vote
We can apply the binomial theorem and obtain
beginalign*
colorbluesum_k=0^nbinomnk=sum_k=0^nbinomnk1^k1^n-k=(1+1)^ncolorblue=2^n
endalign*
answered Jul 24 at 12:15
Markus Scheuer
56k450135
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Combinatorial argument:
$displaystylebinom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.
$$000,|,001,010,100,|,011,101,110,|,111$$
answered Jul 24 at 8:06
Yves Daoust
111k665203
add a comment |Â
up vote
1
down vote
Combinatorial argument:
$displaystylebinom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.
$$000,|,001,010,100,|,011,101,110,|,111$$
answered Jul 24 at 8:06
Yves Daoust
111k665203
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Combinatorial argument:
$displaystylebinom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.
$$000,|,001,010,100,|,011,101,110,|,111$$
answered Jul 24 at 8:06
Yves Daoust
111k665203
Combinatorial argument:
$displaystylebinom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.
$$000,|,001,010,100,|,011,101,110,|,111$$
answered Jul 24 at 8:06
Yves Daoust
111k665203
edited Jul 24 at 8:12
answered Jul 24 at 8:06
Yves Daoust
111k665203
answered Jul 24 at 8:06
Yves Daoust
111k665203
answered Jul 24 at 8:06
Yves Daoust
111k665203
111k665203
add a comment |Â
add a comment |Â
up vote
0
down vote
We can apply the binomial theorem and obtain
beginalign*
colorbluesum_k=0^nbinomnk=sum_k=0^nbinomnk1^k1^n-k=(1+1)^ncolorblue=2^n
endalign*
answered Jul 24 at 12:15
Markus Scheuer
56k450135
add a comment |Â
up vote
0
down vote
We can apply the binomial theorem and obtain
beginalign*
colorbluesum_k=0^nbinomnk=sum_k=0^nbinomnk1^k1^n-k=(1+1)^ncolorblue=2^n
endalign*
answered Jul 24 at 12:15
Markus Scheuer
56k450135
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We can apply the binomial theorem and obtain
beginalign*
colorbluesum_k=0^nbinomnk=sum_k=0^nbinomnk1^k1^n-k=(1+1)^ncolorblue=2^n
endalign*
answered Jul 24 at 12:15
Markus Scheuer
56k450135
We can apply the binomial theorem and obtain
beginalign*
colorbluesum_k=0^nbinomnk=sum_k=0^nbinomnk1^k1^n-k=(1+1)^ncolorblue=2^n
endalign*
answered Jul 24 at 12:15
Markus Scheuer
56k450135
answered Jul 24 at 12:15
Markus Scheuer
56k450135
answered Jul 24 at 12:15
Markus Scheuer
56k450135
answered Jul 24 at 12:15
Markus Scheuer
56k450135
56k450135
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861100%2falgebraic-derivation-of-sum-of-binomial-coefficients%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
$2^n=(1+1)^n=$ ...
– Michael Hoppe
Jul 24 at 8:04