Let $A$ be a finite set. Let $f:A\to A$ be an injective function from the set $A$ to itself and let $x_0$ be an element of $A$. Let $x_n$ be defined for all positive integers $n$ so that $x_n=f(x_{n-1})$ for all positive integers $n$. Prove that there exists some positive integer $m$ such that $x_m=x_0$.

Now a function is said to be injective when there is a one to one mapping. When $f : A \to A$, it means that for any element $x$ in $A$, it maps to a distinct element $y$ in $A$.

Now applying the function $x_n=f(x_{n-1})$ if $n =1$, then the function would give a result $x_0$.

The question is how do i prove this even thou i have show that there exists some positive integer which in this case is $1$


1 Answer 1


Here’s an outline of the proof.

You start with $x_0\in A$ and keep applying the function $f$ to get $x_1=f(x_0)$, $x_2=f(x_1)=f\big(f(x_0)\big)$, and so on. This generates a sequence $\langle x_0,x_1,x_2,\dots\rangle$ of elements of $A$.

Now prove by induction on $n$ that if $x_0,x_1,x_2,\dots,x_n$ are all distinct elements of $A$, then $$x_{n+1}=f(x_n)\notin\{x_1,\dots,x_n\}\;;$$ use the fact that $f$ is injective. From this you can conclude that either $x_{n+1}=x_0$, in which case you’re done, or $x_0,x_1,x_2,\dots,x_n,x_{n+1}$ are all distinct elements of $A$, and the induction can continue. Since $A$ is finite, it must stop at some point, and at that point you have your desired $m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.