全ての自然数に対し、偶数の時は2で割り、奇数の時は1を足して２で割る操作を繰り返すと必ず1になることを証明せよ。
特に指定はなし。
(証明)
以下、自然数は0を含まないものとする。
どんな自然数nも、偶数のとき2で割り、奇数のとき1を足して2で割る操作を繰り返すと必ず1になることを示す。
数学的帰納法を用いる。
(1)n=1のとき、
真である。
(2)1<nのとき、
どんなn未満の自然数も条件を満たすとする。
(1)nが偶数のとき、n/2<nであるから真である。
(2)nが奇数のとき、(n+1)/2<nであるから真である。
(証明終)