Mathematical induction

A method for proving or defining a proposition involving variables over natural numbers by focusing on certain properties of the natural numbers. When p ( x ) is a predicate about the natural number x , it is known that the property of natural numbers is that "if p (1) is true, and if for any natural number k , then if p ( k ), then p ( k +1), then for all natural numbers n , then p ( n )." A proof or definition that uses this is called a proof by mathematical induction, and a definition by mathematical induction (inductive definition).

for example,

To prove that the above holds true, we can say that "when n = 1, both the left and right sides are 1, so the above holds true." Furthermore, we can say that "when n = k , the above holds true,

and also holds for n = k + 1."

Next, let us define a sequence { a _n } by mathematical induction. When n = 1, define a _n as 1, that is, a ₁ = 1. Assume that a _k is defined when n = k , and define a k ₊₁ = a _k · ( k + 1) when n = k + 1. This kind of definition by induction is as follows:

A sequence by this definition is usually written as
a ₁ =1, a ₂ =1・2=2, a ₃ =2・3=6,
a ₄ =6・4=24, a ₅ =24・5=120, ……,
a _n =1・2・3・4・……・( n −1)・n (= n !),……
To see that the sequence { a _n } is defined using this method, consider the proposition p ( n ) that "the n-th term of the sequence a _n is defined."

There are various forms of mathematical induction, such as "For any natural number k , if p ( m ) then p ( k +1) for all natural numbers m ≦ k , then p ( n ) is true for all natural numbers n ." The name of mathematical induction comes from the fact that its form is very similar to "induction," and its content is a type of "deduction" since it examines all of the objects. For this reason, it is also called complete induction.

[Ken Hirose]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

自然数上の変数を含む命題に対し、自然数のある性質に着目して、その命題を証明、あるいは定義するための手法をいう。p(x)を自然数xについての述語とするとき、自然数の性質として、「p(1)が成り立ち、かつ、任意の自然数kについてp(k)ならばp(k＋1)である、が成立すれば、すべての自然数nについてp(n)である」が成り立つことが知られている。このことを用いた証明あるいは定義が、数学的帰納法による証明であり、数学的帰納法による定義（帰納的定義）である。

　たとえば、

が成立することの証明には、「n＝1のときには、左辺、右辺とも1となって成立する」。さらに、「n＝kのとき成立すると仮定すると、

となって、n＝k＋1の場合も成立する」ことで十分である。

　次に、ある数列｛a_n｝を数学的帰納法によって定義してみよう。n＝1のとき、a_nを1、すなわち、a₁＝1と定義し、n＝kのときa_kが定義されていると仮定して、n＝k＋1のとき、a_k+1＝a_k・(k＋1)と定義する。このような帰納法による定義は、

と書くのが普通である。この定義による数列は、
　　a₁＝1, a₂＝1・2＝2, a₃＝2・3＝6,
　　a₄＝6・4＝24, a₅＝24・5＝120, ……,
　　a_n＝1・2・3・4・……・(n－1)・n(＝n！),……
となる。この方法によって数列｛a_n｝が定義されていることは、「数列の第n項a_nが定義される」という命題p(n)を考えてみればよい。

　数学的帰納法には、「任意の自然数kについて、m≦kなるすべての自然数mに対しp(m)ならばp(k＋1)である、が成立すれば、すべての自然数nについてp(n)が成立する」など、いろいろな形式のものがある。なお、数学的帰納法は、その形式が「帰納」にきわめて似通っていることからきた名称で、内容は、対象のすべてを調べるのであるから、「演繹(えんえき)」の一種である。このため、完全帰納法ともよばれる。

［廣瀬　健］

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例