Test GR2

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f(0)=1$ $f(1)=3$ $f(n)=n+3;n\ge 2$	$f(0)=2$ $f(1)=3$ $f(n)=n+1;n\ge 2$
Maszyna rozpoznająca $w{w}^{\leftarrow }$	$f(n)=6+8+\dots +(n+3)+2;n=2k+1$ $f(n)=5+7+\dots +(n+3)+1;n=2k$	$f(n)=n+1$

$\Rightarrow$	0	1	...	...
Cell1	Cell2

$\Rightarrow$	0	1
0	1	1
1	0	1

$p$	$\mathrm{\neg }p$
0	1
1	0

$\wedge$	0	1
0	0	o
1	0	1

$\vee$	0	1
0	0	1
1	1	1

"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\ge 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.

Obrazek 2.1 nieskończone domino ponumerowanych liczbami naturalnymi klocków w trakcie przewracania

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+\cdots +(2n-1)=n^2.$

tak więc suma pierwszych $n+1$ liczb nieparzystych $1+3+\cdots +(2n-1)+(2(n+1)-1)$, przy użyciu założenia powyżej może być zapisana jako

$1+3+\cdots +(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 $n$ liczb naturalnych jest równa $\frac{1}{2}n(n+1)$.

Solution. Aby udowodnić wzór na sumę $n$ pierwszych liczb naturalnych posłużymy się indukcją.

• Dla $n=1$ mamy $\frac{1}{2}\cdot 1\cdot 2=1$.

• Zakładamy, że wzór jest prawdziwy dla $n$. W związku z tym do sumy

$1+2+\cdots +n+(n+1)=$

stosujemy założenie indukcyjne

$(1+2+\cdots +n)+(n+1)=\frac{1}{2}n(n+1)+(n+1)=$

i po paru prostych przekształceniach otrzymujemy

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

co dowodzi kroku indukcyjnego.

Na zasadzie indukcji matematycznej dowiedliśmy wzór na sumę $n$ pierwszych liczb naturalnych.

Koniec ćwiczenia 2.1

Ćwiczenie 2.2

Wykaż, że suma kwadratów pierwszych $n$ liczb naturalnych jest równa $\frac{1}{6}n(n+1)(2n+1)$. Solution. Aby wykazać prawdziwość wzoru powyżej postępujemy jak w poprzednim zadaniu.

• Dla $n=1$ mamy $\frac{1}{6}\cdot 1\cdot 2\cdot 3=1$ co dowodzi podstawy indukcji.

• Zakładamy że wzór jest prawdziwy dla $n$ to jest, że

$1^2+2^2+\cdots +n^2=\frac{1}{6}n(n+1)(2n+1).$

Korzystając z tego faktu przekształcamy

$1^2+2^2+\cdots +n^2+{(n+1)}^2=\frac{1}{6}n(n+1)(2n+1)+{(n+1)}^2=$

i dalej do

$\frac{1}{6}(n+1)(n(2n+1)+6(n+1))=\frac{1}{6}(n+1)(2n^2+7n+6)=\frac{1}{6}(n+1)(n+2)(2(n+1)+1)$

co dowodzi kroku indukcyjnego.

Podobnie jak w poprzednim przykładzie zasada indukcji matematycznej gwarantuje, że wzór jest prawdziwy dla wszystkich liczb naturalnych.

Koniec ćwiczenia 2.2

Ćwiczenie 2.3

Wykaż, że dla $n\ge 1$ zachodzi $4|3^{2n-1}+1$.

Solution. Jak poprzednio stosujemy zasadę indukcji matematycznej.

• Dla $n=1$ mamy $3^{2n-1}+1=3^1+1=4$ jest podzielne przez 4.

• Zakładamy że podzielność zachodzi dla $n$. Pokażemy że $3^{2(n+1)-1}+1$ jest podzielne przez 4. Przekształcamy

$3^{2(n+1)-1}+1=3^{2n-1+2}+1=9\cdot 3^{2n-1}+1=$

wprowadzamy sztuczny czynnik

$=9\cdot (3^{2n-1}+1-1)+1=9\cdot (3^{2n-1}+1-1)+1=9\cdot (3^{2n-1}+1)-9+1=9\cdot (3^{2n-1}+1)-8.$

Zarówno $(3^{2n+1}+1)$ (na mocy założenia indukcyjnego) jak i 8 są podzielne przez 4, a wiec ich różnica również. W ten sposób udowodniliśmy krok indukcyjny.

Koniec ćwiczenia 2.3

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\ge 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\ne 0$ i dla dowolnego $n\ge 2$ zachodzi ${(1+x)}^n>1+nx$.

Solution. Rozwiązanie:

• Nierówność ostra nie jest prawdą dla $n=0$, ani dla $n=1$. Krok indukcyjny zaczniemy od 2. Wtedy

${(1+x)}^2=1+2x+x^2>1+2x$, gdzie ostatnia nierówność bierze się z faktu, że $x\ne 0$.

• Zakładamy teraz, że nierówność jest prawdziwa dla $n$, czyli, że dla dowolnego $x$ takiego, że $0\ne x>-1$ mamy

${(1+x)}^n>1+nx.$

Przekształcając nierówność dla $n+1$ otrzymujemy

${(1+x)}^{(n+1)}={(1+x)}^n(1+x)>(1+nx)(1+x)=1+(n+1)x+x^2\ge 1+(n+1)x,$

gdzie otrzymujemy ostrą nierówność dzięki założeniu indukcyjnemu i faktowi, że $x\ne -1$. W ten sposób krok indukcyjny został udowodniony.

Koniec ćwiczenia 2.4

Ć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\ge 2$ liczby $f_n$ i $f_{n-1}$ są względnie pierwsze.

Solution. Dowód przez indukcję matematyczną

• Twierdzenie jest prawdą dla $n=2$ ponieważ $f_2$ i $f_1$ są względnie pierwsze.

• Zakładamy że twierdzenie jest prawdą dla $n$. Rozpatrzmy wspólny dzielnik liczb $f_{n+1}$ i $f_n$ i oznaczmy go przez $k$. Jeśli $k$ dzieli $f_{n+1}$ i równocześnie $f_n$ to $k|f_{n+1}-f_n$. Korzystając z definicji liczb Fibbonaciego otrzymujemy $f_{n+1}-f_n=f_n+f_{n-1}-f_n=f_{n-1}$. W związku z czym $k$ jest wspólnym dzielnikiem liczb $f_n$ i $f_{n-1}$, więc na mocy założenia indukcyjnego mówiącego, że liczby te są względnie pierwsze, jest równy 1. Pokazaliśmy, że każdy wspólny dzielnik $f_{n+1}$ i $f_n$ jest równy 1, a więc liczby te są względnie pierwsze. Krok indukcyjny został pokazany.

Koniec ćwiczenia 2.5

Kolejnym uogólnieniem zasady indukcji matematycznej jest indukcja, w której w drugi 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\le k,l\le n$. Założenie indukcyjne gwarantuje, że

$k=p_1\cdot p_2\cdot \cdots \cdot p_i$ i $l=q_1\cdot q_2\cdot \cdots \cdot q_j$

gdzie $p_1,\dots ,p_i,q_1,\dots ,q_j$ są liczbami pierwszymi. W związku z tym

$n+1=p_1\cdot p_2\cdot \cdots \cdot p_i\cdot q_1\cdot q_2\cdot \cdots \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.

Solution. Przedstawimy dowód przez indukcję.

• Dla $n=1$ mamy $f_2=1$.

• Zakładamy że każda liczba mniejsza lub równa $n$ może być przedstawiona w sposób opisany powyżej. Jeśli liczba $n+1$ jest liczbą Fibonacciego to krok indukcyjny jest już dowiedziony, jeśli nie to znajdujemy największą liczbę Fibonacciego mniejszą od $n+1$ - oznaczmy tą liczbę $f_k$. Liczba $n+1-f_k$ jest mniejsza niż $n$ więc, na mocy założenia indukcyjnego, posiada reprezentację jako suma liczb Fibonacciego

$n+1-f_k=f_{l_0}+\cdots +f_{l_i}$

tak, że każda z liczb w tej reprezentacji występuje co najwyżej raz. Oczywiście

$n+1=f_k+f_{l_0}+\cdots +f_{l_i}$

i pozostaje wykazać, że $f_k$ nie występuje pośród liczb $f_{l_0},\dots ,f_{l_i}$. Skoro $f_k$ było największą liczbą Fibonacciego mniejszą niż $n+1$ to $f_{k+1}>n+1$ a więc $f_{k-1}=f_{k+1}-f_k>n+1-f_k$. W związku z tym liczby $f_{l_0},\dots ,f_{l_i}$ są silnie mniejsze niż $f_{k-1}$ i żadna z nich nie może być równa $f_k$. W ten sposób krok indukcyjny został dowiedziony.

Koniec ćwiczenia 2.6

Ć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.

Solution. Dowód indukcyjny jest niepoprawny. Krok indukcyjny nie działa dla wszystkich $n$ większych lub równych od 0 - które jest podstawą indukcji. Jeśli $n=0$, to $n+1=1$ i nie jesteśmy w stanie rozbić liczby 1 na sumę dwóch liczb istotnie mniejszych od niej samej.

Koniec ćwiczenia 2.7

Ć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\le n_{xy}{n}_{xz}{n}_{yz}.$

Hint 1. Użyj nierówności pomiędzy średnią geometryczną, a średnią arytmetyczną

$\frac{1}{2}(a+b)\ge \sqrt{ab}.$

Hint 2. Podziel punkty na dwie grupy płaszczyzną równoległą do którejś z płaszczyzn
    $O_x,O_y$, $O_x,O_z$ lub $O_y,O_z$.

Solution. Dowiedziemy nierówność przy użyciu indukcji.

• Jeśli $n=1$ to $n_{xy}=n_{xz}=n_{yz}=1$ i nierówność jest prawdziwa.

• Zakładamy, że nierówność jest prawdziwa dla wszystkich liczb naturalnych (dla dowolnego układu punktów) mniejszych niż $n+1$. Rozpoczynamy z dowolnym układem $n+1$ punktów w przestrzeni. Ponieważ $n+1>1$ wiemy, że istnieje płaszczyzna równoległa do którejś z płaszczyzn $O_x,O_y$, $O_x,O_z$ lub $O_y,O_z$ i dzieląca $n+1$ punktów na dwie niepuste części posiadające odpowiednio $n^{\prime }$ i $n^{″}$ punktów. Ponieważ nasz układ jest bardzo symetryczny możemy założyć że nasza płaszczyzna jest równoległa do płaszczyzny $O_x,O_y$. Stosując założenie indukcyjne do każdej z części otrzymujemy

${n^{\prime }}^2\le n{\text{'}}_{xy}n{\text{'}}_{xz}n{\text{'}}_{yz}$

oraz

${n^{″}}^2\le n^{\prime }{\text{'}}_{xy}{n}^{\prime }{\text{'}}_{xz}{n}^{\prime }{\text{'}}_{yz}.$

Co więcej, pomiędzy projekcjami zachodzą następujące zależności

$n{\text{'}}_{xz}+n^{\prime }{\text{'}}_{xz}=n_{xz}$ oraz $n{\text{'}}_{yz}+n^{\prime }{\text{'}}_{yz}=n_{yz}.$

Dla płaszczyzny $O_x,O_y$ nie posiadamy podziału na część punktów należących do $n^{\prime }$ i $n^{″}$ i możemy jedynie wnioskować, że

$n{\text{'}}_{xy}\le n_{xy}$ oraz $n^{\prime }{\text{'}}_{xy}\le n_{xy}.$

Zaczynamy przekształcenia mające udowodnić pożądaną nierówność

Parser nie mógł rozpoznać (nieznana funkcja „\beginsplit”): {\displaystyle \beginsplit n^2& ={(n'+n'')}^2={(n')}^2+2n'n'' + {(n'')}^2\leq {(n')}^2+2\sqrt{{(n')}^2}\sqrt{{(n'')}^2} + {(n'')}^2\leq \\ & \leq n'_{xy}n'_{xz}n'_{yz} +2\sqrt{n'_{xy}n'_{xz}n'_{yz}}\sqrt{n''_{xy}n''_{xz}n''_{yz}}+n''_{xy}n''_{xz}n''_{yz} \leq\\ & \leq n_{xy}n'_{xz}n'_{yz} +2\sqrt{n_{xy}n'_{xz}n'_{yz}n_{xy}n''_{xz}n''_{yz}}+n_{xy}n''_{xz}n''_{yz} \leq \\ & \leq n_{xy}\left(n'_{xz}n'_{yz} +2\sqrt{n'_{xz}n'_{yz}n''_{xz}n''_{yz}}+n''_{xz}n''_{yz} \right)\endsplit }

używając założenia indukcyjnego i nierówności pomiędzy projekcjami na płaszczyznę $O_x,O_y$. Kontynuujemy używając nierówności pomiędzy średnią algebraiczną i geometryczną

Parser nie mógł rozpoznać (nieznana funkcja „\beginsplit”): {\displaystyle \beginsplit n^2 & \leq n_{xy}\left(n'_{xz}n'_{yz} +2\sqrt{n'_{xz}n''_{xz}n'_{yz}n''_{yz}}+n''_{xz}n''_{yz}\right) \leq \\ & \leq n_{xy}\left(n'_{xz}n'_{yz} +2\frac{1}{2}(n'_{xz}n''_{xz} +n'_{yz}n''_{yz})+n''_{xz}n''_{yz}\right) = \\ & = n_{xy}\left(n'_{xz}n'_{yz} +n'_{xz}n''_{xz} +n'_{yz}n''_{yz}+n''_{xz}n''_{yz}\right) = n_{xy}(n'_{xz} + n''_{xz})(n'_{yz}+n''_{yz}) \endsplit }

W ostatnim kroku wystarczy wykorzystać zależności pomiędzy projekcjami na pozostałe dwie współrzędne i

$n^2\le n_{xy}(n{\text{'}}_{xz}+n^{\prime }{\text{'}}_{xz})(n{\text{'}}_{yz}+n^{\prime }{\text{'}}_{yz})=n_{xy}{n}_{xz}{n}_{yz}.$

Krok indukcyjny został dowiedziony.

Na podstawie zasady indukcji matematycznej twierdzenie jest prawdziwe.

Koniec ćwiczenia 2.8

Obrazek 2.2 Obrazek do powyższego ćwiczenia według załączonego skanu

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.

"Naiwne" dowody niewprost

Częstą metodą dowodzenia twierdzeń matematycznych jest dowodzenie niewprost. Dowód niewprost polega na założeniu zaprzeczenia twierdzenia, które chcemy udowodnić i doprowadzeniu do sprzeczności. Wykazujemy, że jeśli twierdzenie nasze jest nieprawdziwe, jesteśmy w stanie udowodnić jakąś tezę, która jest w sposób oczywisty fałszywa.

Jednym z najbardziej znanych dowodów niewprost jest dowód istnienia nieskończenie wielu liczb pierwszych. Dowód ten został zaproponowany przez Euclid of Alexandria a my prezentujemy go w wersji podanej przez Ernst'a Kummera.

Twierdzenie [Istnieje nieskończenie wiele liczb pierwszych]

Dowód

Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych $p_0,\dots ,p_n$. Zdefiniujmy liczbę

$k=p_0\cdot p_1\cdot \cdots \cdot p_n$

i rozważmy $k+1$. Liczba $k+1$ posiada dzielnik pierwszy, a ponieważ jedynymi pierwszymi liczbami są liczby $p_0,\dots ,p_n$ wnioskujemy, że $p_i$ dzieli $k+1$ dla pewnego $i$. Liczba $p_i$ dzieli również $k$, a więc $p_i$ dzieli $(k+1)-k=1$ co jest sprzecznością.

Ćwiczenie 3.1

Wykaż, że nie istnieje największa liczba naturalna.

Solution. Załóżmy, niewprost, że istnieje największa liczba naturalna i oznaczmy ją przez $n$. Niewątpliwie $n+1$ jest liczbą naturalną większą od $n$, co jest sprzecznością z naszym założeniem.

Koniec ćwiczenia 3.1

Ćwiczenie 3.2

Wykaż, że $\sqrt{2}$ jest liczbą niewymierną.

Solution. Załóżmy, niewprost, że $\sqrt{2}$ jest liczbą wymierną, czyli, że istnieją dwie naturalne, względnie pierwsze liczby $k$ i $l$ takie, że $\sqrt{2}=k/l$. Przekształcając ostatnie wyrażenie otrzymujemy $k^2=2l^2$. Skoro $2$ dzieli lewą stronę równości dzieli też i prawą, a ponieważ dwa jest liczbą pierwszą wnioskujemy, że $2$ dzieli $k$. Jeśli $2$ dzieli $k$ to $4$ dzieli $k^2$ i na podstawie równości $4$ dzieli $2l^2$. Wnioskujemy stąd, że $2$ dzieli $l^2$ i, na podstawie pierwszości liczby $2$, że $2$ dzieli $l$. Udowodniliśmy, że $2$ dzieli zarówno $k$ jak i $l$, co jest sprzecznością z założeniem, że liczby te są względnie pierwsze.

Koniec ćwiczenia 3.1

Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie logiki, której poświęcony jest następny wykład.