+ Pokaż spis treści

Indukcja matematyczna


Indukcja matematyczna jest metodą dowodzenia twierdzeń o liczbach naturalnych.
Niech  oznacza twierdzenie, w którym jest mowa o liczbach naturalnych.
 
Zasada indukcji matematycznej
 
Jeżeli istnieje taka liczba naturalna , dla której:
1. twierdzenie  jest prawdziwe,
2. Dla każdej liczby naturalnej  z prawdziwości twierdzenia  wynika prawdziwość
twierdzenia , to twierdzenie  jest prawdziwe dla każdej liczby naturalnej .
 
 
Dowód przeprowadzany metodą indukcji matematycznej nazywamy dowodem indukcyjnym. Postępuje się przy nim w następujący sposób:
 
1. Określa się najmniejszą liczbę naturalną , dla której twierdzenie ma być prawdziwe, a następnie
sprawdza się, czy rzeczywiście dane twierdzenie jest prawdziwe dla  (metodą podstawienia liczby  w miejsce zmiennej  w twierdzeniu).
 
2. Zakłada się, że twierdzenie jest prawdziwe dla dowolnej liczby  (jest to tzw. założenie 
indukcyjne).
 
3. Dowodzi się, że twierdzenie jest prawdziwe dla następnej liczby naturalnej tzn. dla .
 
4. Na mocy indukcji matematycznej wnosi się, że twierdzenie jest prawdziwe dla każdej liczby 
naturalnej .
 
 
Przykład:
Udowodnić, że dla każdej liczby naturalnej n prawdziwa jest równość: 
 

Rozwiązanie:
Skorzystamy z zasady indukcji matematycznej.
 
1. Wyznaczamy najmniejszą liczbę, dla której równość jest prawdziwa. Z postaci pierwszego i ostatniego składnika  sumy wnioskujemy, że , a więc . Dla  sprawdzamy prawdziwość danej równości:
 
     i      ,
 
a więc , gdzie  i  oznaczają odpowiednio lewą i prawą stronę równości.
 
2. Zakładamy, że równość jest spełniona dla dowolnej liczby naturalnej , tzn. prawdziwa jest równość:
 
  (założenie indukcyjne).
 
3. Udowodnimy, że prawdziwa jest równość dla  tzn.: 
 
(teza indukcyjna).
Dowód:
 
Przekształcamy lewą stronę tezy korzystając z założenia indukcyjnego:
 
 =  =
 
.
 
4. Udowodniliśmy, że z prawdziwości równości dla dowolnej liczby naturalnej  wynika prawdziwość tej równości dla liczby następnej  oraz, że równość jest prawdziwa dla liczby , więc na mocy indukcji matematycznej wnosimy, że równość jest prawdziwa dla każdej liczby naturalnej .