Mixing
prove that $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k}rightarrow a_n=n!$
$begingroup$
I try to prove that:
Given $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (combinatorial proofs)?
combinatorics combinatorial-proofs
asked Feb 1 at 12:55
provenproven
12
$endgroup$
|
show 2 more comments
$begingroup$
I try to prove that:
Given $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (combinatorial proofs)?
combinatorics combinatorial-proofs
asked Feb 1 at 12:55
provenproven
12
$endgroup$
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12
|
show 2 more comments
$begingroup$
I try to prove that:
Given $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (combinatorial proofs)?
combinatorics combinatorial-proofs
asked Feb 1 at 12:55
provenproven
12
$endgroup$
I try to prove that:
Given $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (combinatorial proofs)?
combinatorics combinatorial-proofs
combinatorics combinatorial-proofs
asked Feb 1 at 12:55
provenproven
12
asked Feb 1 at 12:55
provenproven
12
edited Feb 1 at 13:29
proven
asked Feb 1 at 12:55
provenproven
12
asked Feb 1 at 12:55
provenproven
12
asked Feb 1 at 12:55
provenproven
12
12
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12
|
show 2 more comments
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.
Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.
Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.
Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of
$$sum_{k=1}^n {n - 1 choose k - 1}(k-1)!a_{n-k}$$
ways to permute $n$ numbers. By definition, this is $a_n$.
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
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%2f3096198%2fprove-that-a-n-sum-k-1n-binomn-1k-1k-1a-n-k-rightarrow-a-n-n%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$
We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.
Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.
Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.
Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of
$$sum_{k=1}^n {n - 1 choose k - 1}(k-1)!a_{n-k}$$
ways to permute $n$ numbers. By definition, this is $a_n$.
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
add a comment |
$begingroup$
We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.
Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.
Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.
Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of
$$sum_{k=1}^n {n - 1 choose k - 1}(k-1)!a_{n-k}$$
ways to permute $n$ numbers. By definition, this is $a_n$.
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
add a comment |
$begingroup$
We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.
Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.
Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.
Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of
$$sum_{k=1}^n {n - 1 choose k - 1}(k-1)!a_{n-k}$$
ways to permute $n$ numbers. By definition, this is $a_n$.
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
$endgroup$
We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.
Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.
Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.
Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of
$$sum_{k=1}^n {n - 1 choose k - 1}(k-1)!a_{n-k}$$
ways to permute $n$ numbers. By definition, this is $a_n$.
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
answered Feb 1 at 14:15
Todor MarkovTodor Markov
2,420412
2,420412
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
add a comment |
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
$begingroup$
sorry, I wish a combinatorial-proof
$endgroup$
– proven
Feb 1 at 15:51
1
1
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
@proven What is not combinatorial about this?
$endgroup$
– Todor Markov
Feb 1 at 16:07
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
$begingroup$
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc.
$endgroup$
– proven
Feb 1 at 16:14
1
1
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
$begingroup$
@proven This is double counting of permutations. If your issue is with induction, I don't think it's avoidable, because the sequence is recurrent. Pretty much the only way to formally prove something about it is induction (or theorems that have themselves been proved using induction).
$endgroup$
– Todor Markov
Feb 1 at 16:45
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%2f3096198%2fprove-that-a-n-sum-k-1n-binomn-1k-1k-1a-n-k-rightarrow-a-n-n%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
$begingroup$
$a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work !
$endgroup$
– Surb
Feb 1 at 12:59
$begingroup$
what doesn't make any sense? this identity is right. you can check it.
$endgroup$
– proven
Feb 1 at 13:03
$begingroup$
Maybe it make sense for you, but not for me ! What does mean $a_n=sum_{k=1}^{n}binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1rightarrow a_n=n!$ ? is it a limit ?
$endgroup$
– Surb
Feb 1 at 13:11
$begingroup$
if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n!
$endgroup$
– proven
Feb 1 at 13:12
$begingroup$
make sense now?
$endgroup$
– proven
Feb 1 at 13:12