Indukcja matematyczna

Indukcja matematyczna jest często stosowaną metodą dowodu w matematyce, najczęściej podczas pracy z liczbami naturalnymi lub innymi sekwencjami.

Zasada

Podstawową zasadą jest to, że dowodzimy danego twierdzenia dla jakiegoś pierwszego elementu, w liczbach naturalnych jest to najczęściej n = 1. Dowodzimy tego przez proste dodawanie. W kolejnym, indukcyjnym kroku udowadniamy implikację "jeśli twierdzenie jest prawdziwe dla n = a, to jest prawdziwe również dla n = a + 1".

Z tych dwóch kroków możemy wywnioskować, że wyrażenie jest prawdziwe dla wszystkich n (z jakiegoś zbioru, z którym aktualnie pracujemy). Dlaczego tak jest? Na początku udowodniliśmy, że wyrażenie jest prawdziwe dla n = 1. Wiemy również, że wyrażenie jest prawdziwe dla n = a i n = a + 1. Wybieramy więc a = 1. Wiemy, że wyrażenie jest prawdziwe dla a = 1 i wiemy również, że jest prawdziwe dla a + 1 = 2. W tym momencie wiemy, że wyrażenie jest prawdziwe dla a = 2. Ale skoro jest prawdziwe dla a + 1, to musi być prawdziwe również dla 2 + 1 = 3. I tak dalej.

Pierwszy przykład

Pierwszy przykład będzie trywialny. Udowodnimy, że jeśli do dowolnej liczby parzystej dodamy dwa, to ponownie otrzymamy liczbę parzystą. Ponieważ mamy do czynienia z liczbami naturalnymi, liczbę parzystą zapiszemy ogólnie jako 2n, gdzie n jest liczbą naturalną. Jeśli dodamy dowolną liczbę naturalną po n, w wyniku otrzymamy liczbę parzystą, co widać na pierwszy rzut oka. Podzielność jest zapisywana za pomocą pionowej linii w następujący sposób:

$$2\mid2n$$

Ta notacja wskazuje, że dwa dzieli wyrażenie 2n bez reszty. Teraz, gdy możemy napisać podzielność, możemy napisać, co musimy udowodnić za pomocą indukcji matematycznej.

$$2\mid 2n+2; \quad n\in\mathbb{N}$$

To jest właśnie to, co mamy udowodnić w pierwszym przykładzie, że dwa dzieli wyrażenie 2n + 2 - jest to dokładnie to, co mówi oryginalny problem słowny "jeśli dodamy dwa do dowolnej liczby parzystej, otrzymamy ponownie liczbę parzystą".

W pierwszym kroku indukcji udowodnimy to dla pierwszego elementu, jedynki. Podstawiamy wyrażenie n = 1:

$$\begin{eqnarray} 2&\mid& 2\cdot1+2\\ 2&\mid& 4 \end{eqnarray}$$

Dwa dzieli cztery bez reszty, więc jest to prawda dla pierwszego elementu. Następnie przechodzimy do etapu indukcji, w którym musimy udowodnić, że jeśli zachodzi to dla a-tego elementu, to zachodzi to również dla (a + 1) elementu. Na początku zakładamy, że nasze założenie jest prawdziwe, tj. n = a:

$$2\mid2a+2$$

Zakładamy, że to wyrażenie jest prawdziwe - używamy go w konstrukcji dowodu. Teraz chcemy udowodnić, że

$$2\mid2(a+1)+2.$$

Co zrobiliśmy? Zamiast a napisaliśmy (a + 1). Nawiasy są ważne, to wyrażenie byłoby błędne: 2a + 1 + 2. Nie dodajemy jedynki do całego wyrażenia, ale tak naprawdę robimy z a wyrażenie o jeden większe, czyli (a + 1). Modyfikujemy wyrażenie mnożąc nawiasy.

$$\begin{eqnarray} 2&\mid&2(a+1)+2\\ 2&\mid&2a+2+2
\end{eqnarray}$$

