Indukcja matematyczna

Mathematical induction, to technika potwierdzania wyników lub ustalania zdań dla liczb naturalnych. Ta część ilustruje metodę za pomocą różnych przykładów.

Definicja

Mathematical Induction jest techniką matematyczną używaną do udowodnienia twierdzenia, wzoru lub twierdzenia, które są prawdziwe dla każdej liczby naturalnej.

Technika obejmuje dwa kroki, aby udowodnić stwierdzenie, jak podano poniżej:

Step 1(Base step) - Dowodzi, że stwierdzenie jest prawdziwe dla wartości początkowej.

Step 2(Inductive step)- Dowodzi, że jeśli stwierdzenie jest prawdziwe dla n- ^tej iteracji (lub liczby n ), to jest również prawdziwe dla (n + 1) ^tej iteracji (lub liczby n + 1 ).

Jak to zrobić

Step 1- Rozważ wartość początkową, dla której stwierdzenie jest prawdziwe. Należy wykazać, że stwierdzenie to jest prawdziwe dla n = wartość początkowa.

Step 2- Załóżmy, że stwierdzenie jest prawdziwe dla dowolnej wartości n = k . Następnie udowodnij, że stwierdzenie jest prawdziwe dla n = k + 1 . W rzeczywistości dzielimy n = k + 1 na dwie części, jedna część to n = k (co jest już udowodnione) i próbujemy udowodnić drugą część.

Zadanie 1

$ 3 ^ n-1 $ jest wielokrotnością 2 dla n = 1, 2, ...

Solution

Step 1 - Dla $ n = 1, 3 ^ 1-1 = 3-1 = 2 $, czyli wielokrotność 2

Step 2 - Załóżmy, że $ 3 ^ n-1 $ jest prawdą dla $ n = k $, Stąd $ 3 ^ k -1 $ jest prawdą (Jest to założenie)

Musimy udowodnić, że $ 3 ^ {k + 1} -1 $ jest również wielokrotnością 2

$ 3 ^ {k + 1} - 1 = 3 \ times 3 ^ k - 1 = (2 \ times 3 ^ k) + (3 ^ k - 1) $

Pierwsza część $ (2 \ times 3k) $ z pewnością będzie wielokrotnością 2, a druga część $ (3k -1) $ jest również prawdziwa, tak jak nasze poprzednie założenie.

Stąd $ 3 ^ {k + 1} - 1 $ to wielokrotność 2.

Zatem udowodniono, że $ 3 ^ n - 1 $ to wielokrotność 2.

Problem 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ dla $ n = 1, 2, \ kropki $

Solution

Step 1 - Dla $ n = 1, 1 = 1 ^ 2 $, zatem krok 1 jest spełniony.

Step 2 - Załóżmy, że to stwierdzenie jest prawdziwe dla $ n = k $.

Stąd $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ jest prawdą (jest to założenie)

Musimy udowodnić, że $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ również zachowuje

$ 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 $

Zatem $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ hold, co spełnia krok 2.

Stąd udowodniono, że $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $.

Problem 3

Udowodnij, że $ (ab) ^ n = a ^ nb ^ n $ jest prawdą dla każdej liczby naturalnej $ n $

Solution

Step 1 - Dla $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, Stąd krok 1 jest spełniony.

Step 2 - Załóżmy, że stwierdzenie jest prawdziwe dla $ n = k $, Stąd, $ (ab) ^ k = a ^ kb ^ k $ jest prawdziwe (jest to założenie).

Musimy udowodnić, że $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ również przytrzymaj

Biorąc pod uwagę, $ (ab) ^ k = a ^ kb ^ k $

Albo $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Mnożenie obu stron przez „ab”]

Lub $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

Lub $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

W związku z tym udowodniono krok 2.

Zatem $ (ab) ^ n = a ^ nb ^ n $ jest prawdą dla każdej liczby naturalnej n.

Silna indukcja

Silna indukcja to kolejna forma indukcji matematycznej. Dzięki tej technice indukcyjnej możemy udowodnić, że funkcja zdaniowa $ P (n) $ jest prawdziwa dla wszystkich dodatnich liczb całkowitych, $ n $, wykonując następujące kroki -

• Step 1(Base step) - Dowodzi, że zdanie początkowe $ P (1) $ jest prawdziwe.

• Step 2(Inductive step) - Dowodzi, że instrukcja warunkowa $ [P (1) \ ziemia P (2) \ ziemia P (3) \ ziemia \ dots \ ziemia P (k)] → P (k + 1) $ jest prawdziwa dla dodatnich liczb całkowitych $ k $.