次: 問題と考え方 上: 数学的帰納法 前: 変形型数学的帰納法

複合命題と数学的帰納法

数学的帰納法はすべて， 何らかの自然数$n$を含む命題がすべての$n$で成立することを示すのだ． その命題が複合命題

$$条件\mathrm{P}が成立する．\quad \Rightarrow \quad 条件\mathrm{Q}が成立する．$$

であるときを考える．

例題 1.12  

$n\ge 2$ とする．$n$ 個の実数 $x_1,\ x_2,\ \cdots,\ x_n$ は $\vert x_i\vert<1\ (i=1,\ 2,\ \cdots n)$ をみたしている． このとき，

$$x_1+x_2+\cdots +x_n<x_1x_2\cdots x_n+n-1$$

がなり立つことを示せ．

考え方     この問題の $n$ と $x_1,\ x_2,\ \cdots,\ x_n$ は本来， 出題者の与えた定数であり，固定されている． しかし，ここで証明すべきことを次のような命題にする．

解答     次の命題を示せばよい．

$n\ge 2$ とする．$n$ 個の実数 $x_1,\ x_2,\ \cdots,\ x_n$が，条件 $\vert x_i\vert<1\ (i=1,\ 2,\ \cdots n)$ をみたすならば， 不等式

$$x_1+x_2+\cdots +x_n<x_1x_2\cdots x_n+n-1$$

がなり立つ．

これを数学的帰納法で示す．

1. $n=2$ のとき．
   
   $$x_1x_2+1-(x_1+x_2)=(x_1-1)(x_2-1)$$
   
   
   ここで $x_1-1<0,\ x_2-1<0$ ならば $(x_1-1)(x_2-1)>0$ よりつねに成立．
2. $n=k$ のとき成立するとする． $n=k+1$ のとき
   
   $$x_1x_2\cdots x_kx_{k+1}+k=x_1x_2\cdots (x_kx_{k+1})+k-1+1$$
   
   
   ここで $y_k=x_kx_{k+1}$ とすると $\vert y_k\vert<1$ である． $k$ 個の数 $x_1,\ \cdots,\ x_{k-1},\ y_k$に対して 帰納法の仮定を使うと
   
   $$x_1x_2\cdots x_{k-1}y_k+k-1+1>x_1+x_2+\cdots +y_k+1$$
   
   
   次に $n=2$ のときになり立つので
   
   $$y_k+1=x_kx_{k+1}+1>x_k+x_{k+1}$$
   
   
   あわせて
   
   $$x_1x_2\cdots x_kx_{k+1}+k>x_1+x_2+\cdots +x_k+x_{k+1}$$
   
   

3. したがって一般に $n$ のときに題意が示された．□

$n$個の実数の条件 $P(n)：\vert x_i\vert<1\ (i=1,\ 2,\ \cdots n)$ ， と， 条件 $Q(n)：x_1+x_2+\cdots +x_n<x_1x_2\cdots x_n+n-1$ がある．これからつくられた自然数$n$に関する条件

$$p(n)：P(n)\quad \Rightarrow \quad Q(n)$$

を考え，すべての自然数 $n$ に対して条件$p(n)$が成立することを示す．

このようにしておくと，数学的帰納法の仮定が， 個別の $x_i$ に対して仮定されるのではなく， 条件を満たす任意の $x_i$ に対して仮定されるので， 証明がずっとやりやすくなる． 「証明すべきことを強める」とか「個数に関する数学的帰納法」 とかいろいろ呼ばれる． 基本は自然数$n$を含む命題の成立を， $n$についての数学的帰納法で示すのである． 個別の $x_i$ とはいっても文字 $x_i$ であるから， もともとの命題そのものを強めた意味で 解釈することもできる． 要はどのような数学的帰納法をしているのか，明確に押さえることである．

例題 1.13       ［97東京工大改題］

$n$ を自然数， $r$ を正の有理数とする．このとき，

$$\displaystyle \sum_{k=1} ^n \frac{1}{x_k} =r$$

をみたす自然数の $x_k$ の組 $(x_1,x_2,\cdots,x_n)$ の個数は有限であることを示せ．

考え方     $n$ 個の未知数とある与えられた有理数 $r$に関する命題， を証明するのに，これを

$$r\ が有理数である． \quad \Rightarrow \quad n\ 個の未知数をもつ上の方程式の解が有限個である．$$

に証明内容を拡大し，数学的帰納法を適用する．

解答     「未知数の個数が $n$ であるかぎり， 任意の有理数 $r$ について，解の個数が有限個である」 ことを数学的帰納法で証明する.

まず，任意の有理数 $r$ に対して

$$\sum_{k=1} ^n \frac{1}{x_k} =r$$

をみたす自然数の $x_k$ の組 $(x_1,x_2,\cdots,x_n)$ で $x_1\le x_2 \le \cdots \le x_n$ となるものの個数が有限であることを数学的帰納法で示す．

1. $n=1$ のとき． $r\le 0$なら解なしなので、有限個であることは成立する．

   $r>0$とする． $r=\dfrac{1}{a}\ (a は自然数)$ という形をしているときは，
   

   $$\dfrac{1}{x_1}=\dfrac{1}{a}$$
   
   
   より $x_1=a$ のみが解である．解の個数は1．
   $r$ が自然数の逆数という形をしていないときは解なし．
   いずれにせよ解の個数は有限である．
2. $n=j$ のとき成立するとする．
   $\dfrac{1}{x_k}\le \dfrac{1}{x_1}$ であるから
   
   $$\displaystyle r=\sum_{k=1}^{j+1} \dfrac{1}{x_k}\le \dfrac{j+1}{x_1}$$
   
   
   よって $0< x_1 \le \dfrac{j+1}{r}$ となりこれを満たす整数 $x_1$ の個数は有限である． これを $x_1=a_1,\ a_2,\ \cdots ,\ a_N$ とする．各 $a_l$ に対し
   
   $$\displaystyle \sum_{k=2} ^{j+1} \frac{1}{x_k}=r-\dfrac{1}{a_l}$$
   
   
   は未知数の個数が $j$ 個なので帰納法の仮定により解の個数は有限である． $l=1,\ \cdots ,\ N$ のそれぞれについて言えるので， $n=j+1$ のときも解の個数は有限である．
3. 従って自然数 $n$ に対して
   
   $$\displaystyle \sum_{k=1} ^n \frac{1}{x_k} =r$$
   
   
   をみたす自然数の $x_k$ の組 $(x_1,x_2,\cdots,x_n)$ で $x_1\le x_2 \le \cdots \le x_n$ となるものの個数が有限であることが示された．

つぎに $x_1\le x_2 \le \cdots \le x_n$ という仮定をとる． するとそれらを並べ替えたものが解になる．その個数は $n$ 個がすべて異なるとき $n!$ 倍され， 同じものを含むときは$n!$ より小さい．いずれにせよ， $x_1\le x_2 \le \cdots \le x_n$ という仮定をとると，解の個数は高々有限数倍されるだけである．

従って，題意の有限性が証明された．□

このように, $n$ 以外にも定数などがある場合に，証明することを強めることによって， 帰納法がかえってうまくできることが少なくない．

次: 問題と考え方 上: 数学的帰納法 前: 変形型数学的帰納法