I am trying to use mathematical induction to prove the following theorem:
For any integer $n$ with $n \ge 1$, the number of permutations of a set with $n$ elements is $n!$.
Proof
Let $P(n)$ be the above statement.
Take the set of elements $\{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.
$P(1)$ holds because the number of permutations of $1$ element is size $1$ and $1! = 1$.
Now assume that $P(n)$ is true for some $n = m \ge 1$.
$P(m + 1)$ means that we have the set $\{ x_1, x_2, \dots, x_{m + 1} \}.$
I'm not sure how to proceed from here. I was thinking of using the multiplication rule somehow, but I've been unable to make progress on this.
I've also been unable to find any proofs for this theorem online.
I would greatly appreciate it if people could please help me prove this.
EDIT (Completed Proof):
Let $P(n)$ be the above statement.
Take the set $X = \{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.
$P(1)$ holds because the number of permutations of $1$ element is size $1$ and $1! = 1$.
Now assume that $P(n)$ is true for some $n = m \ge 1$.
And assume we have the sets $X = \{ x_1, x_2, \dots, x_m \}$ and $X' = \{ x_{m + 1} \}$.
Let task $T$ represent tasks $T_1, T_2, \dots, T_m$, where task $T_k, k = 1, 2, \dots, m$, represents the task where the $k$th element of the set $X$ is fixed and every permutation of the resultant set configuration is calculated.
Every time we fix one element and find all permutations of the resultant set, that leaves one set configuration that the next set cannot have since it would be identical to one of the permutations of the previous configuration. This is what we assumed to be true for a set with $m$ elements.
Let task $T_{m + 1}$ be the task where we take the set $X^* = X \cup X'$, fix the element $x_{m + 1}$, and calculate all permutations of the resultant set configuration. Since there are $m + 1$ elements in the set $X^*$, there are $m + 1$ ways to fix $x_{m + 1}$ ($m + 1$ set configurations) and calculate all permutations. Therefore, according to the multiplication rule, there are $(m!)(m + 1) = (m + 1)!$ ways to perform tasks $T$ and $T_{m + 1}$. $$\tag*{$\blacksquare$}$$
I would greatly appreciate it if people could please review the complete proof and provide feedback as to its correctness.
Best Answer
Your proof seems correct, but (in my opinion) it's too elaborate. It obscures the combinatorial simplicity of the argument. I might write the following:
Clearly, there is only one (that is, $1!$) permutation on a set containing a single element.
Suppose now (for the purpose of induction) that there are $m!$ permutations of a set containing $m$ elements. We seek to show that there are $(m+1)!$ permutations of a set containing $m+1$ elements.
We can construct all permutations of the latter set as follows:
By the inductive hypothesis, Step 1 can be completed in $m!$ ways. Step 2 can be completed in $m+1$ ways, since there are $m+1$ locations into which the final element may be inserted. Therefore, we have (by the multiplication principle) that the number of permutations of an $m+1$ element set is equal to $m! \cdot (m+1)$, which is the desired $(m+1)!$.