Modified Collatz Problem

Question

How can one prove for all $n \in \mathbb N$ that the following sequence always results in $1$: Choose $m$ $x_1 = m$ $$x_{n+1} = \begin{cases} x_n/2 & \text{if $x_n$ is even} \\ \\ x_n + 1 & \text{if $x_n$ is odd} \end{cases}$$

Answer 1

I decided that its just easier to post the full proof:

Every natural number $m$ can be written as $m=2^k(2j+1)$ where $j,k$ are positive integers. Iterating $m$ we see it takes exactly $k$ iterations to arrive at $(2j+1)$ which is clearly odd hence the next iterate is $2j+2$ then $j+1$. Now it is easy to show that $j+1<2^k(2j+1)$ and $j+1$ is also a natural number hence can be written in the form stated earlier. Repeating the process will again result in a smaller natural number however, the naturals are bounded below by $1$ and hence the process must terminate. To show it ends at $1$ requires a little work but is also easy.