Inductive proof $f(n) = n$ with function composition. I need help with a inductive proof. Currently got no idea how to start with this assignment.
Assignment:
Let $f : \mathbb{N}_0 \to \mathbb{N}_0$ be a function, so that the inequality:
$$f \circ f(n) < f(n+1)$$ exists. $\forall n \in \mathbb{N}_0$
Show that $f(n) = n$. $\forall n \in \mathbb{N}_0$
I am currently struggling to understand where to start with this one. Thanks for any help in advance.
 A: First, note that it is enough to show that any such $f$ is strictly increasing, for then $f(f(n))<f(n+1)$ implies $f(n)<n+1$ and an easy induction shows that $f$ is the identity.
Since the image of $f$ is a non-empty set of natural numbers, it has a a smallest element, $m_0$.  Suppose that $f(n)=m_0$ for some $n>0$.  Then $n-1\in \mathbb{N}_0$, and we have $f(f(n-1))<f(n)=m_0$ which contradicts the definition of $m_0$.  However, $f(n)=m_0$ for some natural number $n$, so $f$ attains its minimum at, and only at, $n=0$.
For $k=1,2,\dots$, let $\mathbb{N}_k=\{n\in \mathbb{N}_0\mid n\geq k\}$, and let $f_k$ be the restriction of $f$ to $\mathbb{N}_k$.   I claim that the minimum value of $f_k$ is attained at, and only at $n=k$.  We have already proved the basis.  Suppose that $k>0$ and that the claim is true for $n=0,1,\dots,k-1$.  $f_k$ attains its minimum $m_k$ at some natural number $n\geq k$.  Suppose, by way of contradiction, that $n>k$.  Then $n-1\geq k$ and we have $f(f(n-1))<f(n)=m_k$.  To show that this is a contradiction, we have only to show that $f(n-1)\geq k$.  The induction hypothesis implies that $f(0), f(1), \dots, f(k-1)$ is an increasing sequence of natural numbers, so that $f(k-1)\geq k-1$.  By the induction hypothesis, $f_k$ attains its minimum only at $k-1$, so that $n-1\geq k$ implies $f(n-1)>f(k-1)\geq k-1$, which completes the proof.
I'd like to say a few words about your statement that you couldn't figure out where to start.  That gave me trouble, too.  I tried to start by proving $f(0)=0$, but all I could prove was that $f(n)\neq0$ for $n>0$.  For a short while, I tried to construct a counterexample, but I quickly became convinced that the statement is true.  So then I looked for a weaker condition that would imply the theorem.
A: Being an inductive proof, we start with the smallest number we can find.
In $\mathbb{N}_0$, the smallest number is $0$.
Hence the  first thing we want to show is that $f(0)=0$
You can start by thinking what would happen if $f(0) \neq 0$, considering that $f \circ f (n) < f(n+1) $ for all $n$.
(I will edit if I reach to go further, but the start of the proof should be in this direction)
