Proving a binomial series to be $2^n$ [duplicate]
$begingroup$
This question already has an answer here:
Proving by induction that $ sum_{k=0}^n{n choose k} = 2^n$
2 answers
I tried to prove
$$sumlimits_{r=0}^nbinom{n}{r}=sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^n.$$
I used induction method:
Assuming $$sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^{n}.$$
Proving $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =2^{n+1}.$$
I got $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =sumlimits_{r=0}^{n+1} Bigl(frac{n!}{r!(n-r)!}+frac{n!}{(r-1)!(n-r+1)!}Bigr),$$
and an invalid term appeared: $(-1)!$.
How does one prove this identity, and what's wrong with my method?
sequences-and-series binomial-coefficients
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
$endgroup$
marked as duplicate by JMoravitz, lab bhattacharjee sequences-and-series
Users with the sequences-and-series badge can single-handedly close sequences-and-series questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 14 '18 at 4:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Proving by induction that $ sum_{k=0}^n{n choose k} = 2^n$
2 answers
I tried to prove
$$sumlimits_{r=0}^nbinom{n}{r}=sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^n.$$
I used induction method:
Assuming $$sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^{n}.$$
Proving $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =2^{n+1}.$$
I got $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =sumlimits_{r=0}^{n+1} Bigl(frac{n!}{r!(n-r)!}+frac{n!}{(r-1)!(n-r+1)!}Bigr),$$
and an invalid term appeared: $(-1)!$.
How does one prove this identity, and what's wrong with my method?
sequences-and-series binomial-coefficients
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
$endgroup$
marked as duplicate by JMoravitz, lab bhattacharjee sequences-and-series
Users with the sequences-and-series badge can single-handedly close sequences-and-series questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 14 '18 at 4:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34
add a comment |
$begingroup$
This question already has an answer here:
Proving by induction that $ sum_{k=0}^n{n choose k} = 2^n$
2 answers
I tried to prove
$$sumlimits_{r=0}^nbinom{n}{r}=sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^n.$$
I used induction method:
Assuming $$sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^{n}.$$
Proving $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =2^{n+1}.$$
I got $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =sumlimits_{r=0}^{n+1} Bigl(frac{n!}{r!(n-r)!}+frac{n!}{(r-1)!(n-r+1)!}Bigr),$$
and an invalid term appeared: $(-1)!$.
How does one prove this identity, and what's wrong with my method?
sequences-and-series binomial-coefficients
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
$endgroup$
This question already has an answer here:
Proving by induction that $ sum_{k=0}^n{n choose k} = 2^n$
2 answers
I tried to prove
$$sumlimits_{r=0}^nbinom{n}{r}=sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^n.$$
I used induction method:
Assuming $$sumlimits_{r=0}^n frac{n!}{r!(n-r)!} =2^{n}.$$
Proving $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =2^{n+1}.$$
I got $$sumlimits_{r=0}^{n+1} frac{{(n+1)}!}{r!(n+1-r)!} =sumlimits_{r=0}^{n+1} Bigl(frac{n!}{r!(n-r)!}+frac{n!}{(r-1)!(n-r+1)!}Bigr),$$
and an invalid term appeared: $(-1)!$.
How does one prove this identity, and what's wrong with my method?
This question already has an answer here:
Proving by induction that $ sum_{k=0}^n{n choose k} = 2^n$
2 answers
sequences-and-series binomial-coefficients
sequences-and-series binomial-coefficients
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
edited Dec 14 '18 at 4:19
David G. Stork
12.1k41735
12.1k41735
asked Dec 14 '18 at 4:16
John HeJohn He
478
asked Dec 14 '18 at 4:16
John HeJohn He
478
asked Dec 14 '18 at 4:16
John HeJohn He
478
478
marked as duplicate by JMoravitz, lab bhattacharjee sequences-and-series
Users with the sequences-and-series badge can single-handedly close sequences-and-series questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 14 '18 at 4:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by JMoravitz, lab bhattacharjee sequences-and-series
Users with the sequences-and-series badge can single-handedly close sequences-and-series questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 14 '18 at 4:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34
add a comment |
1
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34
1
1
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The identity you are using in the last equality has some hypothesis: it holds when $r > 0$.
There are many approaches to prove this fact. I particulary like a combinatorial proof via the following counting argument: if $A_k$ is the set of subsets of ${1, dots, n}$ of size $k$, then by (one possible) definition, $|A_k| = {n choose k}$. Moreover, we have that the subsets of ${1, dots, n}$, that is the elements of $mathcal{P}({1,dots,n})$, are the disjoint union of $A_0, dots, A_n$.
Thus, $mathcal{P}({1,dots,n}) = sqcup_{0 leq i leq n}A_i$ and
$$
2^n = |mathcal{P}({1,dots,n})| = |sqcup_{0 leq i leq n}A_i| = sum_{i=0}^n|A_i| = sum_{i = 0}^n{n choose i}.
$$
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The identity you are using in the last equality has some hypothesis: it holds when $r > 0$.
There are many approaches to prove this fact. I particulary like a combinatorial proof via the following counting argument: if $A_k$ is the set of subsets of ${1, dots, n}$ of size $k$, then by (one possible) definition, $|A_k| = {n choose k}$. Moreover, we have that the subsets of ${1, dots, n}$, that is the elements of $mathcal{P}({1,dots,n})$, are the disjoint union of $A_0, dots, A_n$.
Thus, $mathcal{P}({1,dots,n}) = sqcup_{0 leq i leq n}A_i$ and
$$
2^n = |mathcal{P}({1,dots,n})| = |sqcup_{0 leq i leq n}A_i| = sum_{i=0}^n|A_i| = sum_{i = 0}^n{n choose i}.
$$
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
$endgroup$
add a comment |
$begingroup$
The identity you are using in the last equality has some hypothesis: it holds when $r > 0$.
There are many approaches to prove this fact. I particulary like a combinatorial proof via the following counting argument: if $A_k$ is the set of subsets of ${1, dots, n}$ of size $k$, then by (one possible) definition, $|A_k| = {n choose k}$. Moreover, we have that the subsets of ${1, dots, n}$, that is the elements of $mathcal{P}({1,dots,n})$, are the disjoint union of $A_0, dots, A_n$.
Thus, $mathcal{P}({1,dots,n}) = sqcup_{0 leq i leq n}A_i$ and
$$
2^n = |mathcal{P}({1,dots,n})| = |sqcup_{0 leq i leq n}A_i| = sum_{i=0}^n|A_i| = sum_{i = 0}^n{n choose i}.
$$
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
$endgroup$
add a comment |
$begingroup$
The identity you are using in the last equality has some hypothesis: it holds when $r > 0$.
There are many approaches to prove this fact. I particulary like a combinatorial proof via the following counting argument: if $A_k$ is the set of subsets of ${1, dots, n}$ of size $k$, then by (one possible) definition, $|A_k| = {n choose k}$. Moreover, we have that the subsets of ${1, dots, n}$, that is the elements of $mathcal{P}({1,dots,n})$, are the disjoint union of $A_0, dots, A_n$.
Thus, $mathcal{P}({1,dots,n}) = sqcup_{0 leq i leq n}A_i$ and
$$
2^n = |mathcal{P}({1,dots,n})| = |sqcup_{0 leq i leq n}A_i| = sum_{i=0}^n|A_i| = sum_{i = 0}^n{n choose i}.
$$
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
$endgroup$
The identity you are using in the last equality has some hypothesis: it holds when $r > 0$.
There are many approaches to prove this fact. I particulary like a combinatorial proof via the following counting argument: if $A_k$ is the set of subsets of ${1, dots, n}$ of size $k$, then by (one possible) definition, $|A_k| = {n choose k}$. Moreover, we have that the subsets of ${1, dots, n}$, that is the elements of $mathcal{P}({1,dots,n})$, are the disjoint union of $A_0, dots, A_n$.
Thus, $mathcal{P}({1,dots,n}) = sqcup_{0 leq i leq n}A_i$ and
$$
2^n = |mathcal{P}({1,dots,n})| = |sqcup_{0 leq i leq n}A_i| = sum_{i=0}^n|A_i| = sum_{i = 0}^n{n choose i}.
$$
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
answered Dec 14 '18 at 4:23
Guido A.Guido A.
8,1251730
8,1251730
add a comment |
add a comment |
1
$begingroup$
Try expanding $(1+1)^n$ by means of the Binomial Theorem.
$endgroup$
– Lubin
Dec 14 '18 at 4:18
$begingroup$
As an aside, rather than writing things out with factorials, you can use binomial coefficients instead. Now, note that $binom{n}{r} = 0$ for all cases where $r<0$ or $r>n$.
$endgroup$
– JMoravitz
Dec 14 '18 at 4:27
$begingroup$
Do you mean r>0 or r<n.
$endgroup$
– John He
Dec 14 '18 at 4:34