Indukcja matematyczna

Indukcja matematyczna (indukcja 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 \(n_0)\), że \(T(n_0)\) jest zdaniem prawdziwym
2) Dla każdej liczny naturalnej \(n\geq n_0\) prawdziwa jest implikacja \(T(n) \Rightarrow T(n+1)\)

Zatem dowód indukcyjny jest dwuetapowy i polega na:

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

Przykłady

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

Przykład 1

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 \(n_0=1\)

1) Sprawdzamy, czy \(T(n+0)=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+6\) na 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 2

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

Widzimy, że \(n_0=1\)
1) Sprawdzamy, czy \(T(n_0)=T(1)\) jest prawdziwe:
\(n_0^5-n_0=1-1=0\)
Zdanie \(T(1)\) jest prawdziwe.

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

ZAŁOŻENIE:

Zakładamy, że liczba \(n^5-n\) jest podzielna przez 5.

TEZA:

Liczba \((n+1)^5-(n+1)\) jest podzielna przez 5.

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 \(n^5-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.