Indukcja matematyczna — zasada, kroki i przykłady

Indukcja matematyczna to metoda dowodzenia, która pozwala wykazać, że pewne zdanie jest prawdziwe dla każdej liczby całkowitej od pewnego miejsca. Aby udowodnić tezę dla wszystkich $n \ge n_0$, pokazujesz, że pierwszy przypadek jest prawdziwy, a następnie że prawdziwość dla jednej liczby całkowitej wymusza prawdziwość dla kolejnej.

Jeśli oba te elementy są poprawne, zdanie zachodzi dla każdej liczby całkowitej z podanego zakresu. Na tym polega cała idea.

Jak działa indukcja matematyczna

Zapisz tezę jako $P(n)$. Wtedy indukcja ma następującą strukturę:

1. Udowodnij bazę indukcji: pokaż, że $P(n_0)$ jest prawdziwe.
2. Udowodnij krok indukcyjny: pokaż, że jeśli $P(k)$ jest prawdziwe dla dowolnej liczby całkowitej $k \ge n_0$, to $P(k+1)$ także jest prawdziwe.

Gdy wykonasz oba kroki, możesz stwierdzić, że $P(n)$ jest prawdziwe dla każdej liczby całkowitej $n \ge n_0$.

Ta logika jest sekwencyjna. Baza indukcji rozpoczyna cały łańcuch, a krok indukcyjny przesuwa go dalej, o jedną liczbę całkowitą naraz.

Dlaczego baza indukcji i krok indukcyjny są jednakowo ważne

Baza indukcji daje ci pierwsze prawdziwe zdanie. Krok indukcyjny mówi, że prawdziwość przechodzi z jednej liczby całkowitej na następną.

Jeśli więc $P(n_0)$ jest prawdziwe, to prawdziwe jest także $P(n_0 + 1)$. Następnie prawdziwe jest $P(n_0 + 2)$ i tak dalej. Indukcja nie pomija punktu startowego i nie pomija przejścia od jednego przypadku do następnego.

Przykład: dowód wzoru na sumę za pomocą indukcji

Standardowym przykładem jest wzór

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

dla wszystkich liczb całkowitych $n \ge 1$.

Niech

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Baza indukcji

Weźmy $n = 1$. Lewa strona wynosi $1$, a prawa strona to

$$\frac{1(1+1)}{2} = 1$$

Zatem $P(1)$ jest prawdziwe.

Krok indukcyjny

Załóżmy, że $P(k)$ jest prawdziwe dla pewnej dowolnej liczby całkowitej $k \ge 1$. To znaczy, że

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Teraz udowodnijmy $P(k+1)$. Zacznijmy od lewej strony dla $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Korzystając z założenia indukcyjnego, otrzymujemy

$$\frac{k(k+1)}{2} + (k+1)$$

Wyłączmy $(k+1)$ przed nawias:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Następnie upraszczamy:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

To jest dokładnie ten sam wzór dla $n = k+1$. Zatem $P(k+1)$ jest prawdziwe.

Ponieważ udowodniliśmy zarówno bazę indukcji, jak i krok indukcyjny, wzór zachodzi dla wszystkich liczb całkowitych $n \ge 1$.

Kiedy stosować indukcję matematyczną

Indukcja jest przydatna wtedy, gdy zdanie zależy od parametru całkowitego, a każdy przypadek w naturalny sposób łączy się z wcześniejszym. Często dzieje się tak przy sumach, twierdzeniach o podzielności, nierównościach, relacjach rekurencyjnych i dowodach dotyczących algorytmów.

Najpierw ustal poprawną wartość początkową. Niektóre tezy zaczynają się od $n = 0$, inne od $n = 1$, a jeszcze inne mają sens dopiero dla większych liczb całkowitych.

Następnie sprawdź, jaki jest kolejny dopuszczalny przypadek. Zwykle przechodzi się od $k$ do $k+1$, ale jeśli zdanie dotyczy tylko liczb parzystych, właściwą wersją może być przejście od $k$ do $k+2$.

Typowe błędy w dowodach indukcyjnych

Udowodnienie tylko bazy indukcji

Baza indukcji sprawdza tylko pierwszą wartość. Sama w sobie nie dowodzi prawdziwości zdania dla kolejnych liczb całkowitych.

Użycie niewłaściwej wartości początkowej

Jeśli teza ma zachodzić dla wszystkich $n \ge 2$, to udowodnienie jedynie $P(1)$ nic nie daje. Baza indukcji musi odpowiadać rzeczywistemu zakresowi tezy.

Nieostrożne traktowanie założenia indukcyjnego

W kroku indukcyjnym zakładasz prawdziwość $P(k)$ dla jednej dowolnej liczby całkowitej $k$ z dopuszczalnego zakresu. Nie zakładasz, że całe twierdzenie zostało już udowodnione.

Udowodnienie niewłaściwego następnego przypadku

Jeśli twoje twierdzenie wymaga kroku $k \to k+1$, to udowodnienie innego przejścia nie kończy rozumowania, chyba że wyjaśnisz, dlaczego to inne przejście wystarcza.

Przydatne rozszerzenie: indukcja zupełna

Czasami do udowodnienia $P(k+1)$ potrzeba czegoś więcej niż tylko $P(k)$. W takiej sytuacji indukcja zupełna pozwala założyć prawdziwość wszystkich wcześniejszych przypadków aż do $k$, a następnie udowodnić kolejny.

Idea jest bardzo podobna, ale założenie jest silniejsze. To przydaje się na przykład wtedy, gdy dowód opiera się na rozkładzie liczby na mniejsze części.

Spróbuj samodzielnie

Weź tezę

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

i udowodnij ją dla wszystkich liczb całkowitych $n \ge 1$, używając tej samej struktury: najpierw baza indukcji, a potem przejście od $k$ do $k+1$. Jeśli potrafisz zapisać ten dowód jasno i poprawnie, metoda zwykle staje się intuicyjna.