Teraz mała dygresja na temat podzielności. Jeśli mamy dwie liczby, powiedzmy p i q, które są podzielne przez pewną liczbę, powiedzmy r, to ich suma jest również podzielna przez r. Zatem:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Możemy wstawić, na przykład, liczby p = 8, q = 20 i r = 4. Widzimy, że cztery dzieli zarówno osiem, jak i dwadzieścia. Podobnie jak ich suma 8 + 20 = 28.

Jak możemy to wykorzystać w naszym przykładzie? Podzielmy prawą stronę na liczby p i q w następujący sposób:

$$p=2a+2; \quad q=2$$

Liczba q, czyli dwa, jest trywialnie podzielna przez dwa. Wyrażenie p jest również trywialnie podzielne przez dwa, ponieważ tak mówi nam przesłanka. Wyrażenie p dokładnie odpowiada naszemu założeniu, które przyjmujemy za prawdziwe. A jeśli p jest podzielne przez dwa i q jest podzielne przez dwa, to suma tych dwóch jest podzielna przez dwa.

Jeszcze raz o założeniu. Na początku powiedzieliśmy, że zakładamy, że

$$2\mid2a+2.$$

Dlatego, gdy podczas konstruowania dowodu natknęliśmy się na wyrażenie 2a + 2, mogliśmy powiedzieć, że jest ono podzielne przez dwa. Właśnie dlatego, że takie jest nasze założenie. Jest to zwykle najtrudniejszy etap indukcji matematycznej - zrozumienie, kiedy i do czego można użyć założenia indukcyjnego.

To kończy indukcję, dowód został pomyślnie przeprowadzony, twierdzenie jest prawdziwe.

Gdybyś chciał, mógłbyś to rozbić inaczej i nie musiałbyś używać przesłanki. p = 2n i q = 2 + 2. Liczba q = 4 jest trywialnie podzielna przez cztery, podobnie jak p = 2n, ponieważ po podzieleniu przez dwa otrzymujemy n, która jest liczbą naturalną, czyli całkowitą. Ponownie mamy więc dwa wyrażenia, które są podzielne przez dwa, więc ich suma jest również podzielna przez dwa.

Ale w obu przypadkach udowodniliśmy, że

1. podane wyrażenie jest prawdziwe dla n = 1,

• jeśli wyrażenie zachodzi dla n, to zachodzi również dla n + 1.

Stąd możemy już wyprowadzić wniosek:

• Wiemy, że wyrażenie zachodzi dla n = 1.
• Jeśli jest ono prawdziwe dla n, to musi być również prawdziwe dla n + 1, czyli również dla 1 + 1, czyli wyrażenie jest również prawdziwe dla n = 2.
• Jeśli ma zastosowanie do n, musi mieć również zastosowanie do n + 1, tj. również do 2 + 1, tj. wyrażenie ma również zastosowanie do n = 3.
• Jeśli ma zastosowanie do n, musi również mieć zastosowanie do n + 1, tj. również do 3 + 1, tj. wyrażenie ma zastosowanie do n = 4.
• Jeśli dotyczy n, musi również dotyczyć n + 1, tj. również 4 + 1, tj. wyrażenie dotyczy n = 5.
• ...

Drugi przykład

Następnie udowodnimy proste twierdzenie za pomocą indukcji matematycznej:

$$2^n\ge2n;\quad n\in\mathbb{N}.$$

W pierwszym kroku sprawdzamy, czy twierdzenie jest prawdziwe dla n = 1, jako pierwszego elementu zbioru liczb naturalnych, z którego wybieramy n.

$$\begin{eqnarray} 2^1&\ge&2\cdot1\\ 2&\ge&2 \end{eqnarray}$$

Twierdzenie jest trywialnie prawdziwe. Teraz przechodzimy do etapu indukcji, w którym musimy sprawdzić, czy jeśli zachodzi dla n = a, to zachodzi również dla n = a + 1. Zakładamy więc, że zachodzi

$$2^a\ge2a$$

i chcemy to udowodnić:

