Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Indukcja matematyczna

Ostatnio komentowane
Czy mutacje samych rybosomów 70s lub 80s mogą powodować choroby dziedziczne?
GreenPea • 2016-12-05 10:16:04
aale fajne
nwm • 2016-12-04 13:32:24
nojs
lol • 2016-12-04 11:05:26
ten nademną to pedał XD
mojstaryjestfanatykiemwedkarstwa • 2016-12-03 17:51:08
elo
lolek • 2016-12-03 10:57:03
Autor:
Drukuj
Drukuj
Rozmiar
AAA

Indukcja matematyczna

W dowodzeniu twierdzeń bardzo przydatna bywa zasada indukcji matematycznej.

Chcemy dowieść prawdziwości zdania T(n). W tym celu musimy zrobić dwa kroki:

(1) sprawdzić, że zdanie T(n) jest prawdziwe dla jakiegoś konkretnego n_{0}.

(2) pokazać, że ze zdania T(n) wynika zdanie T(n+1).

Po wykonaniu tych dwóch kroków został przeprowadzony dowód prawdziwości zdania T(n) dla wszystkich n \ge n_{0}.

 

Przykład:

Udowodnić, że suma kwadratów kolejnych n liczb nieparzystych ma postać  \frac{4n^{3}-n}{3} .

Posłużymy się zasadą indukcji matematycznej. Sprawdźmy, czy zdanie jest prawdziwe dla n = 1.

1^{2}=1.

 \frac{4 \cdot 1^{3}-1}{3} = \frac{4-1}{3} = \frac{3}{3} = 1.

Dla n = 1 twierdzenie jest prawdziwe.

Pozostaje pokazać, że z prawdziwości tego twierdzenia dla n wynika jego prawdziwość dla n+1.

Rozpiszmy to zdanie.

1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} =  \frac{4n^{3}-n}{3} - to jest nasze wyjściowe zdanie dla n. Jednocześnie jest to założenie, z którego będziemy potem korzystać.

1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} +(2(n+1)-1)^{2} =  \frac{4(n+1)^{3}-(n+1)}{3} - to jest wyjściowe twierdzenie dla n+1.

Przekształćmy prawą stronę tego drugiego zdania. Korzystać będziemy ze wzoru skróconego mnożenia (na sześcian sumy).

 \frac{4(n+1)^{3}-(n+1)}{3} =  \frac{4(n^{3}+3n^{2}+3n+1)-n-1}{3} =
\frac{4n^{3}+12n^{2}+12n+4-n-1}{3} = \frac{4n^{3}+12n^{2}+11n+3}{3}.

Teraz zajmijmy się lewą stroną.

1^{2} + 3^{2} + 5^{2} + ... + (2n-1)^{2} +(2(n+1)-1)^{2} =  
\frac{4n^{3}-n}{3} + (2n+2-1)^{2}

 - korzystając z założenia przekształciliśmy lewą stronę zdania. Teraz (korzystając ze wzoru skróconego mnożenia na kwadrat sumy) przekształcimy ją dalej.

\frac{4n^{3}-n}{3} + (2n+1)^{2} =\frac{4n^{3}-n}{3} + 4n^{2}+4n+1.

Ostatnim etapem jest doprowadzenie tej strony do postaci takiej samej jak prawa strona. W tym celu sprowadzimy wyrażenie do wspólnego mianownika.


\frac{4n^{3}-n+12n^{2}+12n+3}{3}  =
\frac{4n^{3}+12n^{2}+11n+3}{3} - lewa strona równania jest taka sama jak prawa, zatem twierdzenie jest prawdziwe.

 

Żeby lepiej zrozumieć zasadę indukcji matematycznej wygodnie jest kojarzyć ją z kostkami domina. Żeby przewrócić wszystkie kostki potrzebne są nam dwie rzeczy:

(1) przewrócenie pierwszej, oraz

(2) gwarancja, że przewrócenie danej kostki przewróci kostkę stojącą za nią. 

Polecamy również:

  • Dowód wprost

    Klasyczny dowód, zwany inaczej dowodem wprost, polega na przyjęciu założeń i takim wyciąganiu z nich wniosków, by finalnie dojść do tezy dowodzonego twierdzenia. Więcej »

  • Dowód nie wprost

    Dowód nie wprost pochodzi wprost ze starożytnej Grecji, gdzie w dyskusjach (zwłaszcza prowadzonych przez Sokratesa) był bardzo popularną metodą. Jego idea jest następująca: ... Więcej »

Komentarze (0)
5 + 1 =