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)?

  • $\begingroup$ $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1\rightarrow 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=1\rightarrow 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

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$.

  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.