Suppose that $H \leq S_n$, and suppose that $H$ has the property that all non-identity elements of $H$ are fixed-point free. Show that $|H| \leq n$.
I am trying to prove this by induction.
For $S_3$, $H_3 = \{e,(123),(132)\}$ so |H_3|=3. So true for $n = 3$.
Assume true for $n=k$ i.e $|H_k|\leq k$.
Then for $n=k+1$. Since $|H_{k+1}| \leq (k+1)!$ I am trying to eliminate elements of $H_{k+1}$ to reduce this to $|H_{k+1}| \leq k+1$.
If we add the $k+1$th element as a disjoint cycle of any permutations of $S_n$ then the permutation fixes the $k+1$th element so $|H_{k+1}| \leq (k+1)! - k!$
Also if we add the $k+1$th element to a cycle which already fixes an element $(1...k)$ (so long as we don't add it so that it transposes our fixed element) then that element remains fixed. There are $(k-1)!$ such elements (by assumption) so $|H_{k+1}| \leq (k+1)! - k! - (k-1)!$.
However this still leaves a number of remaining elements. I think this is because we can choose what part of the cycle we want to put our $k+1$th element in. e.g. Say $(12)(34)(5)$ fixes $5$ in $S_5$ then both $(126)(34)(5),(162)(34)(5) ,(12)(346)(5) and,(12)(364)(5)$ all fix $5$ in $S_6.$
How can I find my remaining elements? Or can someone suggest a better way to tackle this problem? Thanks.
I do not think that this proposition allows a nice proof by induction. Note that you can't construct every subgroup of $S_n$ by adding an element to a subgroup of $S_{n-1}$. Instead, you can apply the pigeon-hole principle immediately: If $|H|>n$, there must exists $h_1,h_2 \in H$ with $h_1(1)=h_2(1)$. Then $1$ is a fixed point of $h_1^ {-1}h_2$.