Indukcja matematyczna

Indukcja matematyczna to często używana metoda dowodzenia w matematyce, najczęściej wtedy, gdy pracujemy z liczbami naturalnymi albo z jakimś innym ciągiem.

Zasada

Podstawowa zasada polega na tym, że dane twierdzenie udowadniamy dla jakiegoś pierwszego elementu, w liczbach naturalnych jest to najczęściej n = 1 (albo n = 0, jeśli zaliczamy zero do liczb naturalnych). To udowadniamy zwykłym podstawieniem – jest to krok bazowy (pierwszy krok indukcji). W kolejnym kroku, nazywanym krokiem indukcyjnym, udowadniamy implikację „jeśli twierdzenie jest prawdziwe dla n = a, to jest prawdziwe także dla n = a + 1”. Jej poprzednik nazywamy założeniem indukcyjnym, a następnik tezą indukcyjną.

Z tych dwóch kroków możemy wywnioskować, że dane wyrażenie jest prawdziwe dla wszystkich n (z jakiegoś zbioru, z którym akurat pracujemy). Dlaczego tak jest? Na początku udowodnimy, że wyrażenie jest prawdziwe dla n = 1. Jednocześnie wiemy, że jeśli wyrażenie jest prawdziwe dla n = a, to jest prawdziwe także dla n = a + 1. Wybierzemy więc a = 1. Wiemy, że dla a = 1 wyrażenie jest prawdziwe, a więc jest prawdziwe także dla a + 1 = 2. W tym momencie wiemy, że wyrażenie jest prawdziwe dla a = 2. Ale ponieważ jest wtedy prawdziwe także dla a + 1, 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 dwójkę, dostaniemy znowu liczbę parzystą. Ponieważ poruszamy się w liczbach naturalnych, liczbę parzystą zapiszemy ogólnie jako 2n, gdzie n jest liczbą naturalną. Jeśli za n podstawimy dowolną liczbę naturalną, dostaniemy w wyniku liczbę parzystą, to widać na pierwszy rzut oka. Podzielność zapisuje się za pomocą pionowej kreski tak:

$$2\mid2n$$

Ten zapis oznacza, że dwójka dzieli bez reszty wyrażenie 2n. Skoro umiemy już zapisać podzielność, możemy zapisać także to, co mamy udowodnić indukcją matematyczną.

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

To mamy udowodnić w pierwszym przykładzie, czyli że dwójka dzieli wyrażenie 2n + 2 – dokładnie to odpowiada wyjściowej słownej treści „jeśli do dowolnej liczby parzystej dodamy dwójkę, dostaniemy znowu liczbę parzystą”.

W pierwszym kroku indukcji (kroku bazowym) udowodnimy to dla pierwszego elementu, dla jedynki. Podstawiamy do wyrażenia n = 1:

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

Dwójka dzieli czwórkę bez reszty, więc dla pierwszego elementu twierdzenie jest prawdziwe. (Jeśli zaliczamy do liczb naturalnych także zero, krok bazowy robimy dla n = 0: $2\mid 2\cdot0+2$, czyli $2\mid2$, co też jest prawdą. Krok indukcyjny poniżej działa dla każdego a, więc twierdzenie zachodzi wtedy już od zera.) Dalej przychodzi kolej na krok indukcyjny, w którym musimy udowodnić, że jeśli twierdzenie jest prawdziwe dla a-tego elementu, to jest prawdziwe także dla elementu (a + 1). Na początku przyjmujemy założenie indukcyjne, czyli że twierdzenie jest prawdziwe dla n = a:

$$2\mid2a+2$$

O tym wyrażeniu zakładamy, że jest prawdziwe – wykorzystamy je przy budowaniu dowodu. Teraz chcemy udowodnić tezę indukcyjną:

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

Co zrobiliśmy? W miejsce a wpisaliśmy (a + 1). Ważne są te nawiasy, takie wyrażenie byłoby złe: 2a + 1 + 2. Nie dodajemy jedynki do całego wyrażenia, tylko naprawdę robimy z a wyrażenie o jeden większe, czyli (a + 1). Wyrażenie przekształcimy, wymnażając nawias.

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

