0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is this an original puzzle? $\endgroup$
    – bobble
    Apr 22, 2021 at 18:34
  • $\begingroup$ @bobble Yes. This was a sub-problem of a proof I was recently doing. $\endgroup$
    – Léreau
    Apr 22, 2021 at 18:51

3 Answers 3

3
$\begingroup$

By elementary logic

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ What if $f(x+1)=0$ and so $f(x+1)-1=-1\notin \mathbb{N}$? $\endgroup$
    – RobPratt
    Apr 22, 2021 at 19:31
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 22, 2021 at 20:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.