数学的帰納法

「2の奇数乗を3で割った余りは2」
を前回の記事で，2項定理を使ってゴリゴリやる方法と，合同式を使ったスマートな方法でやってみた．＞以前の記事
が，もう一つ，induction でもいいな．こっちも「ごりごり」に比べれば多少簡潔．

正の奇数 $q$ に対して $2^q$ を 3で割ると余り2の証明
$q=2n-1$ とする．
$n=1$のとき，$q=1$ より $2^1=2$ を3で割ると余り2より成り立つ．
nのとき成り立つと仮定すると，
$2^{2n-1}=3k+2$（$k$は整数）
と表せる．
両辺 4 倍すると，
$4\times2^{2n-1}=4\times(3k+2)$
$2^{2n+2-1}=12k+8$
$2^{2(n+1)-1}=12k+6+2=3(4k+2)+2$
より，n+1のときも3で割って2余る．
したがって，すべての $n$ について成り立つ．

＞数学的帰納法に関する記事