投稿者: 数学的帰納法
「n=1のときをなくせる」というとキャッチーですが, 要するに自明に成り立つ形に変わるだけです.
よくみる数学的帰納法は以下の形です。
\(\mathbb{N}\)に関する命題\(\varphi\)について,
(1) \(\varphi(1)\)が成り立つ,
(2) \(\varphi(k)\)が成り立つならば\(\varphi(k+1)\)が成り立つ,
が共に示せたとき, 任意の\(n \in \mathbb{N}\)について\(\varphi(n)\)が成り立つ.
これと同値な命題として次があります.
\(\mathbb{N}\)に関する命題\(\varphi\)について,
\(n\)未満のすべての\(k\)で\(\varphi(k)\)が成り立つならば\(\varphi(n)\)が成り立つ,
が示せたとき, 任意の\(n \in \mathbb{N}\)について\(\varphi(n)\)が成り立つ.
この２つの同値性はあまり難しくないのでお任せするとして, ２つ目の数学的帰納法を論理式に直してみると面白いことがわかります.
論理式で表すと
論理式で書くと,
\( \forall n \Big( \big( \forall k < n \varphi(k) \big) \rightarrow \varphi(n) \Big) \rightarrow \big( \forall j \varphi(j)\big) \)
特に, \(\forall k < n \varphi(k)\)の部分に注目します.
\(\forall k < n \varphi(k) \iff \forall k \big[ (k < n) \rightarrow \varphi(k) \big]\),
となります（\(\forall k < n \varphi(k)\)の定義ですが意味を考えれば明らかでしょう）.
ところで, 自然数が\(1\)から始まるとしたとき \(n = 1\)とすると\(k < n\)を満たす\(k\)は存在しません.
したがって, \((k < n) \rightarrow \varphi(k) \)は左が真とならないので全体が真となります.
すなわち, \(n = 1\)のときだけ分けて証明する必要がありません.
見通しの良い方を使う
証明したい命題によってどちらの形を使った方が便利なのかは変わります.
たとえば, 論理式の長さについての帰納法を使うときには,
\( \varphi \equiv \psi_1 \land \psi_2, \)
のように論理式を２つに分けて証明することがあります．
このとき，\(\psi_1, \psi_2\)の長さはわかりません. ただし, \(\varphi\)よりは短い（つまり\(n\)未満）であることはわかります．
こういう場合は後者の帰納法の方が便利です.