数列が関わる証明法に数学的帰納法があります。\(n=1\)と\(n=k+1\)が成り立つことを証明することにより、すべての条件が成立すると証明できる方法が数学的帰納法です。

数学的帰納法を利用して証明するとき、実際に問題を解くことで慣れなければいけません。漸化式と同様に問題の解き方は決まっており、どのような仕組みによって証明できるのか学ぶ必要があります。

なお漸化式では応用問題を解かなければいけないケースもあります。数列や漸化式には難問がたくさん存在します。これは数学的帰納法も同様であり、応用問題は解くのが難しいです。そこで基本を利用し、応用問題を解けるようになりましょう。

それでは、どのように数学的帰納法を利用して証明すればいいのでしょうか。複数の例題を利用して、数学的帰納法の利用法を解説していきます。

数学的帰納法による証明の方法

ドミノをイメージすれば、数学的帰納法を理解できます。ドミノが倒れるためには、最初のきっかけが必要です。最初のドミノを倒せば、ドミノは最後まで倒れます。

ドミノと同じ概念が数学的帰納法です。数学的帰納法では、まず\(n=1\)のときに成り立つことを証明します。その後、\(n=k\)のときに成り立つと仮定し、\(n=k+1\)であっても成り立つことを証明します。これにより、以下のようになります。

  • \(n=1\)のときに成り立つ
  • \(n=1\)で成り立つため、\(n=2\)のときも成り立つ
  • \(n=2\)で成り立つため、\(n=3\)のときも成り立つ
  • \(n=3\)で成り立つため、\(n=4\)のときも成り立つ
  • ……

\(n=k+1\)であっても成り立つため、ドミノ倒しのようにすべての条件で成り立つことを証明できます。ただ最初のきっかけが必須であり、\(n=1\)のときに成り立つと証明できる必要があります。そのため、\(n=1\)と\(n=k+1\)のときに成り立つことを証明するのです。

基本的な数学的帰納法の計算

それでは、実際に数学的帰納法を用いて証明してみましょう。\(n\)が自然数のとき、数学的帰納法を用いて以下の等式を証明しましょう。

  • \(1^2+2^2+3^2+\)\(…+n^2\)\(=\displaystyle\frac{1}{6}n(n+1)(2n+1)\)

数列では、二乗の和の公式を覚えなければいけません。ただ、なぜこの公式が成り立つのか理解していない人は多いです。そこで、数学的帰納法を用いて証明しましょう。

・[1] \(n=1\)のときに成り立つと証明する

\(n=1\)を代入すると、以下のようになります。

\(\displaystyle\frac{1}{6}×1×2×3=1^2\)

こうして、\(n=1\)のときに成り立つと証明できました。

・[2] \(n=k\)のときに成り立つと仮定し、\(n=k+1\)であっても成り立つことを証明する

\(n=k\)のときに成り立つと仮定すると、式は以下のようになります。

  • \(1^2+2^2+3^2+\)\(…+k^2\)\(=\displaystyle\frac{1}{6}k(k+1)(2k+1)\)

そこで、\(n=k+1\)のときを考えましょう。

\(1^2+2^2+3^2+\)\(…+k^2\)\(+(k+1)^2\)

\(=\displaystyle\frac{1}{6}k(k+1)(2k+1)\)\(+(k+1)^2\)

\(=\displaystyle\frac{1}{6}(k+1)\{k(2k+1)+6(k+1)\}\)

\(=\displaystyle\frac{1}{6}(k+1)(2k^2+7k+6)\)

\(=\displaystyle\frac{1}{6}(k+1)(k+2)(2k+3)\)

左辺の\(n\)を\(k+1\)に変えることにより、右辺の\(n\)を\(k+1\)に変えたときの式を導き出すことができました。つまり、\(n=k+1\)のときも成り立ちます。[1]と[2]より、すべての自然数\(n\)で等式が成り立ちます。

漸化式で一般項を推測し、数学的帰納法によって証明する

数学的帰納法で漸化式を用いるケースもあります。この場合は数列の一般項を推測し、数学的帰納法によって式が成り立つことを証明しましょう。以下の問題の答えは何でしょうか。

  • \(a_1=2\)である数列\(\{a_n\}\)について、すべての自然数\(n\)に対して\(a_{n+1}=2-\displaystyle\frac{1}{a_n}\)を満たしています。\(a_2\)、\(a_3\)、\(a_4\)を計算し、一般項を推測した後、数学的帰納法によってその推測が正しいことを証明しましょう。

