Logo Serwisu Media Nauka

Indukcja matematyczna, indukcja zupełna

Teoria Indukcja matematyczna (zupełna) jest to metoda dowodzenia twierdzeń o liczbach naturalnych.

Niech T(n) oznacza formę zdaniową zmiennej n określoną w dziedzinie liczb naturalnych. W zależności od wartości n forma zdaniowa może być prawdziwa lub fałszywa.

Zasada indukcji matematycznej
1) Istnieje taka liczba naturalna n0, że T(n0) jest zdaniem prawdziwym
2) Dla każdej liczny naturalnej n≥n0 prawdziwa jest implikacja T(n)\Rightarrow{T(n+1)}

Zatem dowód indukcyjny jest dwuetapowy i polega na:

1) sprawdzeniu, czy zdanie T(n0) jest prawdziwe
2) (krok indukcyjny) założeniu, że prawdziwe jest zdanie T(n) dla n≥n0 (założenie indukcyjne) i dowiedzeniu na tej podstawie prawdziwości zdania T(n+1) (teza indukcyjna)

Zrozumienie indukcji matematycznej nie jest łatwe, ale bardzo często przydaje się przy dowodzeniu twierdzeń matematycznych. Przeanalizujmy przykład dowodu indukcyjnego.

Przykład Przykład

Udowodnić, że dla każdej liczby naturalnej (bez zera) prawdziwa jest równość:

1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}

Widzimy, że n0=1

1) Sprawdzamy, czy T(n0)=T(1) jest prawdziwe:

1^2=\frac{1\cdot(1+1)(2\cdot{1}+1)}{6}\\1=\frac{2\cdot{3}}{6}\\1=1

Zdanie T(1) jest prawdziwe.

2) Formułujemy założenie indukcyjne oraz tezę:

ZAŁOŻENIE: zakładamy, że zdanie 1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}jest prawdziwe
TEZA: 1^2+2^2+3^2+...+n^2+(n+1)^2=\frac{(n+1)[(n+1)+1][2(n+1)+1]}{6}=\frac{(n+1)(n+2)(2n+3)}{6}

Musimy udowodnić prawdziwość tego zdania.
Wyjdźmy od lewej strony równania (L) i wykorzystajmy założenie (podkreślona część wyrażenia to nic innego jak nasze założenie):
L=\underline{1^2+2^2+3^2+...+n^2}+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\\=\frac{n+1}{6}[n(2n+1)+6(n+1)]=\frac{n+1}{6}(2n^2+7n+6)=\frac{n+1}{6}[2(n+2)(n+\frac{3}{2})]=\\=\frac{n+1}{6}[(n+2)(2n+3)]=\frac{(n+1)(n+2)(2n+3)}{6}=P
A więc otrzymaliśmy prawą stronę równania (P), czego należało dowieść.

Rachunki pomocnicze: Rozłożenie trójmianu 2n^2+7n+6na czynniki:
\Delta=49-48=1\\n_1=\frac{-b-sqrt{\Delta}}{2a}=\frac{-7-1}{4}=-2\\n_2=\frac{-b+sqrt{\Delta}}{2a}=\frac{-7+1}{4}=-\frac{3}{2}\\2n^2+7n+6=2(n+2)(n+\frac{3}{2})

Przykład Przykład

Udowodnić, że dla każdej liczby naturalnej (bez zera) liczba n5-n jest podzielna przez 5:

Widzimy, że n0=1
1) Sprawdzamy, czy T(n0)=T(1) jest prawdziwe:
n05-n0=1-1=0
Zdanie T(1) jest prawdziwe.

2) Formułujemy założenie indukcyjne oraz tezę:
ZAŁOŻENIE: zakładamy, że liczba n5-n jest podzielna przez 5
TEZA: Liczba (n+1)5-(n+1)

Musimy udowodnić prawdziwość tego zdania.
Obliczmy wartość tego wyrażenia:
(n+1)^5-(n+1)=(n+1)[(n+1)^4-1]=
Wyjęliśmy czynnik n+1 przed nawias, a teraz skorzystajmy ze wzoru skróconego mnożenia na różnicę kwadratu liczb:
=(n+1)[(n+1)^2-1][(n+1)^2+1]=(n+1)(n+1-1)(n+1+1)(n^2+2n+1+1)=\\n(n+1)(n+2)(n^2+2n+2)=
Wymnażamy wszystkie liczby przez siebie:
=(n^2+n)(n+2)(n^2+2n+2)=(n^3+2n^2+n^2+2n)(n^2+2n+2)=\\=n^5+5n^4+10n^3+10n^2+4n=
Nie skorzystaliśmy jeszcze z założenia, że n5-n jest podzielne przez 5. Nie mamy tutaj wprost takiego wyrazu, ale możemy wyrazić czynnik 4n jako 5n-n:
=n^5+5n^4+10n^3+10n^2+5n-n=\underline{n^5-n}+5n^4+10n^3+10n^2+5n
Zauważmy, że liczba ta jest podzielna przez 5, gdyż podkreślony człon, to z założenia liczba podzielna przez 5, a każdy następny wyraz wyrażenia też jest liczbą podzielną przez 5.


© medianauka.pl, 2016-07-02, ART-296







Polecamy koszyk



© Media Nauka 2008-2017 r.