# Find the bound of the function [closed]

Let $$f : \mathbb{N} \rightarrow \mathbb{N}$$ be a function satisfying $$y < f(x+1) \rightarrow y < f(x)$$ for every $$x, y \in \mathbb{N}$$. Show that this function is bounded and determine the bound.

• Is this an original puzzle? Apr 22, 2021 at 18:34
• @bobble Yes. This was a sub-problem of a proof I was recently doing. Apr 22, 2021 at 18:51

the given statement $$f(x+1)>y \Rightarrow f(x)>y \forall x,y\in\mathbb N$$ is equivalent to $$f(x+1) \le y \Leftarrow f(x) \le y \forall x,y\in\mathbb N$$. It is now obvious and easily verified by induction that $$f(0)$$ is a (sharp) upper bound.

Similar to Jaap's answer, but without the risk of a $$-1 \notin \mathbb{N}$$ appearing:

Always choose $$y = f(x)$$. Then the condition becomes $$\forall x \in \mathbb{N}. f(x) < f(x+1) \rightarrow f(x) < f(x)$$. The conclusion of that is always false, which means that its premise must always be false too, so we know $$\forall x \in \mathbb{N}. f(x) \ge f(x+1)$$. A trivial induction then shows that $$\forall x \in \mathbb{N}. f(0) \ge f(x)$$, so $$f(0)$$ is our upper bound.

Here is a simple proof:

Applying the given statement to $$y=f(x+1)-1$$ we deduce that $$f(x+1) < f(x)+1$$ for all $$x$$. Since $$f$$ is an integer-valued function we get $$f(x+1) \le f(x)$$ for all x.
$$f$$ is therefore a decreasing function, which is obviously bounded above by the value at its left-most point, $$f(0)$$.

• What if $f(x+1)=0$ and so $f(x+1)-1=-1\notin \mathbb{N}$? Apr 22, 2021 at 19:31
• @RobPratt Good point. If the function has some point where $f(x+1)>0$ my argument works for all smaller x. It does not work on the tail of $f$ where it is 0, but that part of $f$ is still below the established bound. Apr 22, 2021 at 20:07