$$2^{a+1}\ge2(a+1)$$

Najpierw rozbijamy lewą stronę za pomocą zasad rachunku potęgowego i po prostu mnożymy prawą stronę.

$$2\cdot2^a\ge2a+2$$

W lewej stronie używamy dodawania zamiast mnożenia, a prawą stronę pozostawiamy bez zmian.

$$2^a+2^a\ge2a+2$$

Teraz użyjemy założenia. Założenie to stwierdzenie, które przyjmujemy za prawdziwe. W nierówności mamy dwa wyrażenia po obu stronach, które się sumują. Jednocześnie wiemy, że

$$\begin{eqnarray} 2^a&\ge&2a\\ 2^a&\ge&2. \end{eqnarray}$$

Pierwszy wiersz mówi nam o założeniu, a drugie stwierdzenie jest trywialne (najniższy 2^a jest dla a = 1 i równa się tylko dwa). Wiemy więc, że dwa wyrażenia po lewej stronie są większe lub równe dwóm wyrażeniom po prawej stronie. W ten sposób udowodniliśmy przez indukcję, że jeśli wyrażenie jest prawdziwe dla a, to jest prawdziwe dla (a + 1), a ponieważ wyrażenie jest prawdziwe dla jednego, to wyrażenie jest prawdziwe.

Trzeci przykład

Spróbujmy udowodnić następujące stwierdzenie:

$$3\mid n\Rightarrow 3\mid n^2;\quad n\in\mathbb{N}$$

Słownie: jeśli n jest podzielne przez trzy, to n² jest również podzielne przez trzy. Jeśli n nie jest podzielne przez trzy, to wyrażenie jest trywialnie prawdziwe (z definicji implikacji), więc rozważymy przypadki, w których n jest podzielne przez trzy. Spowoduje to wygenerowanie ciągu liczb naturalnych a_i=3, 6, 9, 12, 15... Od teraz będziemy przechodzić przez ten ciąg a_i.

Dowód przez indukcję rozpoczynamy od pierwszego kroku, tzn. jeśli zachodzi dla pierwszego elementu. Przypomnijmy, że poruszamy się w ciągu a_i, więc bierzemy pierwszy element tego ciągu, tj. element a₁, który jest trójką. Dla trójki wyrażenie jest prawdziwe:

$$3\mid3\Rightarrow 3\mid3^2$$

Przechodzimy teraz do kroku indukcji. Widzimy, że ciąg a_i można zapisać jako 3n, gdzie n jest liczbą naturalną. Zatem drugi element jest o trzy większy od poprzedniego itd. Załóżmy teraz, że wyrażenie to zachodzi dla n i musimy upewnić się, że zachodzi ono również dla (n + 3), co jest receptą, która wygeneruje następny element w sekwencji, przez którą się poruszamy. Zapiszmy najpierw założenie:

$$3\mid n\Rightarrow 3\mid n^2$$

, a następnie to, co chcemy udowodnić

$$3\mid (n+3)\Rightarrow 3\mid(n+3)^2.$$

Dekomponujemy nawias po drugiej stronie za pomocą wzoru:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

I prawie jesteśmy na miejscu. Po lewej stronie mamy wyrażenie, które na pewno jest podzielne przez trzy, ponieważ n jest podzielne przez trzy z założenia (poruszamy się tylko po liczbach ciągu a_i), a trzy jest również podzielne przez trzy. Po prawej stronie mamy najpierw n², która z założenia jest podzielna przez trzy. To znaczy, wiemy, że n jest podzielne przez trzy, a założenie mówi, że jeśli n jest podzielne przez trzy, to n² jest również podzielne przez trzy:

$$3\mid n\Rightarrow 3\mid n^2$$

Następnie otrzymujemy wyrażenie 6n, które jest trywialnie podzielne przez trzy. Można to traktować jako skrócenie ułamka:

$$\frac{6n}{3}=2n$$

