How to prove there exists a positive integer $1\le i\le n$ so that $p^i(x)=x$ when $p:[n]\to[n]$ is permutation and $x\in[n]$

80 Views Asked by At

I am reading book A Walk Through Combinatorics and here is a Lemma and its proof.

Let $p:[n]\to[n]$ be a permutation, and let $x\in[n]$, then there exists a positive integer $1\le i\le n$ so that $p^i(x)=x$.
Proof: Consider the entries $p(x),p^2(x),\cdots,p^n(x)$. If none of them is equal to $x$, then the Pigeon-hole Principle implies that there are two of themthat are equal, say $p^j(x)=p^k(x)$, with $j<k$. Then, applying $p^{−1}$ to both sides of this equation, we get $p^{j−1}(x)=p^{k−1}(x)$. Repeating this step, we get $p^{j−2}(x)=p^{k−2}(x)$, and repeating this step $j−3$ more times, we get $p(x)=p^{k−j+1}(x)$.

In the end, the writer says we get $p(x)=p^{k−j+1}(x)$ but he doesn't say anything about $p^i(x)=x$ or something like this. Or here is another $x$ which meets the assumption of lemma? Or it contradicts something? How to understand this proof?

1

There are 1 best solutions below

0
On BEST ANSWER

It probably should say to apply the step $j-2$ more times to get $x = p^{k-j}(x)$, which contradicts that none of the entries were equal to $x$.