Mixing
Combinatorial Proof vs. Algebraic Proof
$begingroup$
I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:
Prove the following two formulas by combinatorial means and algebraic manipulation:
(i) For all $k$, $n in mathbb{N}$ with $k leq n$.
${n choose 2} + {n+1 choose 2} = n^{2}$.
(ii) For all $k$, $n in mathbb{N}$ with $k leq n$.
$k{n choose k} = n{n-1 choose k-1}$.
combinatorics
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
$endgroup$
add a comment |
$begingroup$
I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:
Prove the following two formulas by combinatorial means and algebraic manipulation:
(i) For all $k$, $n in mathbb{N}$ with $k leq n$.
${n choose 2} + {n+1 choose 2} = n^{2}$.
(ii) For all $k$, $n in mathbb{N}$ with $k leq n$.
$k{n choose k} = n{n-1 choose k-1}$.
combinatorics
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
$endgroup$
2
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
2
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15
add a comment |
$begingroup$
I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:
Prove the following two formulas by combinatorial means and algebraic manipulation:
(i) For all $k$, $n in mathbb{N}$ with $k leq n$.
${n choose 2} + {n+1 choose 2} = n^{2}$.
(ii) For all $k$, $n in mathbb{N}$ with $k leq n$.
$k{n choose k} = n{n-1 choose k-1}$.
combinatorics
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
$endgroup$
I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:
Prove the following two formulas by combinatorial means and algebraic manipulation:
(i) For all $k$, $n in mathbb{N}$ with $k leq n$.
${n choose 2} + {n+1 choose 2} = n^{2}$.
(ii) For all $k$, $n in mathbb{N}$ with $k leq n$.
$k{n choose k} = n{n-1 choose k-1}$.
combinatorics
combinatorics
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
asked Jan 18 at 2:20
Kishan PatelKishan Patel
174
174
2
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
2
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15
add a comment |
2
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
2
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15
2
2
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
2
2
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
binom{n}{2} + binom{n+1}{2} = frac{n(n-1) + (n+1)n}{2} = n^2,
$$
and
$$
kbinom{n}{k} = kfrac{n!}{k!(n-k)!} = frac{n!}{(k-1)!(n-k)!} = nfrac{(n-1)!}{(k-1)!(n-k)!} = nbinom{n-1}{k-1}.
$$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ sum_{k=0}^n binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 leq p leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
$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%2f3077762%2fcombinatorial-proof-vs-algebraic-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
binom{n}{2} + binom{n+1}{2} = frac{n(n-1) + (n+1)n}{2} = n^2,
$$
and
$$
kbinom{n}{k} = kfrac{n!}{k!(n-k)!} = frac{n!}{(k-1)!(n-k)!} = nfrac{(n-1)!}{(k-1)!(n-k)!} = nbinom{n-1}{k-1}.
$$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ sum_{k=0}^n binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 leq p leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
$endgroup$
add a comment |
$begingroup$
Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
binom{n}{2} + binom{n+1}{2} = frac{n(n-1) + (n+1)n}{2} = n^2,
$$
and
$$
kbinom{n}{k} = kfrac{n!}{k!(n-k)!} = frac{n!}{(k-1)!(n-k)!} = nfrac{(n-1)!}{(k-1)!(n-k)!} = nbinom{n-1}{k-1}.
$$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ sum_{k=0}^n binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 leq p leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
$endgroup$
add a comment |
$begingroup$
Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
binom{n}{2} + binom{n+1}{2} = frac{n(n-1) + (n+1)n}{2} = n^2,
$$
and
$$
kbinom{n}{k} = kfrac{n!}{k!(n-k)!} = frac{n!}{(k-1)!(n-k)!} = nfrac{(n-1)!}{(k-1)!(n-k)!} = nbinom{n-1}{k-1}.
$$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ sum_{k=0}^n binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 leq p leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
$endgroup$
Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
binom{n}{2} + binom{n+1}{2} = frac{n(n-1) + (n+1)n}{2} = n^2,
$$
and
$$
kbinom{n}{k} = kfrac{n!}{k!(n-k)!} = frac{n!}{(k-1)!(n-k)!} = nfrac{(n-1)!}{(k-1)!(n-k)!} = nbinom{n-1}{k-1}.
$$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ sum_{k=0}^n binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 leq p leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
answered Jan 18 at 9:07
Yuval FilmusYuval Filmus
48.7k471145
48.7k471145
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%2f3077762%2fcombinatorial-proof-vs-algebraic-proof%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
2
$begingroup$
A combinatorial proof is generally one which "tells a story" and through metaphor of the story proves the desired result. Commonly, this is done by presenting a scenario which we wish to count and explaining how by approaching the problem in different ways we arrive at different expressions for the final result, but by the nature that they count the same thing they are therefore equal despite appearing different. For (ii) for instance, consider a group of $n$ people and you want to make a team of size $k$ where you designate one of those to be the team leader.
$endgroup$
– JMoravitz
Jan 18 at 2:29
2
$begingroup$
I encourage you to search this site for the phrase "combinatorial proof" and you will find dozens more examples. On the other hand, an algebraic proof is one which shows the one expression is equal to the other directly via algebraic manipulation. See also this question for more thoughts on what exactly a "combinatorial proof" is.
$endgroup$
– JMoravitz
Jan 18 at 2:32
$begingroup$
Somewhat less fancifully, a combinatorial proof describes the number as the cardinality of a set.
$endgroup$
– Matt Samuel
Jan 18 at 3:02
$begingroup$
Leave the combinatorial part : have you seen proofs by algebraic manipulation anywhere?
$endgroup$
– астон вілла олоф мэллбэрг
Jan 18 at 5:15