I have been working on this exercise for a while now. It's in B.L. van der Waerden's Algebra (Volume I), page $19$. The exercise is as follows:
The order of the symmetric group $S_n$ is $n!=\prod_{1}^{n}\nu$. (Mathematical induction on $n$.)
I don't comprehend how we can logically use induction here. It seems that the first step would be proving $S_1$ has $1!=1$ elements. This is simply justified: There is only one permutation of $1$, the permutation of $1$ to itself.
The next step would be assuming that $S_n$ has order $n!$. Now here is where I get stuck. How do I use this to show that $S_{n+1}$ has order $(n+1)!$?
Here is my attempt: I am thinking this is because all $n!$ permutations of $S_n$ now have a new element to permutate. For example, if we take one single permutation $ p(1,\dots,n) = \begin{pmatrix} 1 & 2 & 3 & \dots & n\\ 1 & 2 & 3 & \dots & n \end{pmatrix} $ We now have $n$ modifications of this single permutation by adding the symbol $(n+1)$:
\begin{align} p(1,2,\dots,n,(n+1))&= \begin{pmatrix} 1 & 2 & \dots & n & (n+1)\\ 1 & 2 & \dots & n & (n+1) \end{pmatrix}\\ p(2,1,\dots,n,(n+1))&= \begin{pmatrix} 1 & 2 & \dots & n & (n+1)\\ 2 & 1 & \dots & n & (n+1) \end{pmatrix}\\ \vdots\\ p(n,2,\dots,1,(n+1))&= \begin{pmatrix} 1 & 2 & \dots & n & (n+1)\\ n & 2 & \dots & 1 & (n+1) \end{pmatrix}\\ p((n+1),2,\dots,n,1)&= \begin{pmatrix} 1 & 2 & \dots & n & (n+1)\\ (n+1) & 2 & \dots & n & 1 \end{pmatrix} \end{align}
There are actually $(n+1)$ permutations of that specific form, but we take $p(1,\dots,n)=p(1,\dots,n,(n+1))$ in order to illustrate and prove our original statement. We can make this general equality for all $n!$ permutations: $p(x_1,x_2,\dots,x_n)=p(x_1,x_2,\dots,x_n,x_{n+1})$ where $x_i$ is any symbol of our finite set of $n$ symbols and $x_{n+1}$ is strictly defined as the symbol $(n+1)$.
We can repeat this process for all $n!$ permutations in $S_n$. This gives us $n!n$ permutations. Then, adding in the original $n!$ permutations, we have $n!n+n!=(n+1)n!=(n+1)!$. Consequently, $S_n$ has order $n!$.
How is my reasoning here? Furthermore, is there a more elegant argument? I do not really see my argument here as incorrect, it just seems to lack elegance. My reasoning may well be very incorrect, however. If so, please point it out to me.