Need explanation on a problem involving natural function Consider a positive integer $n$ and the function
$f:\mathbb{N}\to \mathbb{N}$ ($\mathbb N$ includes $0$) by
$$f(x) = \begin{cases}   \frac{x}{2}
 & \text{if } x \text{ is even} \\   \frac{x-1}{2} + 2^{n-1} & \text{if } x \text{ is odd} \end{cases} $$
Determine the set
$$   A = \{ x\in \mathbb{N} \mid \underbrace{\left( f\circ f\circ ....\circ f \right)}_{n\ f\text{'s}}\left( x \right)=x \}.   $$
(Romania NMO 2013)
The solution starts by stating that $f(x)<x, \quad\forall x\ge 2^n-1$. This was easy enough to understand. However, they continue by saying this implies that $A\subset\{0,1,\dots,2^n-1\}$. Why is that?
Please help me understand! Thanks in advance!
 A: Note first that the inequality $f(x) < x$ only holds for $x \geq 2^n$ since $f(2^n - 1) = 2^n -1$.
If there is an element $x \in A$ with $x \geq 2^n$, then we can choose such an $x$ minimally, i.e. such that every $y \in A$ with $y < x$ satisfies $y \leq 2^n - 1$. Now we have $f^n(x) = x$ and hence $$f^n(f(x)) = f^{n+1}(x) = f(f^n(x)) = f(x),$$ so $f(x) \in A$ and the minimality of $x$ together with $f(x) < x$ implies $f(x) \leq 2^n - 1$.
Now check that this implies $f^k(f(x)) \leq 2^n-1$ for all $k \in \mathbb{N}$ (as hinted at in Daniel's comment) and in particular $x = f^n(x) = f^{n-1}(f(x)) \leq 2^n-1$, contradicting the initial choice of $x$.
A: Hint:
Letting all divisions be integer and splitting the cases after the low order bits of $x$, we can expand the function iterates for, say, $n=4$, and the pattern becomes obvious.
$$f(x)=\begin{cases}\frac x2&\text{ if } x \text{ is even}\\\frac{x}2+8&\text{ if } x \text{ is odd}\end{cases}$$
$$f(f(x))=\begin{cases}\frac x4&\\\frac{x}4+4\\\frac{x}4+8\\\frac{x}4+12\end{cases}$$
$$f(f(f(x)))=\begin{cases}
\frac x8&\\\frac{x}8+2\\\frac{x}8+4\\\frac{x}8+6\\
\frac x8+8&\\\frac{x}8+10\\\frac{x}8+12\\\frac{x}8+14\end{cases}$$
$$f(f(f(f(x))))=\begin{cases}
\frac x{16}&\\\frac{x}{16}+1\\\frac{x}{16}+2\\\frac{x}{16}+3\\
\frac x{16}+4&\\\frac{x}{16}+5\\\frac{x}{16}+6\\\frac{x}{16}+7\\
\frac x{16}+8&\\\frac{x}{16}+9\\\frac{x}{16}+10\\\frac{x}{16}+11\\
\frac x{16}+12&\\\frac{x}{16}+13\\\frac{x}{16}+14\\\frac{x}{16}+15\end{cases}$$
A: Stating $f(x) < x,\forall x > 2^n-1$ can be seen as the base step for an induction argument.
We can finish by induction proving :
if  $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k\ f\text{'s}}\left( x \right) <  x,\forall x > 2^n-1$ then $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k+1\ f\text{'s}}\left( x \right) <x,\forall x > 2^n-1$.
First of all  put  $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k\ f\text{'s}}\left( x \right) = t_1$ and $\underbrace{\left( f\circ f\circ ....\circ f \right)}_{k+1\ f\text{'s}}\left( x \right) = t_2$ , now:

*

*if $t_1$ is even then $t_2 = \frac{t_1}{2} <  t_1< x$.


*if $t_1$ is odd, then $t_2 = \frac{t_1-1}{2}+2^{n-1}$, then we have to show:$$\frac{t_1-1}{2}+2^{n-1} < x \iff t_1 <x+x-(2^n-1)$$but we know that $t_1<x$ and that $x-(2^n-1)>0$, so $t_1 <x+x-(2^n-1)$ is true.
So clearly $A$ is a subset of $\{1,2,...,2^n-1\}$.
