Ponieważ przeprowadzania dowodów indukcyjnych najłatwiej się nauczyć, oglądając przykłady, zobaczmy kilka porządnie opisanych przykładów.
Udowodnić, że dla dowolnej liczby naturalnej n liczba 11n + 1 + 122n − 1 jest podzielna przez 133.
Rozwiązanie
Liczba naturalna jest podzielna przez 133 wtedy i tylko wtedy, gdy można ją zapisać jako iloczyn 133⋅k, gdzie k jest liczbą naturalną. Wobec tego chcemy udowodnić, że dla dowolnego n∈N istnieje k∈N takie, że 11n + 1 + 122n − 1 = 133k.
Dowodzimy przez indukcję.
1. Sprawdzamy dla n = 1: 112+12=121+12=133=133⋅1.
2. Załóżmy, że udowodniliśmy tezę dla liczb naturalnych od 1 do n, dowodzimy dla n + 1.
Zauważmy, że 11(n+1)+1+122(n+1)−1=11⋅11n+1+122⋅122n−1=11⋅11n+1+(133+11)⋅122n−1=11⋅(11n+1+122n−1)+133⋅122n−1.
Korzystamy z założenia indukcyjnego: istnieje liczba naturalna k taka, że 11n + 1 + 122n − 1 = 133k.
Wobec tego powyższe wyrażenie jest równe 11⋅133⋅k+133⋅122n−1=133⋅(11k+122n−1), czyli jego wartość jest podzielna przez 133 (ponieważ wartość wyrażenia w nawiasie jest liczbą całkowitą).
Na mocy zasady indukcji matematycznej teza zadania jest prawdziwa dla dowolnego n∈N.
Dla jakich n∈N zachodzi nierówność 3n > n3?
Rozwiązanie
Rowiązywanie zadań, w których treść wymaga znalezienia wszystkich wartości, dla których pewien warunek jest spełniony, warto rozpoczynać od zbadania zachowania tego warunku dla niedużych wartości. Wobec tego sprawdzamy daną nierówność dla małych n.
n = 1: 31 > 13 - zgadza się;
n = 2: 32 = 9 > 23 = 8 - zgadza się;
n = 3: po obu stronach mamy 33 = 27 - jest równość zamiast ostrej nierówności, czyli dla 3 nierówność nie jest spełniona;
n = 4: 34 = 81 > 43 = 64;
n = 5: 35 = 243 > 53 = 125...
Można się spodziewać, że dla większych wartości n lewa strona nierówności będzie rosła dużo szybciej niż prawa, więc nierówność będzie spełniona. Ale trzeba to udowodnić!
Przeprowadzimy dowód indukcyjny.
1. Zaczniemy indukcję od n = 4, ponieważ dla mniejszych liczb nierówność nie zawsze jest spełniona.
2. Załóżmy, że udowodniliśmy tę nierówność dla liczb od 4 do n, dowodzimy dla n + 1.
Chcemy wykazać, że 3n + 1 > (n + 1)3. Zapisujemy 3n + 1 jako 3⋅3n i korzystamy z założenia indukcyjnego, otrzymując 3⋅3n>3⋅n3.
Żeby wykazać tezę dla n + 1, wystarczy więc udowodnić nierówność 3n3 > (n + 1)3, czyli 3n3 > n3 + 3n2 + 3n + 1, co jest równoważne 2n3 > 3n2 + 3n + 1 (1).
Zauważmy, że jeśli n > 3, to n3 > 3n2 oraz n3 > 3n + 1 (ponieważ n3−3n=n(n2−3)≥n⋅1>1).
Sumując stronami te dwie nierówności otrzymujemy nierówność (1), co kończy dowód kroku indukcyjnego.
Na mocy zasady indukcji matematycznej nierówność 3n > n3 jest prawdziwa dla wszystkich liczb naturalnych n≥4. Ponadto z bezpośredniego sprawdzenia wynika, że ta nierówność jest spełniona również dla n = 1 i n = 2, natomiast nie zachodzi dla n = 3.
Wykazać, że n-kąt wpisany w okrąg ma n(n−3)2 przekątnych.
Uwaga: Do czego potrzebne jest założenie, że wielokąt ma być wpisany w okrąg? Wielokąt spełniający ten warunek ma dobre własności. Nie mogą się w nim zdarzyć dziwne sytuacje, np. takie, że przekątna wychodzi poza wnętrze wielokąta, czy że pewne przekątne częściowo się pokrywają. Można tutaj z pewnością wypisać słabsze założenia, ale nie chodzi nam o to, żeby sprawdzić, jak bardzo ogólny jest ten wzór, ale żeby zobaczyć, jak opisać liczbę przekątnych w przypadku porządnych wielokątów.
Rozwiązanie
Zastosujemy zasadę indukcji matematycznej.
1. Sensowny początek indukcji to n = 3 - trudno określić, czym miałby być wielokąt o jednym lub dwóch wierzchołkach i bokach. Dla n = 3 we wzorze mamy 3(3−3)2=0, czyli liczbę przekątnych trójkąta.
2. Załóżmy, że wykazaliśmy tezę dla liczb od 3 do n, dowodzimy dla n + 1.
Wybierzmy trzy kolejne wierzchołki n + 1-kąta. Oznaczmy je A, B i C, jak na rysunku. Rysując przekątną łączącą A i C odcinamy od wielokąta trójkąt ABC. Otrzymujemy w ten sposób n-kąt wpisany w okrąg. Z założenia indukcyjnego liczba przekątnych w tym n-kącie wynosi n(n−3)2 - oczywiście wszystkie te przekątne są również przekątnymi wyjściowego n + 1-kąta.
Musimy się tylko zastanowić, ile przekątnych straciliśmy, odcinając trójkąt ABC. Są to przekątne wychodzące z wierzchołka B oraz odcinek AC. Drugim końcem przekątnej wychodzącej z punktu B może być dowolny wierzchołek n + 1-kąta poza A, B i C (dla A i C zamiast przekątnych otrzymalibyśmy boki). Takich wierzchołków jest n + 1 − 3 = n − 2, więc jeszcze nie policzonych przekątnych jest n − 1.
Wobec tego wszystkich przekątnych n + 1-kąta jest n(n−3)2+n−1=n2−3n+2n−22=n2−n−22=(n+1)(n−2)2, co należało udowodnić.
Na mocy zasady indukcji matematycznej teza twierdzenia jest prawdziwa dla dowolnego n∈N, n≥3.
Rozwiązanie drugie, nieindukcyjne.
Policzmy najpierw przekątne wychodzące z wybranego wierzchołka A. Drugim końcem takiej przekątnej może być dowolny wierzchołek n-kąta oprócz A i jego dwóch sąsiadów, czyli z każdego wierzchołka wychodzą n − 3 przekątne. Mnożąc tę liczbę przez liczbę wierzchołków wielokąta każdą przekątną policzymy dwa razy - raz dla każdego jej końca. Wobec tego liczba wszystkich przekątnych to połowa tego, co otrzymamy, zliczając dla wszystkich wierzchołków wychodzące z nich przekątne, czyli n(n−3)2.
To rozwiązanie jest od poprzedniego istotnie krótsze w zapisie, ale żeby je napisać, najpierw trzeba mieć pomysł. Rozwiązania indukcyjne często wymagają mniej pomysłowości, ale za to nieco więcej rachunków.
Udowodnić, że dla każdej liczby naturalnej n zachodzi nierówność:
1n+1+1n+2+…+13n+1≥1.
Rozwiązanie
Prowadzimy dowód przez indukcję względem n.
1. Sprawdźmy nierówność dla n = 1: 12+13+14=1312≥1
2. Załóżmy, że udowodniliśmy daną nierówność dla liczb naturalnych od 1 do n, dowodzimy dla n + 1. Lewa strona to 1(n+1)+1+1(n+1)+2+…+13(n+1)+1=1n+2+1n+3+…+13n+4.
Ta suma jest bardzo podobna do sumy z lewej strony nierówności dla n - różnią się one tylko o kilka wyrazów. Dokładniej, jeśli przez Lk oznaczymy lewą stronę nierówności dla n = k, to Ln+1=Ln−1n+1+13n+2+13n+3+13n+4≥1−1n+1+13n+2+13n+3+13n+4, gdzie nierówność otrzymujemy korzystając z założenia indukcyjnego.
Wobec tego żeby udowodnić, że Ln+1≥1, wystarczy wykazać, że 1−1n+1+13n+2+13n+3+13n+4≥1. Ta nierówność jest równoważna 13n+2+13n+3+13n+4≥1n+1.
Wykonując dodawanie przekształcamy ją do postaci 27n2+54n+26(3n+2)(3n+3)(3n+4)≥1n+1
i dalej 27n2+54n+263(3n+2)(3n+4)≥1,
czyli równoważnie 27n2+54n+26≥3(3n+2)(3n+4).
Rozwijając prawą stronę otrzymujemy 27n2+54n+26≥27n2+54n+24, a ta nierówność jest prawdziwa dla każdej liczby naturalnej n, co na mocy zasady indukcji matematycznej dowodzi tezy.
Z dowodami indukcyjnymi trzeba czasami uważać - może się zdarzyć, że pominiemy jakiś ważny szczególny przypadek, przez co cały dowód okaże się błędny...
"Twierdzenie": Wszystkie koty są tego samego koloru. (W tym twierdzeniu przenosimy się do świata, gdzie koty są jednokolorowe.)
"Dowód": Wystarczy wykazać, że w dowolnym zbiorze zawierającym n kotów, gdzie n jest dowolną liczbą naturalną, wszystkie koty mają ten sam kolor.
1) Podstawa indukcji to sprawdzenie dla n = 1: oczywiście w zbiorze zawierającym tylko jednego kota wszystkie koty są tego samego koloru.
2) Załóżmy, że udowodniliśmy twierdzenie dla wszystkich liczb naturalnych od 1 do n − 1, dowodzimy dla n. Weźmy dowolny zbiór A zawierający n kotów. Pokażemy, że koty ze zbioru A są tego samego koloru.
Wyrzucając z A pewnego kota X otrzymamy zbiór zawierający n − 1 kotów - możemy skorzystać z założenia indukcyjnego, żeby stwierdzić, że wszystkie koty w A oprócz X mają ten sam kolor. Ale teraz, wyrzucając z A kota Y (innego niż X), wnioskujemy z założenia indukcyjnego, że kot X ma ten sam kolor, co pozostałe koty w A. Wobec tego wszystkie koty w A mają ten sam kolor.
Zatem na mocy zasady indukcji matematycznej wszystkie koty są tego samego koloru.
Podczas dowodu zapewne większość osób wyobraża sobie zbiór A większy niż dwuelementowy (jak na rysunku). Dla takiego zbioru rozumowanie z kroku indukcyjnego jest poprawne, ale nic z tego nie wynika, bo nie działa ono dla n = 2. Wobec tego nie mamy podstawy do stosowania indukcji. Umiemy sprawdzić przypadek n = 1, a krok indukcyjny działa dopiero od n = 3 - przerwa pomiędzy tymi wartościami powoduje, że dowód jest zupełnie bez sensu.