[Ciągi] Indukcja matematyczna :: Kompendium / Polski Serwis Naukowy

Polecamy również:

Konfirmacja i falsyfikacja - uzasadnienie twierdzeń

[F.wielomianowa] Rozkład na czynniki, dodawanie, mnożenie, dzielenie wielomianów

Indukcja matematyczna jest sposobem dowodzenia twierdzeń, w których mowa o liczbach naturalnych. Dowód tą metodą musi przebiegać według ustalonego schematu:

Załóżmy, że dany jest ciąg twierdzeń: $\fs2 T_1 , T_2 , T_3 , \text{...} , T_n$ . Wówczas sprawdzamy prawdziwość twierdzenia dla początkowej liczby naturalnej. Kolejnym krokiem jest udowodnienie prawdziwości implikacji $T_n \Rightarrow T_{n+1}$ . Jest to drugi krok indukcyjny.

Po uzyskaniu prawdziwości obu kroków indukcyjnych stwierdzamy, że $\fs2 \bigwedge_{n \in N}$ (dla każdego/dowolnego $\fs2 n \in N$ ) twierdzenie $\fs2 T_n$ jest prawdziwe.

Przykład 1
Udowodnij, że $\fs2 \bigwedge_{n \in N} \quad 1+2+3+\text{...}+n=\frac{n(n+1)}{2}$ .

Dowód:
Pierwszy krok indukcyjny - sprawdzamy prawdziwość tweirdzenia dla początkowej liczby naturalnej, czyli 1.

$\fs2 \text{L}=1$
$\fs2 \text{P}=\frac{1(1+1)}{2}=1$
$\fs2 \text{L}=\text{P}$

Drugi krok indukcyjny - sprawdzamy prawdziwość twierdzenia dla n+1.

$\fs2 \text{L} = 1+2+3+\text{...}+n+(n+1)= \frac{n(n+1)}{2} + (n+1) =\qquad$ (podstawiamy za $\fs2 1+2+3+\text{...}+n$ wyrażenie $\fs2 \frac{n(n+1)}{2}$ ).
$\fs2 = \frac{n(n+1)}{n}+\frac{2(n+1)}{2}=\frac{(n+1)(n+2)}{2} \qquad$ (grupujemy wyrazy wyłaczajac wspólny czynnik przed nawias).

$\fs2 \text{P} = \frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}$

$\fs2 \text{L}=\text{P}$

Oba kroki indukcyjne zaszły prawidłowo, zatem twierdzenie zostało udowodnione.

Przykład 2
Udowodnij, że $\fs2 \bigwedge_{n \in N} \quad$ liczba $\fs2 n^3+2n$ jest podzielna przez 3.

Dowód:
Sprawdzamy prawdziwość twierdzenia początkowej liczby naturalnej: $\fs2 1^3 + 2 = 3$
Otrzymana liczba 3 jest podzielna przez 3.

Drugi krok indykcyjny. Spradzamy, czy jeśli twierdzenie jest prawdziwe dla n, to czy też jest prawdziwe dla następnej liczby naturalnej, czyli n+1.

$(n+1)^3 +2(n+1)=n^3+3n^2+3n+1+2n+2=\underline{n^3+2n} + 3n^2+3n+3=n^3+2n+3(n^2+n+1)$

W pierwszym kroku indukcyjnym udowodniliśmy, że liczba $\fs2 n^3+2n$ jest podzielna przez 3. Podzielelne jest także wyrażenie $\fs2 3(n^2+n+1)$ , zatem ich suma także jest podzielna przez 3.

komentuj publikację