A problem from Herstein's Abstract algebra

[AdrianZ]

Homework Statement

if f \in S_n show that there is some positive integer k, depending on f, such that f^k=i. (from baby Herstein).

The Attempt at a Solution

Suppose that S={x₁,x₂,...,x_n}. Elements of S_n are bijections from S to S. to show that f^k=i it's enough to show that f^k(x_m)=x_m for every m (1<=m<=n)
If f is in S_n, then f may stabilize(not permute) a finite number of elements and permutes the other elements. the elements that are not permuted by f will also be stabilized by f^k. (because if f(x_s)=x_s, then f²(x_s)=f(x_s)=x_s and by induction It's possible to show that f^k(x_s)=x_s). So, for the elements that are not permuted by f we're done.
Now, We can suppose that x_p is permuted by f and f(x_p)=x_q (x_p\neqx_q). if we apply f again, f² will again permute x_p to another member of S and this process of permutation never halts because if finally x_p is mapped to something that is not permuted anymore by f, like x_s, then f^k(x_p)=x_s and f^k(x_s)=x_s which contradicts the fact that f^k is bijective. Since this process never halts and S is a finite set and f is a bijection, then finally after k times (2<=k<=n) f^k(x_p)=x_p (I'm in someway using the pigeonhole principle). this k depends on x_p. (It can be shown by studying permutations of S_n for n>2)
It's easy to show that if f^k(x_p)=x_p then f^nk(x_p)=x_p. since k is dependent to the x_p we choose, let's associate a k_i with every element of S that is permuted. by the same argument we know that f^k_i(x_pi)=x_pi. if we set K=LCM(k_i) then by our previous arguments, It's obvious that for any x_p we'll have f^K(x_p)=x_p. Q.E.D.

I come up with this proof after studying permutations in S₅. I know that the way I've explained my proof might be a little bit confusing but I hope that it's understandable. Is my proof correct? and if yes, is there any other way to prove it in a simpler way?

 

[HallsofIvy]

Actually, you don't even need to know that this is a group of permutations. This is true for any finite group. Consider the set of all x^k where k is any positive integer. There are an infinite number of possible values for k but only a finite number of possible values for x^k. Therefore, by the pigeon hole principle as you say, there must be some values, k_1 and k_2, with k_1\ne k_2 but x^{k_1}= x^{k_2}.

We can, without loss of generality, assume that k_1&lt; k_2. It follows that x^{k_2}x^{-k_1}= x^{k_2-k_1}= i.

 

[AdrianZ]

Actually, you don't even need to know that this is a group of permutations. This is true for any finite group. Consider the set of all x^k where k is any positive integer. There are an infinite number of possible values for k but only a finite number of possible values for x^k. Therefore, by the pigeon hole principle as you say, there must be some values, k_1 and k_2, with k_1\ne k_2 but x^{k_1}= x^{k_2}.

We can, without loss of generality, assume that k_1&lt; k_2. It follows that x^{k_2}x^{-k_1}= x^{k_2-k_1}= i.

I see. so, I had made the problem way harder than It actually was. Was my own proof correct?