Indukcja matematyczna jest jednym z podstawowych narzędzi służącym do dowodzenia twierdzeń w matematyce i nie tylko. Pokażemy, że i informatyka nie może się obyć bez indukcji, zarówno na etapie definiowania pojęć i algorytmów jak i dowodzenia własności programów.

Prawdopodobnie każdy z nas ustawiał kiedyś "płotek" z kamieni do gry w domino. Jeśli kamienie ustawimy dostatecznie blisko jeden obok drugiego i pierwszy z nich lekko popchniemy, to pierwszy kamień popchnie drugi, który przewracając się potrąci trzeci itd. W rezultacie cały "płotek" przewróci się. Proces przewracania się kamieni domina oddaje dość dobrze ideę zasady indukcji (Rys. 9.0).

Rys. 9.0 Zasada indukcji.

Indukcja matematyczna przypomina też wdrapywanie się na drabinę. Jeśli umiemy wejść na pierwszy stopień, i będąc na dowolnym stopniu drabiny umiemy się wspiąć na stopień następny, to możemy się wspiąć dowolnie wysoko.

W tym wykładzie będziemy mówili o różnych sformułowaniach zasady indukcji matematycznej i przedstawimy dowody twierdzeń wykorzystujących tę zasadę. Pokażemy sposoby definiowania nowych pojęć przez indukcję i sformułujemy ogólną zasadę tworzenia definicji rekurencyjnych. Na zakończenie, przedstawimy pojęcie niezmiennika, służące do analizy zachowania algorytmów i związek tego pojęcia z rozumowaniem indukcyjnym.