Teraz mała dygresja o podzielności. Jeśli mamy dwie liczby, powiedzmy p i q, które są podzielne przez jakąś liczbę, na przykład r, to również ich suma jest podzielna przez r. Zachodzi więc:

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

Możemy tu podstawić na przykład liczby p = 8, q = 20 i r = 4. Widzimy, że czwórka dzieli zarówno ósemkę, jak i dwudziestkę. I tak samo dzieli też ich sumę 8 + 20 = 28.

Jak to wykorzystamy w naszym przykładzie? Podzielimy prawą stronę na liczby p i q tak:

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

Liczba q, czyli dwójka, jest w oczywisty sposób podzielna przez dwa. A wyrażenie p też jest podzielne przez dwa, bo mówi nam to założenie. Wyrażenie p dokładnie odpowiada naszemu założeniu indukcyjnemu, o którym zakładamy, że jest prawdziwe. A jeśli p jest podzielne przez dwa i jednocześnie q jest podzielne przez dwa, to także ich suma jest podzielna przez dwa.

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

$$2\mid2a+2.$$

Dlatego gdy przy budowaniu dowodu natrafiliśmy na wyrażenie 2a + 2, mogliśmy o nim powiedzieć, że jest podzielne przez dwa. Właśnie dlatego, że to jest nasze założenie. Zwykle to bywa najtrudniejszy krok indukcji matematycznej – zrozumieć, kiedy i dlaczego można użyć założenia indukcyjnego.

Na tym indukcja się kończy, dowód został pomyślnie przeprowadzony, twierdzenie jest prawdziwe.

Gdybyś chciał, mógłbyś to rozłożyć inaczej i nie musiałbyś korzystać z założenia. p = 2n i q = 2 + 2. Liczba q = 4 jest w oczywisty sposób podzielna przez dwa i tak samo p = 2n, bo po podzieleniu przez dwa zostaje nam liczba n, która jest naturalna, czyli całkowita. Znowu dostaliśmy więc dwa wyrażenia, które są oba podzielne przez dwa, więc także ich suma jest podzielna przez dwa.

W obu przypadkach udowodniliśmy jednak, że

1. dane wyrażenie jest prawdziwe dla n = 1,
2. jeśli wyrażenie jest prawdziwe dla n, to jest prawdziwe także dla n + 1.

Stąd możemy już wywnioskować:

• Wiemy, że wyrażenie jest prawdziwe dla n = 1.
• Jeśli jest prawdziwe dla n, musi być prawdziwe także dla n + 1, czyli także dla 1 + 1, czyli wyrażenie jest prawdziwe także dla n = 2.
• Jeśli jest prawdziwe dla n, musi być prawdziwe także dla n + 1, czyli także dla 2 + 1, czyli wyrażenie jest prawdziwe także dla n = 3.
• Jeśli jest prawdziwe dla n, musi być prawdziwe także dla n + 1, czyli także dla 3 + 1, czyli wyrażenie jest prawdziwe także dla n = 4.
• Jeśli jest prawdziwe dla n, musi być prawdziwe także dla n + 1, czyli także dla 4 + 1, czyli wyrażenie jest prawdziwe także dla n = 5.
• …

Drugi przykład

Teraz udowodnimy indukcją matematyczną proste twierdzenie:

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

Najpierw krok bazowy: sprawdzimy, czy twierdzenie jest prawdziwe dla n = 1, czyli dla najmniejszej dodatniej liczby naturalnej. Indukcję prowadzimy tu od n = 1, czyli dowodzimy twierdzenia dla n≥1, bo krok indukcyjny poniżej korzysta z nierówności 2^a≥2, która dla a = 0 nie zachodzi. Jeśli zaliczamy do liczb naturalnych także zero, przypadek n = 0 sprawdzimy osobno: 2⁰ = 1≥0 = 2 · 0, więc i dla zera twierdzenie jest prawdziwe.

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

