1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – sato
    Feb 18, 2021 at 3:23

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Can you explain the last step? How did you go from f(i +1) > i to i + 1 $\leq$ f(1 + i) $\endgroup$
    – Beaba
    Feb 18, 2021 at 3:39
  • $\begingroup$ 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$. $\endgroup$
    – atzlt
    Feb 18, 2021 at 3:45
  • $\begingroup$ Sorry, I am learning proofs right now so it was not obvious yet. Very clear explanation, thank you. $\endgroup$
    – Beaba
    Feb 18, 2021 at 3:48
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .