TITLE: Strictly Increasing Function, $x \leq f(x)$ on the naturals
QUESTION [1 upvotes]: Show that for a strictly increasing function $f: \mathbb{N} \rightarrow \mathbb{N}$, we have that $x \leq f(x)$ for all $x \in \mathbb{N}.$
I am trying to prove by induction, however, I am not sure if it is the right path.

REPLY [4 votes]: When $x=0$, because $f(x)\in\mathbb{N}$, $f(x)\geq0=x$, therefore $x\leq f(x)$.
If $i\leq f(i)$ for some $i\in\mathbb{N}$, then $f(i+1)>f(i)\geq i\implies f(i+1)>i;\quad\because f(i+1)\in\mathbb{N},\quad\therefore f(i+1)\geq i+1$.

REPLY [1 votes]: We have that $f(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$ and $f(n) < f(n + 1),$ (i.e. $f(n) + 1 \leq f(n + 1)$). In particular, $f(1) \geq 1.$ It follows that for $n > 1,$ $f(n) \geq f(n - 1) + 1 \geq f(n - 2) + 2 \geq \dots \geq f(1) + n - 1 \geq 1 + n - 1 = n,$ so $f(n) \geq n$ for all $n \in \mathbb{N}.$ I hope this helps. :)
{"set_name": "stack_exchange", "score": 1, "question_id": 4029998}