1

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

Michael Hardy
  • 1
Kyle
  • 25
  • Sketch of Proof: Let $m\in\mathbb{N}$. We can see that the operation for even iterates decreases the next output by a multiple $1/2$ whereas the operation for odd iterates increases the next output by $1$. The even operation will decrease the original number more than the adding ect... Its rough but that can be made precise and is not difficult to show. The Collatz problem is a while different animal. – Joseph Zambrano Mar 12 '14 at 04:19

1 Answers1

2

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.

Joseph Zambrano
  • 1,237