§B1.6数学的帰納法

証明. 各正の整数$j$に対して、主張$Q(j)$を$P(m+j-1)$と定める。$Q(1)$は$P(m)$であり、条件 (a)により成り立つ。

正の整数$j$を取り、$k=m+j-1$とおく。$k$は$m$以上の整数であり、$Q(j)$は$P(k)$、$Q(j+1)$は$P(k+1)$であるから、条件 (b)により、$Q(j)$が成り立つならば$Q(j+1)$が成り立つ。

したがって§A3.10 定理 1.1を$Q$に適用すると、すべての正の整数$j$について$Q(j)$が成り立つ。$m$以上の整数$n$は$j=n-m+1$によって$n=m+j-1$と表されるから、$P(n)$が成り立つ。▨

証明.$n$についての数学的帰納法で示す。示す主張$P(n)$は上の等式である。

出発点は$n=1$である。左辺は$1$、右辺は$\dfrac{1\cdot 2}{2} = 1$であり、両辺は一致する。

正の整数$k$を取り、$n=k$のときの主張

が成り立つと仮定する。$n=k+1$のときの主張の左辺は$1+2+\cdots+k+(k+1)$である。この式の$1+2+\cdots+k$の部分に、仮定した等式を用いると

である。最初の等号で仮定を用いた。右端の式は$n=k+1$のときの主張の右辺であるから、$n=k+1$のときの主張が成り立つ。

定理 1.1により、すべての正の整数$n$について等式が成り立つ。▨

証明.$h$を$h>-1$を満たす実数として固定し、$n$についての数学的帰納法で示す。

出発点は$n=1$である。左辺は$1+h$、右辺は$1 + 1\cdot h = 1+h$であり、等号が成り立つ。

正の整数$k$を取り、$n=k$のときの主張$(1+h)^{k} \ge 1+kh$が成り立つと仮定する。条件$h>-1$から$1+h > 0$であるから、この不等式の両辺に$1+h$を掛けても不等号の向きは変わらない。したがって

である。ここの不等号で、仮定した$n=k$のときの主張と、$1+h>0$であることの両方を用いた。$k$は正の整数であり$h^{2}$は$0$以上であるから$kh^{2} \ge 0$であり、

である。二つを合わせると$(1+h)^{k+1} \ge 1+(k+1)h$となり、$n=k+1$のときの主張が成り立つ。

定理 1.1により、すべての正の整数$n$について不等式が成り立つ。

次に、等号が成り立つ場合を調べる。$n=1$のときは両辺とも$1+h$であり、$h=0$のときは両辺とも$1$であるから、いずれの場合も等号が成り立つ。逆に$n \ge 2$かつ$h \ne 0$とする。上で示した$(1+h)^{k+1} \ge (1+kh)(1+h)$を$k = n-1$について読むと

である。$n-1 \ge 1$と$h^{2} > 0$から$(n-1)h^{2} > 0$であるから、$(1+h)^{n} > 1+nh$であり、等号は成り立たない。よって等号が成り立つのは、$n=1$の場合と$h=0$の場合に限る。▨

証明.$n$についての数学的帰納法で示す。

出発点は$n=1$である。$1^{3}-1 = 0$であり、$0 = 6\cdot 0$であるから$6$の倍数である。

正の整数$k$を取り、$n=k$のときの主張、すなわち$k^{3}-k$が$6$の倍数であることを仮定する。このとき、ある整数$c$によって$k^{3}-k = 6c$と書くことができる。$n=k+1$のときの式を展開すると

である。最後の等号で仮定を用いた。$k$と$k+1$は連続する二つの整数であるから、一方は偶数であり、積$k(k+1)$は偶数である。そこで、ある整数$d$によって$k(k+1) = 2d$と書くことができ、$3k(k+1) = 6d$である。したがって

であり、$c+d$は整数であるから、$n=k+1$のときの主張が成り立つ。

定理 1.1により、すべての正の整数$n$について$n^{3}-n$は$6$の倍数である。▨

証明.$n$についての数学的帰納法で示す。定理 1.1を$m=5$として用いる。

出発点は$n=5$である。$2^{5} = 32$、$5^{2} = 25$であり、$32 > 25$である。

$5$以上の整数$k$を取り、$n=k$のときの主張$2^{k} > k^{2}$が成り立つと仮定する。両辺に正の数$2$を掛けても不等号の向きは変わらないので

である。ここの不等号で仮定を用いた。あとは$2k^{2} \ge (k+1)^{2}$を示せば結論が従う。差を取ると

であり、$k \ge 5$から$(k-1)^{2} \ge 16$であるから$(k-1)^{2} - 2 \ge 14 > 0$である。よって$2k^{2} > (k+1)^{2}$であり、$2^{k+1} > (k+1)^{2}$が成り立つ。

定理 1.1により、$5$以上のすべての整数$n$について$2^{n} > n^{2}$が成り立つ。▨

証明.$m$以上の各整数$n$に対して、「$P(n)$と$P(n+1)$がともに成り立つ」という主張を$Q(n)$と置く。

条件 (a)により、$Q(m)$が成り立つ。

$m$以上の整数$k$を取り、$Q(k)$が成り立つと仮定する。すなわち、$P(k)$と$P(k+1)$がともに成り立つ。このとき条件 (b)により$P(k+2)$が成り立つ。$P(k+1)$と$P(k+2)$がともに成り立つので、$Q(k+1)$が成り立つ。

定理 1.1を主張$Q$に適用すると、$m$以上のすべての整数$n$について$Q(n)$が成り立つ。$Q(n)$は$P(n)$が成り立つことを含むので、$m$以上のすべての整数$n$について$P(n)$が成り立つ。▨

証明.定理 6.1を$m=1$として用いる。示す主張$P(n)$は$a_{n} = 3\cdot 2^{\,n-1} - 2$である。

出発点を二つ確かめる。$n=1$では$3\cdot 2^{0} - 2 = 1$であり、$a_{1} = 1$と一致する。$n=2$では$3\cdot 2^{1} - 2 = 4$であり、$a_{2} = 4$と一致する。

正の整数$k$を取り、$n=k$のときの主張$a_{k} = 3\cdot 2^{\,k-1} - 2$と、$n=k+1$のときの主張$a_{k+1} = 3\cdot 2^{\,k} - 2$がともに成り立つと仮定する。漸化式に、仮定した二つの等式を代入すると

である。二つめの等号で、仮定した二つの主張の両方を用いた。$6\cdot 2^{\,k} = 3\cdot 2^{\,k+1}$であるから$a_{k+2} = 3\cdot 2^{\,(k+2)-1} - 2$であり、$n=k+2$のときの主張が成り立つ。

定理 6.1により、すべての正の整数$n$について$a_{n} = 3\cdot 2^{\,n-1} - 2$が成り立つ。▨