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:
- Choose a permutation of the first $m$ elements.
- Insert the final element into the permutation.
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)!$.
Well, it is true, and in fact you only need $2n-1$ integers in order to do so. It was proven by Erdős, Ginzburg and Ziv and it is not a trivial application of pigeon-hole principle.
One way that I know of proving it is using the Chevary-Warning theorem, which states that for $p$ prime, given polinomials $f_1,...,f_n\in\mathbb{Z[x_1,...,x_n]}$, such that
$$\sum_{1\leq i\leq k}deg(f_i)\leq n-1$$
the set
$$A=\{(x_1,...,x_n)\in\mathbb{Z}_p^n|f_i(x_1,...,x_n)=0\forall i=1,...,k \}$$
satisfies $p$ divides $|A|$ (the cardinality of $A$).
Using this, we can prove that for $n$ prime, given the set $\{a_1,.,,a_{2n-1}\}$, the system
$$f_1(x_1,...,x_{2n-1})=x_1^{n-1}+...+x_{2n-1}^{n-1}=0\quad(mod p)$$
$$f_2(x_1,...,x_{2n-1})=a_1x_1^{n-1}+...+a_{2n-1}x_{2n-1}^{n-1}=0\quad (mod p)$$
have more than one solution, by the Chevary-Warning theorem (one solution is trivially $x_i=0$). As each $x_i^{n-1}$ is either 0 or 1, by Fermat's little theorem, a non-trivial solution to the systems corresponds to the choice of $n$ numbers such that theirs sum is multiple of $n$.
For the cases when $n$ is not prime we can use induction over the numbers of prime factos of $n$: if there is an anwser for $m$ and $n$ it is easy to obtain an answer for $mn$...
Edit: just to clarify, this proof of is not mine, I took it from the book "Teoria dos Números: Um Passeio com Primos e Outros Números Familiares Pelo Mundo Inteiro", which is a book about number theory in portuguese.
Best Answer
Phicar's suggestion in the comments is a good one. It follows from the q-binomial theorem that $$q^\binom{m}{2} \binom{n}{m}_q = \sum_{X \subset [n] : |X| = m} q^{\sigma(X)}, \qquad (*)$$ where $\sigma(X)$ is the sum of the elements of a subset $X \subset \{1, \dots, n\}$. We are going to evaluate this expression on all complex $m$th roots of unity and sum. On the right-hand side, the only terms which survive are those with $\sigma(X) \equiv 0 \pmod m$, so we get precisely $m$ times what we want. What do we get on the left-hand side?
Say $q = e^{i2\pi k / m}$. First, $q^\binom{m}{2} = e^{i2\pi k (m-1)/2} = (-1)^{k(m-1)}$. Second, by definition $$ \binom{n}{m}_q = \frac{(q^n - 1)(q^{n-1} - 1) \cdots (q^{n-m+1} - 1)}{(q^m-1) (q^{m-1} - 1) \cdots (q - 1)}.$$ The apparent singularities near roots of unity are all removable (this follows from (*) for example). We can evaluate $\binom{n}{m}_q$ when $q$ is a primitive $d$th root of unity, where $d \mid m$, by applying l'Hospital's rule $m/d$ times. Let $n'$ be the largest multiple of $d$ less than $n$. Then we get $$ \frac{n'(n'-d) \dots (n'-m+d)}{m(m-d) \dots d} = \binom{n'/d}{m/d}.$$ Since there are $\varphi(d)$ primitive $d$th roots of unity, all together we get $$\sum_{d \mid m} (-1)^{m(m-1)/d} \varphi(d) \binom{n'/d}{m/d}.$$ This is equivalent to your expression. (Regarding the sign factor, if $m$ is even then the sign factor is $(-1)^{m/d}$, so we agree in this case, while if $m$ is odd then the sign factor is always 1 and so is yours, so we agree in that case too.)