In the $x + 1$ problem, does every positive integer $x$ eventually reach $1$?

Question

I know that the more famous $3x + 1$ problem is still unresolved. But it seems to me like the similar $x + 1$ problem, with the function

$$f(x) = \begin{cases} x/2 & \text{if } x \equiv 0 \pmod{2} \\ x + 1 & \text{if } x \equiv 1 \pmod{2}.\end{cases}$$

should be very easy to prove it with just my modest, haphazardly obtained knowledge of mathematics. But the only thing I can think of is "of course every $x$ has to reach $1$," which is clearly not a rigorous proof.

Is this easy to prove, or is it perhaps just as difficult as the $3x + 1$ problem?

Answer 1

This question is not too hard to resolve if we look at $f(f(x))$. We have $$f(f(x))=\left\{\begin{array} \displaystyle{\tfrac{x}{4}} &\text{ if }x\equiv0\pmod{4}\\ \tfrac{x}{2}+1&\text{ if }x\equiv2\pmod{4}\\ \tfrac{x}{2}+\tfrac{1}{2}&\text{ if }x\equiv1\pmod{2} \end{array}\right.$$ In particular, we see that $f(f(x))<x$ if $x>3$. So for all $x>3$, eventually we will end up at an integer that is at most $3$. Then we can finish by checking that $$f(2)=1\qquad\text{ and }\qquad f(f(f(3)))=1.$$ So every integer $x$ eventually ends up at $1$. A similar approach works if you replace $x+1$ by $ax+b$ with $a\leq2$ and any $b>0$, though there are more numbers to check by hand for large $b$.

Answer 2

The variant you have described is not hard. For example one can give a formal proof by strong induction.

Here is the induction step. Suppose that we ultimately end up at $1$ if we start at any number $u\lt k$. We show that we end up at $1$ if we start at $k$.

If $k$ is even, in one step we are below $k$, and we are finished.

If $k$ is odd and greater than $1$, in two steps we are at $\frac{k+1}{2}\lt k$.