To jest w oczywisty sposób prawdziwe. Teraz przejdziemy do kroku indukcyjnego, w którym musimy sprawdzić, czy jeśli twierdzenie jest prawdziwe dla n = a, to jest prawdziwe także dla n = a + 1. Nasze założenie indukcyjne brzmi więc

$$2^a\ge2a$$

a teza indukcyjna, którą chcemy udowodnić:

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

Lewą stronę najpierw rozpiszemy za pomocą reguł działań na potęgach, a prawą stronę po prostu wymnożymy.

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

Po lewej stronie zamiast mnożenia użyjemy dodawania, prawą zostawimy bez zmian.

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

Teraz skorzystamy z założenia. Założenie to zdanie, o którym zakładamy, że jest prawdziwe. W nierówności mamy po obu stronach po dwa wyrażenia, które są dodawane. Jednocześnie jednak wiemy, że

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

Pierwszy wiersz mówi nam założenie, a drugie zdanie jest trywialne (dla a≥1 najmniejsze 2^a jest dla a = 1 i wynosi właśnie dwa). Wiemy więc, że oba wyrazy po lewej stronie są nie mniejsze niż odpowiadające im wyrazy po prawej stronie. Tym samym udowodniliśmy indukcyjnie, że jeśli wyrażenie jest prawdziwe dla a, to jest prawdziwe także dla (a + 1), a ponieważ jest prawdziwe także dla jedynki, dane wyrażenie jest prawdziwe dla wszystkich n≥1 (a zero sprawdziliśmy osobno).

Trzeci przykład

Spróbujemy udowodnić następujące twierdzenie:

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

Słownie: jeśli n jest podzielne przez trzy, to także n² jest podzielne przez trzy. Jeśli n nie jest podzielne przez trzy, to wyrażenie jest w oczywisty sposób prawdziwe (z definicji implikacji), więc zajmiemy się przypadkami, w których n jest podzielne przez trzy. To wyznacza ciąg liczb naturalnych a_i=3, 6, 9, 12, 15… Od tej chwili będziemy się poruszać w tym ciągu a_i.

Dowód indukcyjny zaczniemy od kroku bazowego, czyli od tego, czy twierdzenie jest prawdziwe dla pierwszego elementu. Przypominam, że poruszamy się w ciągu a_i, więc bierzemy pierwszy wyraz tego ciągu, czyli wyraz a₁, a to jest trójka. Dla trójki wyrażenie jest prawdziwe:

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

Jeśli zaliczamy do liczb naturalnych także zero, ciąg a_i zaczyna się od zera, a wtedy krok bazowy jest dla n = 0: $3\mid0\Rightarrow 3\mid0^2$, co też jest prawdą, bo zero jest podzielne przez trzy. Krok indukcyjny jest w obu przypadkach taki sam.

Teraz przejdziemy do kroku indukcyjnego. Widzimy, że ciąg a_i dałoby się zapisać jako 3n, gdzie n jest liczbą naturalną. Każdy kolejny wyraz jest więc o trzy większy od poprzedniego. Załóżmy teraz, że wyrażenie jest prawdziwe dla n, i musimy zapewnić, żeby było prawdziwe także dla (n + 3), bo to jest przepis, który daje następny wyraz ciągu, w którym się poruszamy. Zapiszemy najpierw założenie indukcyjne:

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

a potem tezę indukcyjną, którą chcemy udowodnić

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

Nawias po drugiej stronie rozwiniemy ze wzoru:

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

I już jesteśmy prawie u celu. Po lewej stronie mamy wyrażenie, które na pewno jest podzielne przez trzy, bo n jest zgodnie z założeniem podzielne przez trzy (poruszamy się tylko w liczbach z ciągu a_i), a trójka też jest podzielna przez trzy. Po prawej stronie mamy najpierw n², które zgodnie z założeniem jest podzielne przez trzy. Wiemy bowiem, że n jest podzielne przez trzy, a założenie mówi, że jeśli n jest podzielne przez trzy, to także n² jest podzielne przez trzy:

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

