"Naiwna" indukcja

Zasada indukcji matematycznej jest o prawie trzysta lat starsza niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy
Francesco Maurolico w 1575 roku. W pracy tej autor wykazał, że suma \( n \) pierwszych liczb nieparzystych równa się \( {n^2} \).

Aby zastosować zasadę indukcji matematycznej, należy wykazać dwa fakty:

  • hipoteza jest prawdziwa dla \( n=1 \),
  • jeśli hipoteza jest prawdziwa dla \( n \), to jest również prawdziwa dla \( n+1 \).

Drugi z powyższych punktów musi być prawdą dla wszystkich \( n\geq 1 \). Jeśli oba fakty są prawdą, to hipoteza jest prawdziwa dla wszystkich liczb naturalnych większych od 1. Rozumowanie, które stoi za tym wnioskiem wygląda następująco:

  1. hipoteza jest prawdziwa dla \( n=1 \) na podstawie podstawy indukcji,
  2. hipoteza jest prawdziwa dla \( n=2 \), ponieważ jest prawdziwa dla 1 i po zastosowaniu kroku     indukcyjnego również dla 2,
  3. hipoteza jest prawdziwa dla \( n=3 \); w poprzednim punkcie pokazaliśmy, że jest prawdziwa dla     2 i na podstawie kroku indukcyjnego jest również prawdziwa 3,
  4. i tak dalej.

Zasadę indukcji matematycznej można porównać do domina. Aby mieć pewność, że przewrócone zostaną wszystkie klocki wystarczy wykazać, że przewrócony zostanie pierwszy klocek i że każdy klocek pociąga za sobą następny.

Dowód indukcyjny przedstawiony przez Francesco Maurolico pokazuje, że suma pierwszych \( n \) liczb nieparzystych jest równa \( {n^2} \).

  • Jeśli \( n=1 \) to pierwsza liczba nieparzysta 1 jest równa \( 1^2 \).
  • Jeśli hipoteza jest prawdą dla \( n \), to znaczy że suma pierwszych \( n \) liczb nieparzystych równa się \( {n^2} \). Bardziej formalnie

\( 1+3+\dotsb+(2n-1) = n^2 \)
tak więc suma pierwszych \( {n+1} \) liczb nieparzystych \( 1+3+\dotsb+(2n-1)+(2(n+1)-1) \), przy użyciu założenia powyżej może być zapisana jako
\( 1+3+\dotsb+(2n-1)+(2(n+1)-1) = n^2 +(2(n+1)-1)= n^2+2n+1= {(n+1)}^2. \)
Krok indukcyjny został dowiedziony.

Ćwiczenie 2.1
Wykaż, że suma pierwszych \( \mathrm {n} \) liczb naturalnych jest równa \( \frac{1}{2}n(n+1) \).

Ćwiczenie 2.2

Wykaż, że suma kwadratów pierwszych \( \mathrm {n} \) liczb naturalnych jest równa \( \frac{1}{6}n(n+1)(2n+1) \).

Ćwiczenie 2.3

Wykaż, że dla \( n\geq 1 \) zachodzi \( 4|3^{2n-1}+1 \).

Często bardzo niepraktyczne jest używanie indukcji w jej podstawowej formie. Używa się wtedy indukcji, która w pierwszym kroku nie zaczyna się od \( n=1 \), ale \( n=0 \), \( n=2 \) lub dowolnej innej liczby naturalnej. W takim przypadku drugi krok indukcyjny nie musi działać dla wszystkich \( n \), a wystarczy, by działał dla \( n \) większych lub równych od liczby, którą wybraliśmy w pierwszym kroku. Końcowy dowód indukcyjny pokaże, że dana hipoteza nie jest prawdziwa dla wszystkich liczb naturalnych, a jedynie dla liczb większych od tej wybranej na pierwszy krok indukcyjny.

Jako przykład pokażemy, że \( n!>2^n \). Po pierwsze nierówność ta nie zachodzi dla \( 1,2,3 \), więc nie można rozpocząć kroku indukcyjnego od \( {n=1} \). Indukcja będzie wyglądać następująco:

  • Hipoteza jest prawdą dla \( n=4 \), ponieważ \( 4!=24>16=2^4 \).
  • Jeśli hipoteza jest prawdą dla \( n \) i jeśli \( n\geq 4 \) to

\( (n+1)!= n!\cdot (n+1)>2^n\cdot(n+1)>2^{n+1}, \)

gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a druga z faktu, że dowodzimy krok indukcyjny dla liczb większych niż 4.

Ćwiczenie 2.4

