Indukcja matematyczna
Indukcja matematyczna to jedna z metod dowodzenia twierdzeń o liczbach naturalnych. Użycie tej metody jest bardzo proste, gdyż dowód przedstawiamy tylko w 2 krokach używając podstaw matematyki.
Indukcję matematyczną można porównać do kostek domina. Po przewróceniu się pierwszej kostki następuje przewrócenie następnej.
2 zasady indukcji matemtycznej to:
- Istnieje taka liczba naturalna (np \(n_0\)), dla której podany wzór \(T(n_0)\) jest prawdziwy. Innymi słowy sprawdzamy czy \(T(n_0)\) jest prawdziwe dla wybranej liczby naturalnej.
- Zakładamy, że \(T(n_0)\) jest prawdziwe i dla każdej liczby naturalnej większej od \(n_0\) prawdziwa jest implikacja \(T(n)\Rightarrow{T(n+1)}\). Innymi słowy sprawdzamy prawdziwość wzoru \(T(n_0)\) czy \(n+1\) jest prawdziwe.
Indukcję matematyczną nazywamy również indukcją zupełną, a najczęściej używana jest ona w dowodzeniu równań i nierówności.
Przykład
Udowodnij, że dla dowolnej liczby naturalnej \(n\) prawdziwe będzie równanie:
\(1+4+7+...+(3n-2)={{n(3n-1)}\over 2}\)
Warunek 1: Sprawdzamy, czy równość jest prawdziwa dla \(n=1\)
\(L=3\cdot1-2\)
\(L=1\)
\(P= {{1 \cdot (3\cdot1-1)}\over 2}\)
\(L=P\)
Lewa strona jest równa prawej, więc równość jest prawdziwa dla \(n=1\)
Warunek 2: Udowadniamy, że prawdziwa jest implikacja
Założenie (za \(n\) podkładamy \(k\)), że równość jest prawdziwa dla liczby \(k\):
\(1+4+7+...+(3k-2)={{k(3k-1)}\over 2}\)
Teza - równość jest prawdziwa dla liczby \(k+1\):
\(1+4+7+...+(3k-2)+(3(k+1)-2)={{(k+1)(3(k+1)-1)}\over 2}\)
Uzasadnienie:
\(P={{(k+1)(3(k+1)-1)}\over 2}={{(k+1)(3k+2)}\over 2}\)
\(P={{3k^2+5k+2}\over 2}=1{1\over2}k^k+2{1\over2}k+1\)
\(L=\underbrace {1+4+7+...+(3k-2)}_{{k(3k-1)}\over 2}+(3(k+1)-2)\)
\(L={{k(3k-1)}\over 2}+(3(k+1)-2)\)
\(L={{3k^2-k}\over 2}+3k+1={{1{1\over2}k^2-{1\over2}k}}+3k+1\)
\(L={{1{1\over2}k^2+2{1\over2}k}}+1\)
\(L=P\)
Wykazaliśmy, że dla dowolnej liczby \(k\) implikacja jest prawdziwa.
Powiązane tematy