まず\(a_2\)、\(a_3\)、\(a_4\)を計算しましょう。

  • \(a_2=2-\displaystyle\frac{1}{2}=\displaystyle\frac{3}{2}\)
  • \(a_3=2-\displaystyle\frac{2}{3}=\displaystyle\frac{4}{3}\)
  • \(a_4=2-\displaystyle\frac{3}{4}=\displaystyle\frac{5}{4}\)

\(a_1=\displaystyle\frac{2}{1}\)と考えると、分母は\(n\)、分子は\(n+1\)であり、\(a_n=\displaystyle\frac{n+1}{n}\)と推測できます。それでは、この推測が正しいことを数学的帰納法を用いて証明しましょう。

・[1] \(n=1\)のときに成り立つと証明する

\(n=1\)のとき、\(a_1=\displaystyle\frac{1+1}{1}=2\)です。そのため、\(n=1\)のときに成り立ちます。

・[2] \(n=k\)のときに成り立つと仮定し、\(n=k+1\)であっても成り立つことを証明する

\(n=k\)のときに成り立つと仮定すると、式は以下のようになります。

  • \(a_k=\displaystyle\frac{k+1}{k}\)

そこで、\(a_k=\displaystyle\frac{k+1}{k}\)を\(a_{k+1}=2-\displaystyle\frac{1}{a_k}\)に代入しましょう。

\(a_{k+1}=2-\displaystyle\frac{1}{a_k}\)

\(a_{k+1}=2-\displaystyle\frac{k}{k+1}\)

\(a_{k+1}=\displaystyle\frac{k+2}{k+1}\)

こうして、\(n=k+1\)のときも成り立ちます。[1]と[2]より、一般項は\(a_n=\displaystyle\frac{n+1}{n}\)です。

数学的帰納法を用いた不等式の証明

次に、不等式を含む場合の証明方法を学びましょう。不等式を証明する方法としては、引き算を利用します。例えば\(a>b\)を証明したい場合、\(a-b>0\)であると示せばいいです。そこで、以下の問題を解きましょう。

  • 自然数\(n\)が\(n≧5\)を満たすとき、\(n^2<2^n\)を満たすことを証明しましょう。

\(n^2<2^n\)を証明するためには、\(0<2^n-n^2\)を証明すればいいです。そこで、以下のように数学的帰納法を用いて証明しましょう。

・[1] \(n=5\)のときに成り立つと証明する

\(0<2^5-5^2\)

\(0<32-25\)

\(0<7\)

そのため、\(n=5\)のときに不等式は成り立ちます。

・[2] \(n=k\)のときに成り立つと仮定し、\(n=k+1\)であっても成り立つことを証明する

\(n=k\)（\(k≧5\)）のときに成り立つと仮定すると、式は\(k^2<2^k\)となります。そこで\(n=k+1\)のときを考えて\((k+1)^2<2^{k+1}\)、つまり\(0<2^{k+1}-(k+1)^2\)を証明しましょう。

\(2^{k+1}-(k+1)^2\)

\(=2·2^k-(k+1)^2\)

なお\(k^2<2^k\)が成り立つと仮定しているため、以下の不等式を作れます。

\(2·k^2-(k+1)^2<2·2^k-(k+1)^2\)

そのため\(0<2·k^2-(k+1)^2\)を証明できれば、\(0<2·k^2-(k+1)^2\)\(<2^{k+1}-(k+1)^2\)となるため、\(0<2^{k+1}-(k+1)^2\)を証明できます。そこで、\(2·k^2-(k+1)^2\)に着目して式を変形しましょう。

\(2·k^2-(k+1)^2\)

\(=k^2-2k-1\)

\(=(k-1)^2-2\)

\(k≧5\)であるため、\(y=(k-1)^2-2\)で\(y\)は必ず正の値になります。そのため\(k≧5\)のとき、\(0<2·k^2-(k+1)^2\)です。こうして、以下の関係が成り立ちます。

\(0<2·k^2-(k+1)^2\)\(<2^{k+1}-(k+1)^2\)

\(0<2^{k+1}-(k+1)^2\)

\((k+1)^2<2^{k+1}\)

