数学的帰納法
Mathematical inductionは、結果を証明したり、自然数のステートメントを確立したりするための手法です。このパートでは、さまざまな例を通じてこの方法を説明します。
定義
Mathematical Induction は、ステートメント、式、または定理がすべての自然数に当てはまることを証明するために使用される数学的手法です。
この手法には、以下に示すように、ステートメントを証明するための2つのステップが含まれます。
Step 1(Base step) −初期値に対してステートメントが真であることを証明します。
Step 2(Inductive step)−ステートメントがn番目の反復（または数n）に当てはまる場合、（n + 1）番目の反復（または数n + 1）にも当てはまることを証明します。
どうやるか
Step 1−ステートメントが真である初期値を検討します。n =初期値の場合にステートメントが真であることを示します。
Step 2− n = kの任意の値に対してステートメントが真であると想定します。次に、ステートメントがn = k +1に対して真であることを証明します。実際には、n = k + 1を2つの部分に分割し、一方の部分はn = k（すでに証明済み）であり、もう一方の部分を証明しようとします。
問題1
$ 3 ^ n-1 $は、n = 1、2、..の場合、2の倍数です。
Solution
Step 1 − $ n = 1の場合、3 ^ 1-1 = 3-1 = 2 $は、2の倍数です。
Step 2 − $ n = k $に対して$ 3 ^ n-1 $が真であると仮定します。したがって、$ 3 ^ k -1 $が真です（これは仮定です）
$ 3 ^ {k + 1} -1 $も2の倍数であることを証明する必要があります
$ 3 ^ {k + 1} -1 = 3 \ times 3 ^ k-1 =（2 \ times 3 ^ k）+（3 ^ k-1）$
最初の部分$（2 \ times 3k）$は2の倍数であることが確実であり、2番目の部分$（3k -1）$も以前の仮定として当てはまります。
したがって、$ 3 ^ {k + 1} – 1 $は2の倍数です。
したがって、$ 3 ^ n – 1 $は2の倍数であることが証明されます。
問題2
$ 1 + 3 + 5 + ... +（2n-1）= n ^ 2 $ for $ n = 1、2、\ dots $
Solution
Step 1 − $ n = 1の場合、1 = 1 ^ 2 $であるため、ステップ1が満たされます。
Step 2 −ステートメントが$ n = k $に対して真であると仮定しましょう。
したがって、$ 1 + 3 + 5 + \ dots +（2k-1）= k ^ 2 $は真です（これは仮定です）
$ 1 + 3 + 5 + ... +（2（k + 1）-1）=（k + 1）^ 2 $も成り立つことを証明する必要があります
$ 1 + 3 + 5 + \ dots +（2（k + 1）-1）$
$ = 1 + 3 + 5 + \ dots +（2k + 2-1）$
$ = 1 + 3 + 5 + \ dots +（2k + 1）$
$ = 1 + 3 + 5 + \ dots +（2k-1）+（2k + 1）$
$ = k ^ 2 +（2k + 1）$
$ =（k + 1）^ 2 $
したがって、$ 1 + 3 + 5 + \ dots +（2（k + 1）-1）=（k + 1）^ 2 $が成り立ち、ステップ2を満たします。
したがって、$ 1 + 3 + 5 + \ dots +（2n-1）= n ^ 2 $が証明されます。
問題3
$（ab）^ n = a ^ nb ^ n $がすべての自然数$ n $に対して真であることを証明します
Solution
Step 1 − $ n = 1の場合、（ab）^ 1 = a ^ 1b ^ 1 = ab $であるため、ステップ1が満たされます。
Step 2 −ステートメントが$ n = k $に対して真であると仮定します。したがって、$（ab）^ k = a ^ kb ^ k $は真です（これは仮定です）。
$（ab）^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $も成り立つことを証明する必要があります
与えられた場合、$（ab）^ k = a ^ kb ^ k $
または、$（ab）^ k（ab）=（a ^ kb ^ k）（ab）$ [両側に 'ab'を掛ける]
または、$（ab）^ {k + 1} =（aa ^ k）（bb ^ k）$
または、$（ab）^ {k + 1} =（a ^ {k + 1} b ^ {k + 1}）$
したがって、ステップ2が証明されます。
したがって、$（ab）^ n = a ^ nb ^ n $はすべての自然数nに当てはまります。
強い帰納法
強い帰納法は、数学的帰納法のもう1つの形式です。この誘導手法により、次の手順を使用して、命題関数$ P（n）$がすべての正の整数$ n $に対して真であることを証明できます。
Step 1(Base step) −最初の命題$ P（1）$が真であることを証明します。
Step 2(Inductive step) −条件文$ [P（1）\ land P（2）\ land P（3）\ land \ dots \ land P（k）]→P（k + 1）$が正の整数$に対して真であることを証明します。 k $。