W dowodzeniu twierdzeń bardzo przydatna bywa zasada indukcji matematycznej.
Chcemy dowieść prawdziwości zdania \(T(n)\). W tym celu musimy zrobić dwa kroki:
(1) sprawdzić, że zdanie \(T(n)\) jest prawdziwe dla jakiegoś konkretnego \(n_{0}\).
(2) pokazać, że ze zdania \(T(n)\) wynika zdanie \(T(n+1)\).
Po wykonaniu tych dwóch kroków został przeprowadzony dowód prawdziwości zdania \(T(n)\) dla wszystkich \(n \ge n_{0}\).
Przykład:
Udowodnić, że suma kwadratów kolejnych \(n\) liczb nieparzystych ma postać \( \frac{4n^{3}-n}{3} \).
Posłużymy się zasadą indukcji matematycznej. Sprawdźmy, czy zdanie jest prawdziwe dla \(n = 1\).
\(1^{2}=1\).
\( \frac{4 \cdot 1^{3}-1}{3} = \frac{4-1}{3} = \frac{3}{3} = 1\).
Dla \(n = 1\) twierdzenie jest prawdziwe.
Pozostaje pokazać, że z prawdziwości tego twierdzenia dla \(n\) wynika jego prawdziwość dla \(n+1\).
Rozpiszmy to zdanie.
\(1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} = \frac{4n^{3}-n}{3}\) - to jest nasze wyjściowe zdanie dla \(n\). Jednocześnie jest to założenie, z którego będziemy potem korzystać.
\(1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} +(2(n+1)-1)^{2} = \frac{4(n+1)^{3}-(n+1)}{3}\) - to jest wyjściowe twierdzenie dla \(n+1\).
Przekształćmy prawą stronę tego drugiego zdania. Korzystać będziemy ze wzoru skróconego mnożenia (na sześcian sumy).
\(\frac{4(n+1)^{3}-(n+1)}{3} = \frac{4(n^{3}+3n^{2}+3n+1)-n-1}{3} = \frac{4n^{3}+12n^{2}+12n+4-n-1}{3} = \frac{4n^{3}+12n^{2}+11n+3}{3}\).
Teraz zajmijmy się lewą stroną.
\(1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} +(2(n+1)-1)^{2} = \frac{4n^{3}-n}{3} + (2n+2-1)^{2} \) - korzystając z założenia przekształciliśmy lewą stronę zdania. Teraz (korzystając ze wzoru skróconego mnożenia na kwadrat sumy) przekształcimy ją dalej.
\(\frac{4n^{3}-n}{3} + (2n+1)^{2} =\frac{4n^{3}-n}{3} + 4n^{2}+4n+1\).
Ostatnim etapem jest doprowadzenie tej strony do postaci takiej samej jak prawa strona. W tym celu sprowadzimy wyrażenie do wspólnego mianownika.
\( \frac{4n^{3}-n+12n^{2}+12n+3}{3} = \frac{4n^{3}+12n^{2}+11n+3}{3}\) - lewa strona równania jest taka sama jak prawa, zatem twierdzenie jest prawdziwe.
Żeby lepiej zrozumieć zasadę indukcji matematycznej wygodnie jest kojarzyć ją z kostkami domina. Żeby przewrócić wszystkie kostki potrzebne są nam dwie rzeczy:
(1) przewrócenie pierwszej, oraz
(2) gwarancja, że przewrócenie danej kostki przewróci kostkę stojącą za nią.