Zmienna n jest pewną liczbą naturalną, więc iloczyn 2n również będzie liczbą naturalną, tzn. po podzieleniu przez trzy mamy liczbę naturalną, a więc wyrażenie 6n musi być podzielne przez trzy. Dziewiątka na końcu również jest podzielna przez trzy. Wyrażenie jest prawdziwe dla pierwszego elementu i dla kroku indukcji.

Liczba nawiasów w wyrażeniu

Ostatni przykład będzie nieco nietypowy. Spróbujmy udowodnić twierdzenie, że liczba nawiasów w prostym wyrażeniu jest zawsze parzysta, aby zobaczyć, że indukcja matematyczna może być używana w zupełnie innym kontekście niż tylko liczby naturalne. Na początek musimy zdefiniować, czym jest wyrażenie proste. Wyrażenie proste to:

• liczba naturalna,
• jeśli p jest wyrażeniem prostym, to (p²) jest wyrażeniem prostym,
• jeśli p i q są wyrażeniami prostymi, to (p + q) jest wyrażeniem prostym.

Więc co jest wyrażeniem prostym: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). I odwrotnie, nie są to wyrażenia proste:

• 1 + 2 $\rightarrow$ brakuje zewnętrznych nawiasów,
• (1 + 2 $\rightarrow$ brakuje prawych nawiasów,
• 13² $\rightarrow$ brakuje nawiasów zewnętrznych,
• (1 + 2 + 3) $\rightarrow$ brakuje nawiasów, poprawna pisownia powinna brzmieć (1+(2 + 3))

Wyrażenie proste można utworzyć na przykład w następujący sposób. Na początku wybieramy wyrażenie proste (a + b). Teraz po a wstawiamy wyrażenie proste a = (c + d), dzięki czemu otrzymujemy ((c + d)+b), a po b wstawiamy trójkę: ((c + d)+3) Po c wstawiamy dziesiątkę: ((10 + d)+3) i wreszcie po d wstawiamy (5²): ((10+(5²))+3) Ważne jest, aby podążać za nawiasami, w przeciwnym razie nie zadziała.

Teraz udowodnimy, że proste wyrażenie zawiera parzystą liczbę nawiasów (liczby parzyste zawierają zero).

W pierwszym kroku indukcji wybieramy jakiś pierwszy element. W tym przypadku pierwszym elementem będzie najbardziej trywialne wyrażenie proste, czyli dowolna liczba naturalna. Wstawiamy więc

$$j=n;\quad n\in\mathbb{N}.$$

Dla wyrażenia j liczba nawiasów wynosi zero, więc pierwszy element jest spełniony. W kroku indukcji założymy, że mamy dwa proste wyrażenia p i q i że oba mają parzystą liczbę nawiasów. Następnie musimy udowodnić, że proste wyrażenia (p + q) i (p²) również mają parzystą liczbę nawiasów.

Najpierw dodawanie. Definiujemy kolejną funkcję z(q), która zwraca liczbę nawiasów wyrażenia q. Następnie wyrażenie (p + q) ma nawiasy z(p)+z(q)+2. Oznacza to, że ma o dwa nawiasy więcej niż suma nawiasów wyrażeń p i q. Z założenia zarówno z(p), jak i z(q) są parzyste, więc jeśli dodamy trzy liczby parzyste, otrzymamy ponownie liczbę parzystą. W tym przypadku twierdzenie jest prawdziwe.

Przejdźmy teraz do potęgi. Ponownie, założenie, że proste wyrażenie p zawiera parzystą liczbę nawiasów, jest prawdziwe. Wyrażenie (p²) zawiera nawiasy z(p)+2, czyli o dwa nawiasy więcej niż wyrażenie p. W tym przypadku również dodajemy liczby parzyste, więc wynik jest parzysty.

Twierdzenie jest prawdziwe dla pierwszego elementu i jest również prawdziwe w kroku indukcji, więc twierdzenie jest prawdziwe.

Dalsze zasoby i przykłady

• Wiele przykładów na forum matematycznym
• slajdy na fi.muni.cz [PDF]