数学的帰納法

「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\) について成り立つ．

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