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)
Wynik działania 1 + 2 =
Ostatnio komentowane
Bardzo przydatne informacje. Przeczytałam z zainteresowaniem.
• 2022-08-13 18:28:30
Ola jest fajną dziewczyną i lubi się bawić z dziećmi i jest w ogóle fajną kobietą....
• 2022-08-09 19:00:20
Rosja nadal jest państwem totalitarnym, a Polska sie nim staje.
• 2022-08-02 19:37:03
Ef. 6:12 [ 11 - 20]. 1Tes.2:13 ; 4: 8..... w tedy i dziś. Łuk.10: 16 .....
• 2022-08-01 16:36:20
To bardzo ciekawa historia godna uwagi każdego.
• 2022-07-12 15:12:25