Hailstone-2.9

\begin{equation} f(x) = \left\{ \begin{array}{lr} x+1 , & \text{if } x{\equiv}1\;(mod\;2)\\ \frac{x}{2}, & \text{if } x{\equiv}0\;(mod\;2)\end{array} \right\}\end{equation}

명제 $p$ : 모든 자연수에 대해 함수를 $m$번 반복해서 $1$에 도달하게 할 수 있다.

증명을 해보자.

 

$sol.1$

모든 자연수가 자기 자신보다 작아질 수 있다는 것을 증명하자.

2가 자기 자신보다 작아지면 1이 되면서 부합하고, 3이 자기 자신보다 작아지면 2를 경유하여 1에 도달하게 된다.

$x>{\frac{x+1}{2}}\;{\Leftrightarrow}\;x>1$

$x>{\frac{x}{2}}$

따라서 x=1인 경우만 해보면 된다.

$sol.2$

$x=1$일 때만 해봐도 되는 것을 보이자.

Hailstone-3의 글에 있는 Theorem 3를 참고하면 된다.