Indukcja matematyczna
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.
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.
Powiązane quizy
© medianauka.pl, 2016-07-02, A-296
Data aktualizacji artykułu: 2023-02-12