30 (285)

1 » Liczby I ich zbiory

1.8. INDUKCJA MATEMATYCZNA

1.8.1. Indukcja przyrodnicza a indukcja matematyczna

(Indukcja przyrodnicza (niezupełna) to rozumowanie uogólniające, prowadzące do sformułowania ogólnego twierdzenia na podstawie obserwacji skończonej liczby przypadków. Jednak takie rozumowanie nie jest niezawodne. Stosowanie indukcji przyrodniczej w matematyce upoważnia jedynie do sformułowania hipotezy, którą następnie należy udowodnić, w matematyce zaś stosujemy indukcję matematyczną. Indukcja matematyczna (zupełna) jest to metoda dowodzenia twierdzeń dotyczących liczb naturalnych.

A Tli

neN '

Założenie

li

Teza

1.8.2. Zasada indukcji matematycznej

Niech 7' ( n ) oznacza twierdzenie dotyczące liczb naturalnych. Wówczas prawdziwe jest następujące twierdzenie zwane zasadą indukcji matematycznej:

Jeżeli:

I * twierdzenie jest prawdziwe dla ustalonej liczby naturalnej n_Q (np. n_c = O V n₀= 1 V n_Q = 2), czyli zachodzi 7'(/t₀),

i 2* z prawdziwości twierdzenia dla dowolnej liczby naturalnej k ^ n_Q wynika prawdziwość twierdzenia dla liczby następnej: k + 1, czyli prawdziwa jest implikacja T=» r(ł+ l); k ^ n_v to twierdzenie jest prawdziwe dla każdej liczby naturalnej ⁿ > "o-

Dowód przeprowadzany metodą indukcji matematycznej nazywamy dowodem indukcyjnym.

Składa się on z dwóch etapów:

1* sprawdzenie prawdziwości T ( n_Q 1 2* wykazanie prawdziwości implikacji r(*) - r(*+ i> k>n_Q

Etap 1* nazywamy pierwszym krokiem indukcyjnym, a etap 2" — drugim krokiem indukcyjnym.

1.8.3. Schemat rozumowania w indukcji matematycznej

V T(n_a) A ,A [>(*) ■ ?-(* + 1)]

2*

Dowód indukcyjny:

1“ sprawdzenie T(n) dla n = n_Q (np. n₀= 1), czyli T(n₀)

2* zbudowanie implikacji: ^(ifc) ■» 7(ifc+ 1) wraz z jej dowodem:

T(k);k^ n_Q

T(k+ 1) dowód 2“: T(k) => T(k + l)

Ostateczna konkluzja na mocy zasady indukcji matematycznej (por. 1.8.2.):

1“ A 2* =» A T(n)

nelV '    '

				HCESZ WIEDZIEĆ WIĘ	CEJ?	------
1			Pochodzenie wybranych symboli matematycznych
	Wiek	Symbol	Znaczenia	Kto wprowadzi 1	Data	Uwagi
	XV	-t-	dodawanie	matematycy	koniec	w handlu w XIV w., w matematyce
		—	odejmowanie	niemieccy	XV	w druku: J. Widmann, 1486
	XVI	f.V—- j	pierwiastki	K. Rudolff	1525	używał symbolu y
				A. Girard	1629	używał symbolu "
				R. Descartes	1637	używał symbolu y , który przyjął się nu stałe dopicrol 1
						^1 w XVIII w.
		[ ]	nawias lewad ratowy	R. Bombę!li	1550
		( )	nawias okrągły	N. Thrtaglia	1556