Mathematische Induktion
Mathematical inductionist eine Technik zum Nachweis von Ergebnissen oder zur Erstellung von Aussagen für natürliche Zahlen. Dieser Teil veranschaulicht die Methode anhand verschiedener Beispiele.
Definition
Mathematical Induction ist eine mathematische Technik, die verwendet wird, um zu beweisen, dass eine Aussage, eine Formel oder ein Satz für jede natürliche Zahl gilt.
Die Technik umfasst zwei Schritte, um eine Aussage zu beweisen, wie unten angegeben -
Step 1(Base step) - Es zeigt, dass eine Aussage für den Anfangswert wahr ist.
Step 2(Inductive step)- Es beweist, dass, wenn die Aussage für die n- te Iteration (oder die Zahl n ) gilt, sie auch für die (n + 1) -te Iteration (oder die Zahl n + 1 ) gilt.
Wie es geht
Step 1- Betrachten Sie einen Anfangswert, für den die Aussage wahr ist. Es ist zu zeigen, dass die Aussage für n = Anfangswert wahr ist.
Step 2- Angenommen, die Aussage gilt für jeden Wert von n = k . Dann beweisen Sie, dass die Aussage für n = k + 1 wahr ist . Wir brechen n = k + 1 tatsächlich in zwei Teile, ein Teil ist n = k (was bereits bewiesen ist) und versuchen, den anderen Teil zu beweisen.
Problem 1
$ 3 ^ n-1 $ ist ein Vielfaches von 2 für n = 1, 2, ...
Solution
Step 1 - Für $ n = 1 ist 3 ^ 1-1 = 3-1 = 2 $ ein Vielfaches von 2
Step 2 - Nehmen wir an, dass $ 3 ^ n-1 $ für $ n = k $ wahr ist. Daher ist $ 3 ^ k -1 $ wahr (es ist eine Annahme).
Wir müssen beweisen, dass $ 3 ^ {k + 1} -1 $ auch ein Vielfaches von 2 ist
$ 3 ^ {k + 1} - 1 = 3 \ mal 3 ^ k - 1 = (2 \ mal 3 ^ k) + (3 ^ k - 1) $
Der erste Teil $ (2 \ mal 3k) $ ist mit Sicherheit ein Vielfaches von 2, und der zweite Teil $ (3k -1) $ gilt ebenfalls als unsere vorherige Annahme.
Daher ist $ 3 ^ {k + 1} - 1 $ ein Vielfaches von 2.
Es ist also bewiesen, dass $ 3 ^ n - 1 $ ein Vielfaches von 2 ist.
Problem 2
$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ für $ n = 1, 2, \ dots $
Solution
Step 1 - Für $ n = 1 ist 1 = 1 ^ 2 $, daher ist Schritt 1 erfüllt.
Step 2 - Nehmen wir an, die Aussage gilt für $ n = k $.
Daher ist $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ wahr (es ist eine Annahme)
Wir müssen beweisen, dass $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ auch gilt
$ 1 + 3 + 5 + \ Punkte + (2 (k + 1) - 1) $
$ = 1 + 3 + 5 + \ Punkte + (2k + 2 - 1) $
$ = 1 + 3 + 5 + \ Punkte + (2k + 1) $
$ = 1 + 3 + 5 + \ Punkte + (2k - 1) + (2k + 1) $
$ = k ^ 2 + (2k + 1) $
$ = (k + 1) ^ 2 $
Also, $ 1 + 3 + 5 + \ Punkte + (2 (k + 1) - 1) = (k + 1) ^ 2 $ halten, was den Schritt 2 erfüllt.
Somit ist $ 1 + 3 + 5 + \ Punkte + (2n - 1) = n ^ 2 $ bewiesen.
Problem 3
Beweisen Sie, dass $ (ab) ^ n = a ^ nb ^ n $ für jede natürliche Zahl $ n $ gilt
Solution
Step 1 - Für $ n = 1 ist (ab) ^ 1 = a ^ 1b ^ 1 = ab $, daher ist Schritt 1 erfüllt.
Step 2 - Nehmen wir an, dass die Aussage für $ n = k $ wahr ist. Daher ist $ (ab) ^ k = a ^ kb ^ k $ wahr (es ist eine Annahme).
Wir müssen beweisen, dass auch $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ gilt
Gegeben, $ (ab) ^ k = a ^ kb ^ k $
Oder $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Beide Seiten mit 'ab' multiplizieren]
Oder $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $
Oder $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $
Somit ist Schritt 2 bewiesen.
Also gilt $ (ab) ^ n = a ^ nb ^ n $ für jede natürliche Zahl n.
Starke Induktion
Starke Induktion ist eine andere Form der mathematischen Induktion. Durch diese Induktionstechnik können wir mit den folgenden Schritten beweisen, dass eine Satzfunktion $ P (n) $ für alle positiven ganzen Zahlen $ n $ gilt -
Step 1(Base step) - Es beweist, dass der ursprüngliche Satz $ P (1) $ wahr ist.
Step 2(Inductive step) - Es zeigt, dass die bedingte Aussage $ [P (1) \ Land P (2) \ Land P (3) \ Land \ Punkte \ Land P (k)] → P (k + 1) $ für positive ganze Zahlen $ gilt k $.