Dowód indukcyjny

Z Wikipedii

Dowód indukcyjny to rozumowanie matematyczne korzystające z zasady indukcji matematycznej.

Zwykle dowody indukcyjne stosowane są w dziedzinach blisko związanych z teorią liczb naturalnych, nie brak jednak dowodów indukcyjnych w innych dziedzinach matematyki. Poprawne rozumowanie indukcyjne wymaga nie tylko wykonania kroku indukcyjnego (porównaj: indukcja matematyczna), ale także podania co najmniej jednego szczególnego przypadku prawdziwości twierdzenia, które się dowodzi.

[edytuj] Przykład dowodu indukcyjnego

Twierdzenie:

$\forall n\in\mathbb{N^{+}}\ 1^3+2^3+3^3+\cdots+n^3=\frac{n^2(1+n)^2}{4}$

Dowód

1.Sprawdzenie prawdziwości twierdzenia dla n=1

$1^3=\frac{1^2(1+1)^2}{4}=1$

Powyższa równość jest prawdziwa, zatem twierdzenie jest prawdziwe dla n=1

2.Założenie indukcyjne. Zakładamy, że twierdzenie jest prawdziwe dla pewnej dodatniej liczby naturalnej k.

$1^3+2^3+3^3+\cdots+k^3=\frac{k^2(1+k)^2}{4}$

$k\in\mathbb{N^{+}}$

3.Teza indukcyjna. Twierdzenie dla k+1

$1^3+2^3+3^3+\cdots+(k+1)^3=\frac{(k+1)^2(2+k)^2}{4}$

4.Krok indukcyjny. Pokażemy, że jeśli twierdzenie jest prawdziwe dla k to jest prawdziwe także dla k+1

$1^3+2^3+3^3+\cdots+(k+1)^3=1^3+2^3+3^3+\cdots+k^3+(k+1)^3$

Na mocy założenia: $1^3+2^3+3^3+\cdots+k^3=\frac{k^2(1+k)^2}{4}$ . Otrzymujemy zatem:

$1^3+2^3+3^3+\cdots+(k+1)^3=\frac{k^2(1+k)^2}{4}+(k+1)^3=\frac{k^2(1+k)^2+4(k+1)^3}{4}=$

$=\frac{(k+1)^2[k^2+4(k+1)]}{4}=\frac{(k+1)^2(k+2)^2}{4}$

Sprawdziliśmy prawdziwość twierdzenia dla n=1; następnie przy założeniu, że twierdzenie jest prawdziwe dla k, pokazaliśmy, że jest ono prawdziwe dla k+1. Stąd, na mocy zasady indukcji matematycznej, twierdzenie jest prawdziwe dla wszystkich liczb naturalnych większych lub równych 1.