자연계열 1-2번

<나>주어진 자연수 $\displaystyle m$에 대하여 다음과 같이 귀납적으로 정의된 수열 $\displaystyle {a_n}$이 있다.1) $\displaystyle a_1=m$2) $\displaystyle a_{n+1}=\begin{cases}a_n+1&(a_n\text{이 홀수})\\\frac{a_n}2&(a_n\text{이 짝수})\end{cases}$

예를 들어 $\displaystyle m=19$인 경우, 수열 $\displaystyle {a_n}$은 $\displaystyle 19,20,10,5,6,3,4,2,1,2,1,\cdots$이다.

수열 $\displaystyle {a_n}$의 정의로부터 각 항은 자연수이다. 또한 제$\displaystyle k$항이 $\displaystyle 1$인 경우, 그 다음 항들은$\displaystyle 2,1,2,1,\cdots$으로 $\displaystyle 2$와 $\displaystyle 1$이 교대로 반복되어 나타남을 알 수 있다.

위와 같이 정의된 수열 $\displaystyle {a_n}$에 대하여 $\displaystyle a_k=1$인 자연수 $\displaystyle k$가 항상 존재한다는 것을 보이자. $\displaystyle a_n>2$인 $\displaystyle n$에 대하여 $\displaystyle a_n>a_{n+2}$이 성립함을 다음과 같이 확인할 수 있다.

$\displaystyle a_n$이 짝수이면 $\displaystyle a_{n+1}=\frac{a_n}2$이고, $\displaystyle a_{n+2}\le a_{n+1}+1$이 성립한다. $\displaystyle a_n>2$이므로$\displaystyle a_{n+2}\le a_{n+1}+1=\frac{a_n}2+1<a_n$이다. $\displaystyle a_n$이 홀수이면 $\displaystyle a_n=2l+1$ ($\displaystyle l$은 자연수)로 쓸 수 있고, $\displaystyle a_{n+1}=2l+2$가 짝수이므로$\displaystyle a_{n+2}=\frac{a_{n+1}}2=l+1$이 되어 $\displaystyle a_n>a_{n+2}$이다. 그러므로 $\displaystyle a_n>2$인 $\displaystyle n$에 대하여 $\displaystyle a_n>a_{n+2}$이다.

지금까지의 논의를 이용하면 $\displaystyle a_k=1$인 자연수 $\displaystyle k$가 존재함을 다음과 같이 보일 수 있다. $\displaystyle a_n>2$인 $\displaystyle n$에 대하여 $\displaystyle a_n>a_{n+2}$이므로, $\displaystyle a_h\le2$를 만족시키는 자연수 $\displaystyle h$가 존재한다. $\displaystyle a_h=1$인 경우 $\displaystyle k=h$로 하고, $\displaystyle a_h=2$인 경우 $\displaystyle k=h+1$로 하면 $\displaystyle a_k=1$이다.

1) $\displaystyle b_1=m$

2) $\displaystyle b_{n+1}=\begin{cases}2b_n-2&(b_n\text{이 홀수})\\\frac{b_n}2&(b_n\text{이 짝수})\end{cases}$