つまり、\(n=k+1\)のときも成り立ちます。[1]と[2]より、\(n≧5\)を満たすすべての自然数\(n\)で不等式が成り立ちます。今回の証明問題では\(n=1\)ではなく、\(n=5\)がスタート地点です。この場合であっても、[1]を\(n=5\)に設定することで証明できます。

\(n=k+2\)を示して証明を行う数学的帰納法

ここまで、基本的な数学的帰納法について解説してきました。ただ場合によっては、\(n=k+1\)を示すだけでは証明できないケースがあります。この場合、\(n=k+1\)だけでなく、\(n=k+2\)の場合も示しましょう。つまり\(n=k+1\)に加えて、\(n=k+2\)のときも成り立つことを証明するのです。

方法は以下になります。

  • \(n=1\)と\(n=2\)のときに成り立つと証明する。
  • \(n=k\)と\(n=k+1\)のときに成り立つと仮定し、\(n=k+2\)であっても成り立つことを証明する。

この場合、以下のようになります。

  • \(n=1\)と\(n=2\)のときに成り立つ
  • \(n=1\)で成り立つため、\(n=3\)のときも成り立つ
  • \(n=2\)で成り立つため、\(n=4\)のときも成り立つ
  • \(n=3\)で成り立つため、\(n=5\)のときも成り立つ
    ……

こうして、すべての自然数\(n\)で成り立つと証明できます。それでは、以下の問題を解いてみましょう。

  • \(x\)と\(y\)について、\(x+y\)と\(xy\)が整数の場合、\(x^n+y^n\)が整数であることを証明しましょう。なお、\(n\)は自然数です。

数学的帰納法を利用することによって証明します。このとき、\(x^k+y^k\)を用いて\(x^{k+1}+y^{k+1}\)を表すと以下のようになります。

  • \(x^{k+1}+y^{k+1}=(x^k+y^k)(x+y)\)\(-(x^{k-1}+y^{k-1})xy\)

ただ\(x^{k-1}+y^{k-1}\)が整数かどうかわからないため、証明することができません。そこで一つ前だけでなく、二つ前も仮定する必要があるのです。実際の証明法は以下になります。

・[1] \(n=1\)と\(n=2\)のときに成り立つと証明する

\(n=1\)のとき、\(x^1+y^1=x+y\)であるため整数です。また\(n=2\)のとき、\(x^2+y^2\)\(=(x+y)-2xy\)であるため整数です。

・[2] \(n=k\)と\(n=k+1\)のときに成り立つと仮定し、\(n=k+2\)であっても成り立つことを証明する

\(n=k\)と\(n=k+1\)のときに成り立つと仮定すると、\(x^k+y^k\)と\(x^{k+1}+y^{k+1}\)は整数です。

なお、仮定するときに\(n=k-1\)と\(n=k\)を用いると、\(n\)は自然数であるため、\(k-1≧1\)となります。つまり\(k≧2\)となるため、これを避けるために\(n=k\)、\(n=k+1\)と仮定します。

次に、\(n=k+2\)のときを考えましょう。そうすると、式は以下のようになります。

  • \(x^{k+2}+y^{k+2}=(x^{k+1}+y^{k+1})(x+y)\)\(-(x^k+y^k)xy\)

\(x+y\)と\(xy\)は整数であり、仮定より\(x^k+y^k\)と\(x^{k+1}+y^{k+1}\)も整数です。そのため、\(x^{k+2}+y^{k+2}\)は整数です。[1]と[2]より、すべての自然数\(n\)で\(x^{k+2}+y^{k+2}\)は整数です。

数学的帰納法を利用して証明する

数列や漸化式の知識を利用することにより、証明する方法が数学的帰納法です。最初が成り立つことを証明した後、\(n=k+1\)が成り立つと証明すれば、ドミノ倒しと同様にすべてを証明できます。これが数学的帰納法の原理です。

基本となる数学的帰納法では、\(n=1\)と\(n=k+1\)を証明すればいいです。ただ応用問題では、ほかの方法を利用しなければいけないこともあります。

例えば\(a>b\)を証明したい場合、両辺の差を利用して、\(a-b>0\)を証明しましょう。また\(n=k+1\)を用いても証明できない場合、\(n=k+2\)も利用して、一つ前だけでなく二つ前も仮定しましょう。

実際に例題を解かないと、数学的帰納法を利用しての証明はできません。そこで問題を解き、数学的帰納法を利用できるようになりましょう。