# Strictly Increasing Function, $x \leq f(x)$ on the naturals [closed]

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.

• Isn't it like obvious that if a function is strictly increasing, the value of $x$ for some $f(x)$ will be $\ge x$? For example $f(x)=x+k, k > 0$.
– sato
Feb 18, 2021 at 3:23

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$$.

• Can you explain the last step? How did you go from f(i +1) > i to i + 1 $\leq$ f(1 + i) Feb 18, 2021 at 3:39
• I think that's obvious... well, if you really don't understand: $f(i+1)$ is an integer, and $f(i+1)>i$, so $f(i+1)-i>0$. $f(i+1)-i\in\mathbb{N}$, then $f(i+1)-i\geq1$, so $f(i+1)\geq i+1$. Feb 18, 2021 at 3:45
• Sorry, I am learning proofs right now so it was not obvious yet. Very clear explanation, thank you. Feb 18, 2021 at 3:48

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. :)