Indukcja matematyczna jest to metoda, która pozwala udowodnić, że zdanie dotyczące liczb naturalnych jest prawdziwe dla wszystkich liczb naturalnych. Jest to więc narzędzie pozwalające udowodnić nieskończoną liczbę zdań prawdziwych w skończonym czasie i skończonym nakładem pracy.

Jeśli przeczytaliśmy ze zrozumieniem wykład 1, i jeśli z tego, że zrozumieliśmy wszystkie wykłady do i-tego wynika, że z łatwością zrozumiemy wykład (i+1)-szy, to na mocy zasady indukcji matematycznej, łatwo uporamy się z wszystkimi wykładami z Matematyki Dyskretnej. Jeśli Czytelnik rozumie tego typu rozumowania, to osiągnęliśmy cel tego wykładu.

Na zakończenie chcielibyśmy podkreślić, że żadnego etapu dowodu indukcyjnego nie można pominąć, baza indukcji jest tak samo ważna jak krok indukcyjny. Przy definiowaniu przez indukcję lub definicjach rekurencyjnych warto zwrócić uwagę na nakład pracy związany z wykonaniem wywołań rekurencyjnych. Bardzo często algorytmy napisane w sposób rekurencyjny, chociaż mają krótszy kod i bardziej elegancką strukturę, to zabierają o wiele więcej czasu niż odpowiadające im algorytmy iteracyjne.

Uwagi bibliograficzne:

Wiele przykładów zastosowania metody niezmienników do analizy algorytmów znajdzie Czytelnik w pracach:

• Banachowski L., Kreczmar A., Analiza algorytmów, WNT,

• Mirkowska G., Salwicki A., Logika dla programistów, WNT, 1992,

• Cormen T., Leiserson Ch., Rivest R., Introduction to Algorithms.

• Więcej o indukcji matematycznej można przeczytać w książce Ross K., B.Wright Matematyka Dyskretna.