W tym ćwiczeniu dowodzimy wariant nierówności Bernoulliego. Dla dowolnego \( x \) takiego, że \( x> -1 \) i \( x\neq 0 \) i dla dowolnego \( n\geq 2 \) zachodzi \( {(1+x)}^n> 1+nx \).

Ćwiczenie 2.5
Liczby Fibonacciego zdefiniowane są następująco:
\( f_1=1, f_2=1 \) oraz \( f_i=f_{i-2}+f_{i-1} \) dla \( i>3. \)
Udowodnij, że dla dowolnego \( n\geq 2 \) liczby \( f_n \) i \( f_{n-1} \) są względnie pierwsze.

Kolejnym uogólnieniem zasady indukcji matematycznej jest indukcja, w której w drugim kroku indukcyjnym zakładamy, że hipoteza jest prawdą dla wszystkich liczb mniejszych niż \( n \) i dowodzimy, że jest również prawdziwa dla \( n+1 \).
Jako przykład udowodnimy, że każda liczba naturalna większa niż 2 jest produktem jednej, lub więcej liczb pierwszych.

  • Hipoteza jest prawdą dla \( n=2 \), ponieważ 2 jest liczbą pierwszą.
  • Zakładamy, że hipoteza jest prawdziwa dla liczb od 2 do \( n \). Weźmy liczbę \( n+1 \), jeśli \( n+1 \) jest liczbą pierwszą, to hipoteza jest udowodniona. Jeśli \( n+1 \) nie jest liczbą pierwszą, to \( n+1=k\cdot l \), gdzie \( 2\leq k,l\leq n \). Założenie indukcyjne gwarantuje, że

\( k=p_1\cdot p_2\cdot\dotsb\cdot p_i \) i \( l=q_1\cdot q_2\cdot\dotsb\cdot q_j, \)

gdzie \( p_1,\dotsc,p_i,q_1,\dotsc,q_j \) są liczbami pierwszymi. W związku z tym

\( n+1=p_1\cdot p_2\cdot\dotsb\cdot p_i\cdot q_1\cdot q_2\cdot\dotsb\cdot q_j \)

i krok indukcyjny jest udowodniony.

Ćwiczenie 2.6

Udowodnij, że każda liczba naturalna większa niż 1 może być przedstawiona jako suma liczb Fibonacciego tak, że żadna liczba nie występuje w tej sumie więcej niż raz.

Ćwiczenie 2.7

Znajdź błąd w poniższym dowodzie indukcyjnym. Dowodzimy indukcyjnie twierdzenia, że wszystkie liczby są parzyste.

  • Twierdzenie jest prawdą dla \( n=0 \) ponieważ 0 jest liczbą parzystą.
  • Zakładamy, że twierdzenie jest prawdą dla wszystkich liczb mniejszych lub równych \( n \). Liczba \( n+1 \) jest niewątpliwie sumą dwóch liczb silnie mniejszych od siebie \( n+1=k+l \). Liczby \( k \) i \( l \), na podstawie założenia indukcyjnego, są parzyste, zatem ich suma równa \( n+1 \) jest parzysta. Krok indukcyjny został dowiedziony.

Na zasadzie indukcji matematycznej wszystkie liczby są parzyste.

Ćwiczenie 2.8

W trójwymiarowej przestrzeni znajduje się \( n \) punktów. Ilość punktów w rzutowaniu na płaszczyznę \( O_x, O_y \) oznaczamy przez \( n_{xy} \). Podobnie ilość punktów w rzutowaniu na \( O_x, O_z \) przez \( n_{xz} \) i ilość punktów w rzutowaniu na \( O_y, O_z \) przez \( n_{yz} \). Wykaż, że dla dowolnego rozkładu punktów w przestrzeni zachodzi nierówność

\( n^2\leq n_{xy}n_{xz}n_{yz}. \)



Zasada indukcji matematycznej jest bardzo potężnym narzędziem. Intuicyjnie wydaje się jasne, że dowody przeprowadzone przy jej pomocy są poprawne. Niemniej jednak, żeby uzasadnić poprawność samej zasady, należy sięgnąć do teorii mnogości i definicji zbioru liczb naturalnych. Wiemy już, że "naiwna teoria mnogości" nie daje nam poprawnych zbiorów, na których można oprzeć ścisłe rozumowanie. W dalszej części wykładu wyprowadzimy zasadę indukcji matematycznej w oparciu o aksjomaty i aksjomatycznie zdefiniowany zbiór liczb naturalnych. Takie podejście gwarantuje nam poprawność rozumowania -- podejście naiwne zapewnia intuicje niezbędne do budowania poprawnych teorii.