数学的帰納法例2

すべての自然数 n について，
4²ⁿ⁺¹ + 3ⁿ⁺² は 13 の倍数であることを証明せよ。

[1]
結論: n = 1 のとき成り立つ。

推論：

$4^{3}+3^{3}=64+27=91=13\times 7$

n = 1 のとき成り立つことがいえた。

[2]
仮定: n = k のとき成り立つ。
i.e.

$4^{2k+1}+3^{k+2}=13m$ … ① なる整数 m がある。
結論: n = k+1 のとき成り立つ。
i.e.

$4^{2k+3}+3^{k+3}$ = 13× (整数) と表せる。

推論：

$4^{2k+3}+3^{k+3}$

$=16\times 4^{2k+1}+3\times 3^{k+2}$

$=16(13m-3^{k+2})+3\times 3^{k+2}$ … ① を用いた。

$=13(16m-3^{k+2})$
ここで 16m - 3^k+2 は整数である。

n = k のとき成り立つと仮定すると， n = k+1 のとき成り立つことがいえた。