Dalej jest wyrażenie 6n, które jest w oczywisty sposób podzielne przez trzy. Możesz to sobie wyobrazić jako skracanie ułamka:

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

Zmienna n jest jakąś liczbą naturalną, więc także iloczyn 2n będzie liczbą naturalną, czyli po podzieleniu przez trzy dostaliśmy liczbę naturalną, a zatem wyrażenie 6n musi być podzielne przez trzy. A dziewiątka na końcu też jest podzielna przez trzy. Wyrażenie jest prawdziwe dla pierwszego elementu i w kroku indukcyjnym, jest więc prawdziwe.

Liczba nawiasów w wyrażeniu

Ostatni przykład będzie trochę nietypowy. Spróbujemy udowodnić twierdzenie, że liczba nawiasów w prostym wyrażeniu jest zawsze parzysta, żebyś zobaczył, że indukcję matematyczną można zastosować także w zupełnie innym kontekście niż same liczby naturalne. Na początku musimy zdefiniować, czym jest proste wyrażenie. Proste wyrażenie to:

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

Prostymi wyrażeniami są więc na przykład: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). A to z kolei nie są proste wyrażenia:

• 1 + 2 $\rightarrow$ brakuje zewnętrznych nawiasów,
• (1 + 2 $\rightarrow$ brakuje prawego nawiasu,
• 13² $\rightarrow$ brakuje zewnętrznych nawiasów,
• (1 + 2 + 3) $\rightarrow$ brakuje nawiasów, poprawny zapis to (1+(2 + 3))

Proste wyrażenie może powstać na przykład tak. Na początku wybierzemy proste wyrażenie (a + b). Teraz za a podstawimy proste wyrażenie a = (c + d), więc dostaniemy ((c + d)+b), a za b podstawimy trójkę: ((c + d)+3). Za c podstawimy dziesiątkę: ((10 + d)+3), a na koniec za d podstawimy (5²): ((10+(5²))+3). Ważne jest pilnowanie nawiasów, inaczej to nie zadziała.

Teraz udowodnimy, że proste wyrażenie zawiera parzystą liczbę nawiasów (do liczb parzystych zalicza się także zero).

W kroku bazowym wybierzemy jakiś pierwszy element. W tym przypadku pierwszym elementem będzie najprostsze proste wyrażenie, czyli dowolna liczba naturalna. Przyjmiemy więc

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

Wyrażenie j ma zero nawiasów, więc pierwszy element spełnia twierdzenie. W kroku indukcyjnym założymy, że mamy dwa proste wyrażenia p i q i że oba mają parzystą liczbę nawiasów. Musimy wtedy udowodnić, że także proste wyrażenia (p + q) i (p²) mają parzystą liczbę nawiasów.

Najpierw dodawanie. Zdefiniujemy sobie jeszcze funkcję z(q), która zwraca liczbę nawiasów wyrażenia q. Wtedy wyrażenie (p + q) ma z(p)+z(q)+2 nawiasów. Ma więc o dwa nawiasy więcej, niż wynosi suma nawiasów wyrażeń p i q. Zgodnie z założeniem z(p) i z(q) są parzyste, a jeśli dodamy trzy liczby parzyste, dostaniemy znowu liczbę parzystą. W tym przypadku zdanie jest więc prawdziwe.

Teraz potęga. Znowu obowiązuje założenie, że proste wyrażenie p zawiera parzystą liczbę nawiasów. Wyrażenie (p²) zawiera wtedy z(p)+2 nawiasów, czyli znowu o dwa nawiasy więcej niż wyrażenie p. Także w tym przypadku dodajemy liczby parzyste, więc wynik jest parzysty.

Zdanie jest prawdziwe dla pierwszego elementu i zachodzi także w kroku indukcyjnym, więc jest prawdziwe.