|
|
| Linia 36: |
Linia 36: |
| ! <math>\wedge</math>!! 0!! 1!! | | ! <math>\wedge</math>!! 0!! 1!! |
| |- | | |- |
| | 0 || 0 || o | | | 0 || 0 || 0 |
| |- | | |- |
| | 1 || 0 || 1 | | | 1 || 0 || 1 |
| Linia 49: |
Linia 49: |
| |} | | |} |
|
| |
|
| =="Naiwna" indukcja==
| | {| border="1" |
| | | ! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{p} \wedge \textnormal{q}</math>!! <math>\neg( p \wedge q)</math>!! <math>\neg p</math>!! <math>\neg q</math>!! <math>\neg p \vee \neg q</math> |
| Zasada indukcji matematycznej jest o prawie trzysta lat starsza
| | |- |
| niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy
| | | 0|| 0|| 0|| 1|| 1|| 1|| 1 |
| <u>'''Francesco Maurolico'''</u> w 1575 roku. W pracy tej autor wykazał, że suma <math>n</math>
| | |- |
| pierwszych liczb nieparzystych równa się <math>n^2</math>.
| | | 0|| 1|| 0|| 1|| 1|| 0|| 1 |
| | | |- |
| Aby zastosować zasadę indukcji matematycznej należy wykazać dwa
| | | 1|| 0|| 0|| 1|| 0|| 1|| 1 |
| fakty:
| | |- |
| | | | 1|| 1|| 1|| 0|| 0|| 0|| 0 |
| * hipoteza jest prawdziwa dla <math>n=1</math>;
| | |} |
| | |
| * jeśli hipoteza jest prawdziwa dla <math>n</math> to jest również prawdziwa dla <math>n+1</math>.
| |
| | |
| Drugi z powyższych punktów musi być prawdą dla wszystkich <math>n\geq
| |
| 1</math>. Jeśli oba fakty są prawdą to hipoteza jest prawdziwa dla
| |
| wszystkich liczb naturalnych większych od <math>1</math>. Rozumowanie które stoi za tym wnioskiem wygląda następująco:
| |
| | |
| :1. hipoteza jest prawdziwa dla <math>n=1</math> na podstawie podstawy indukcji,
| |
| | |
| :2. hipoteza jest prawdziwa dla <math>n=2</math>, ponieważ jest prawdziwa dla '''1''' i po zastosowaniu kroku indukcyjnego również dla '''2''',
| |
| | |
| :3. hipoteza jest prawdziwa dla <math>n=3</math>; 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 <u>'''Francesco Maurolico'''</u> pokazuje, że suma pierwszych <math>n</math> liczb nieparzystych jest równa <math>n^2</math>.
| |
| | |
| | |
| * Jeśli <math>n=1</math> to pierwsza liczba nieparzysta <math>1</math> jest równa <math>1^2</math>.
| |
| | |
| * Jeśli hipoteza jest prawdą dla <math>n</math>, to znaczy że suma pierwszych <math>n</math> liczb nieparzystych równa się <math>n^2</math>. Bardziej formalnie
| |
| | |
| | |
| <center><math>
| |
| 1+3+\dotsb+(2n-1) = n^2.
| |
| </math></center>
| |
| | |
| | |
| tak więc suma pierwszych <math>n+1</math> liczb nieparzystych
| |
| <math>1+3+\dotsb+(2n-1)+(2(n+1)-1)</math>, przy użyciu założenia powyżej może być zapisana jako
| |
| | |
| | |
| <center><math>
| |
| 1+3+\dotsb+(2n-1)+(2(n+1)-1) = n^2 +(2(n+1)-1)= n^2+2n+1=
| |
| {(n+1)}^2.
| |
| </math></center>
| |
| | |
| | |
| Krok indukcyjny został dowiedziony.
| |
| | |
| {{cwiczenie|2.1|| | |
| Wykaż, że suma pierwszych <math>n</math> liczb naturalnych jest równa
| |
| <math>\frac{1}{2}n(n+1)</math>.
| |
|
| |
| '''Solution.''' Aby udowodnić wzór na sumę <math>n</math> pierwszych liczb naturalnych posłużymy się indukcją.
| |
| | |
| :* Dla <math>n=1</math> mamy <math>\frac{1}{2}\cdot 1\cdot 2 = 1</math>.
| |
| | |
| :* Zakładamy, że wzór jest prawdziwy dla <math>n</math>. W związku z tym do sumy
| |
| | |
| <center><math>
| |
| 1+2+\dotsb+n+(n+1) =
| |
| </math></center>
| |
| | |
| :stosujemy założenie indukcyjne
| |
| | |
| <center><math>
| |
| (1+2+\dotsb+n ) +(n+1) = \frac{1}{2}n(n+1) + (n+1) =
| |
| </math></center> | |
| | |
| :i po paru prostych przekształceniach otrzymujemy
| |
| | |
| <center><math>
| |
| = \frac{1}{2}n(n+1) +\frac{1}{2}2(n+1) = \frac{1}{2}(n+1)(n+2)
| |
| </math></center> | |
| | |
| :co dowodzi kroku indukcyjnego.
| |
| | |
| Na zasadzie indukcji matematycznej dowiedliśmy wzór na sumę <math>n</math>
| |
| pierwszych liczb naturalnych.
| |
| | |
| Koniec ćwiczenia 2.1
| |
| }}
| |
| | |
| {{cwiczenie|2.2||
| |
| Wykaż, że suma kwadratów pierwszych <math>n</math> liczb
| |
| naturalnych jest równa <math>\frac{1}{6}n(n+1)(2n+1)</math>.
| |
| '''Solution.''' Aby wykazać prawdziwość wzoru powyżej postępujemy jak
| |
| w poprzednim zadaniu.
| |
| | |
| :* Dla <math>n=1</math> mamy <math>\frac{1}{6}\cdot 1\cdot 2\cdot 3 = 1</math> co dowodzi podstawy indukcji.
| |
| | |
| :* Zakładamy że wzór jest prawdziwy dla <math>n</math> to jest, że
| |
| | |
| | |
| <center><math>
| |
| 1^2+2^2+\dotsb+n^2 = \frac{1}{6}n(n+1)(2n+1).
| |
| </math></center> | |
| | |
| | |
| :Korzystając z tego faktu przekształcamy
| |
| | |
| | |
| <center><math>
| |
| 1^2+2^2+\dotsb+n^2 + {(n+1)}^2= \frac{1}{6}n(n+1)(2n+1) + {(n+1)}^2 =
| |
| </math></center> | |
| | |
| | |
| :i dalej do
| |
| | |
| | |
| <center><math>
| |
| \frac{1}{6}(n+1)\left(n(2n+1)+6(n+1)\right)=\frac{1}{6}(n+1)(2n^2+7n+6)= \frac{1}{6}(n+1)(n+2)(2(n+1)+1) | |
| </math></center> | |
| | |
| | |
| :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
| |
| }}
| |
| {{cwiczenie|2.3||
| |
| | |
| Wykaż, że dla <math>n\geq 1</math> zachodzi <math>4|3^{2n-1}+1</math>.
| |
|
| |
| '''Solution.''' Jak poprzednio stosujemy zasadę indukcji matematycznej.
| |
| | |
| :* Dla <math>n=1</math> mamy <math>3^{2n-1} + 1 = 3^1 +1 = 4</math> jest podzielne przez '''4'''.
| |
| | |
| :* Zakładamy że podzielność zachodzi dla <math>n</math>. Pokażemy że <math>3^{2(n+1)-1}+1</math> jest podzielne przez '''4'''. Przekształcamy
| |
| | |
| <center><math>
| |
| 3^{2(n+1)-1}+1 = 3^{2n-1+2} + 1 = 9\cdot 3^{2n-1} + 1=
| |
| </math></center>
| |
| | |
| | |
| :wprowadzamy sztuczny czynnik
| |
| | |
| | |
| <center><math>
| |
| =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.
| |
| </math></center>
| |
| | |
| :Zarówno <math>(3^{2n+1} +1)</math> (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 <math>n=1</math>, ale <math>n=0</math>, <math>n=2</math> lub dowolnej
| |
| innej liczby naturalnej. W takim przypadku drugi krok indukcyjny
| |
| nie musi działać dla wszystkich <math>n</math> a wystarczy by działał dla <math>n</math>
| |
| 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 <math>n!>2^n</math>. Po pierwsze nierówność ta nie
| |
| zachodzi dla <math>1,2,3</math>, więc nie można rozpocząć kroku indukcyjnego
| |
| od <math>n=1</math>. Indukcja będzie wyglądać następująco.
| |
| | |
| * Hipoteza jest prawdą dla <math>n=4</math>, ponieważ <math>4!=24>16=2^4</math>.
| |
| | |
| * Jeśli hipoteza jest prawdą dla <math>n</math> i jeśli <math>n\geq 4</math> to
| |
| | |
| <center><math>
| |
| (n+1)!= n!\cdot (n+1)>2^n\cdot(n+1)>2^{n+1}
| |
| </math></center> | |
| | |
| :gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a
| |
| druga z faktu, że dowodzimy krok indukcyjny dla liczb większych
| |
| niż '''4'''.
| |
| }}
| |
| | |
| {{cwiczenie|2.4||
| |
| | |
| W tym ćwiczeniu dowodzimy wariant nierówności Bernoulliego. Dla dowolnego <math>x</math> takiego, że <math>x> -1</math> i <math>x\neq 0</math> i dla dowolnego <math>n\geq 2</math> zachodzi <math>{(1+x)}^n> 1+nx</math>.
| |
| | |
| '''Solution.''' Rozwiązanie:
| |
| | |
| :* Nierówność ostra nie jest prawdą dla <math>n=0</math>, ani dla <math>n=1</math>. Krok indukcyjny zaczniemy od '''2'''. Wtedy
| |
| <math>{(1+x)}^2=1+2x+x^2>1+2x</math>, gdzie ostatnia nierówność bierze się z faktu, że <math>x\neq 0</math>.
| |
| | |
| :* Zakładamy teraz, że nierówność jest prawdziwa dla <math>n</math>, czyli, że dla dowolnego <math>x</math> takiego, że <math>0\neq x> -1</math> mamy
| |
| | |
| | |
| <center><math>
| |
| {(1+x)}^n> 1+nx.
| |
| </math></center>
| |
| | |
| | |
| :Przekształcając nierówność dla <math>n+1</math> otrzymujemy
| |
| | |
| | |
| <center><math>
| |
| {(1+x)}^{(n+1)}={(1+x)}^n(1+x)>(1+nx)(1+x)=1+(n+1)x +x^2\geq
| |
| 1+(n+1)x,
| |
| </math></center>
| |
| | |
| | |
| :gdzie otrzymujemy ostrą nierówność dzięki założeniu indukcyjnemu i faktowi, że <math>x\neq -1</math>. W ten sposób krok indukcyjny został udowodniony.
| |
| | |
| Koniec ćwiczenia 2.4
| |
| }}
| |
| | |
| {{cwiczenie|2.5||
| |
| | |
| Liczby Fibonacciego zdefiniowane są następująco
| |
| | |
| | |
| <center><math>
| |
| f_1=1, f_2=1 </math> oraz <math> f_i=f_{i-2}+f_{i-1} </math> dla <math> i>3.</math></center>
| |
| | |
| | |
| Udowodnij, że dla dowolnego <math>n\geq 2</math> liczby <math>f_n</math> i <math>f_{n-1}</math> są względnie pierwsze.
| |
| | |
|
| |
| '''Solution.''' Dowód przez indukcję matematyczną
| |
| | |
| :* Twierdzenie jest prawdą dla <math>n=2</math> ponieważ <math>f_2</math> i <math>f_1</math> są względnie pierwsze.
| |
| | |
| :* Zakładamy że twierdzenie jest prawdą dla <math>n</math>. Rozpatrzmy wspólny dzielnik liczb <math>f_{n+1}</math> i <math>f_n</math> i oznaczmy go przez <math>k</math>. Jeśli <math>k</math> dzieli <math>f_{n+1}</math> i równocześnie <math>f_n</math> to <math>k | f_{n+1}-f_n</math>. Korzystając z definicji liczb Fibbonaciego otrzymujemy <math>f_{n+1}-f_n=f_n+f_{n-1}-f_n=f_{n-1}</math>. W związku z czym <math>k</math> jest wspólnym dzielnikiem liczb <math>f_n</math> i <math>f_{n-1}</math>, 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 <math>f_{n+1}</math> i <math>f_n</math> 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ż <math>n</math> i dowodzimy, że jest również prawdziwa dla <math>n+1</math>.
| |
| | |
| Jako przykład udowodnimy, że każda liczba naturalna większa niż
| |
| <math>2</math> jest produktem jednej, lub więcej liczb pierwszych.
| |
| | |
| * Hipoteza jest prawdą dla <math>n=2</math> ponieważ '''2''' jest liczbą pierwszą.
| |
| | |
| * Zakładamy że hipoteza jest prawdziwa dla liczb od '''2''' do <math>n</math>. Weźmy liczbę <math>n+1</math>, jeśli <math>n+1</math> jest liczbą pierwszą, to hipoteza jest udowodniona. Jeśli <math>n+1</math> nie jest liczbą pierwszą, to <math>n+1=k\cdot l</math> gdzie <math>2\leq k,l\leq n</math>. Założenie indukcyjne gwarantuje, że
| |
| | |
| | |
| <center><math>
| |
| k=p_1\cdot p_2\cdot\dotsb\cdot p_i </math> i <math> l=q_1\cdot
| |
| q_2\cdot\dotsb\cdot q_j
| |
| </math></center>
| |
| | |
| | |
| :gdzie <math>p_1,\dotsc,p_i,q_1,\dotsc,q_j</math> są liczbami pierwszymi. W związku z tym
| |
| | |
| | |
| <center><math>
| |
| n+1=p_1\cdot p_2\cdot\dotsb\cdot p_i\cdot q_1\cdot
| |
| q_2\cdot\dotsb\cdot q_j
| |
| </math></center>
| |
| | |
| | |
| :i krok indukcyjny jest udowodniony.
| |
| | |
| {{cwiczenie|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 <math>n=1</math> mamy <math>f_2=1</math>.
| |
| | |
| :* Zakładamy że każda liczba mniejsza lub równa <math>n</math> może być przedstawiona w sposób opisany powyżej. Jeśli liczba <math>n+1</math> jest liczbą Fibonacciego to krok indukcyjny jest już dowiedziony, jeśli nie to znajdujemy największą liczbę Fibonacciego mniejszą od <math>n+1</math> - oznaczmy tą liczbę <math>f_k</math>. Liczba <math>n+1-f_k</math> jest mniejsza niż <math>n</math> więc, na mocy założenia indukcyjnego, posiada reprezentację jako suma liczb Fibonacciego
| |
| | |
| | |
| <center><math>
| |
| n+1-f_k=f_{l_0}+\dotsb+f_{l_i}
| |
| </math></center>
| |
| | |
| | |
| :tak, że każda z liczb w tej reprezentacji występuje co najwyżej raz. Oczywiście
| |
| | |
| | |
| <center><math>
| |
| n+1 = f_k+f_{l_0}+\dotsb+f_{l_i}
| |
| </math></center>
| |
| | |
| | |
| :i pozostaje wykazać, że <math>f_k</math> nie występuje pośród liczb <math>f_{l_0},\dotsc,f_{l_i}</math>. Skoro <math>f_k</math> było największą liczbą Fibonacciego mniejszą niż <math>n+1</math> to <math>f_{k+1}>n+1</math> a więc <math>f_{k-1}=f_{k+1}-f_k>n+1-f_k</math>. W związku z tym liczby <math>f_{l_0},\dotsc,f_{l_i}</math> są silnie mniejsze niż <math>f_{k-1}</math> i żadna z nich nie może być równa <math>f_k</math>. W ten sposób krok indukcyjny został dowiedziony.
| |
| | |
| Koniec ćwiczenia 2.6
| |
| }}
| |
| {{cwiczenie|2.7||
| |
| Znajdź błąd w poniższym dowodzie indukcyjnym. Dowodzimy
| |
| indukcyjnie twierdzenia, że wszystkie liczby są parzyste.
| |
| | |
| * Twierdzenie jest prawdą dla <math>n=0</math> ponieważ <math>0</math> jest liczbą parzystą.
| |
| | |
| * Zakładamy, że twierdzenie jest prawdą dla wszystkich liczb mniejszych lub równych <math>n</math>. Liczba <math>n+1</math> jest niewątpliwie sumą dwóch liczb silnie mniejszych od siebie <math>n+1=k+l</math>. Liczby <math>k</math> i <math>l</math>, na podstawie założenia indukcyjnego, są parzyste, zatem ich suma równa <math>n+1</math> 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 <math>n</math> większych lub równych od '''0''' - które jest podstawą indukcji. Jeśli <math>n=0</math>, to <math>n+1=1</math> i nie jesteśmy w stanie rozbić liczby '''1''' na sumę dwóch liczb istotnie mniejszych od niej samej.
| |
| | |
| Koniec ćwiczenia 2.7
| |
| }}
| |
| | |
| {{cwiczenie|2.8||
| |
| W trójwymiarowej przestrzeni znajduje się <math>n</math> punktów. Ilość
| |
| punktów w rzutowaniu na płaszczyznę <math>O_x, O_y</math> oznaczamy przez
| |
| <math>n_{xy}</math>. Podobnie ilość punktów w rzutowaniu na <math>O_x, O_z</math> przez
| |
| <math>n_{xz}</math> i ilość punktów w rzutowaniu na <math>O_y, O_z</math> przez
| |
| <math>n_{yz}</math>. Wykaż, że dla dowolnego rozkładu punktów w przestrzeni
| |
| zachodzi nierówność
| |
| | |
| <center><math>
| |
| n^2\leq n_{xy}n_{xz}n_{yz}.
| |
| </math></center>
| |
| | |
| '''Hint 1.''' Użyj nierówności pomiędzy średnią geometryczną, a średnią arytmetyczną
| |
| | |
| | |
| <center><math>
| |
| \frac{1}{2}(a+b)\geq \sqrt{ab}.
| |
| </math></center>
| |
| | |
| | |
| '''Hint 2.''' Podziel punkty na dwie grupy płaszczyzną równoległą do
| |
| którejś z płaszczyzn<br/> <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math>.
| |
|
| |
| '''Solution.''' Dowiedziemy nierówność przy użyciu indukcji.
| |
| | |
| :* Jeśli <math>n=1</math> to <math>n_{xy}=n_{xz}=n_{yz}=1</math> i nierówność jest prawdziwa.
| |
| | |
| :* Zakładamy, że nierówność jest prawdziwa dla wszystkich liczb naturalnych (dla dowolnego układu punktów) mniejszych niż <math>n+1</math>. Rozpoczynamy z dowolnym układem <math>n+1</math> punktów w przestrzeni. Ponieważ <math>n+1>1</math> wiemy, że istnieje płaszczyzna równoległa do którejś z płaszczyzn <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math> i dzieląca <math>n+1</math> punktów na dwie niepuste części posiadające odpowiednio <math>n'</math> i <math>n''</math> 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 <math>O_x, O_y</math>. Stosując założenie indukcyjne do każdej z części otrzymujemy
| |
| | |
| | |
| <center><math>
| |
| {n'}^2\leq n'_{xy}n'_{xz}n'_{yz}
| |
| </math></center>
| |
| | |
| | |
| :oraz
| |
| | |
| | |
| <center><math>
| |
| {n''}^2\leq n''_{xy}n''_{xz}n''_{yz}.
| |
| </math></center>
| |
| | |
| | |
| :Co więcej, pomiędzy projekcjami zachodzą następujące zależności
| |
| | |
| | |
| <center><math>
| |
| n'_{xz}+n''_{xz}=n_{xz} </math> oraz <math> n'_{yz}+n''_{yz}=n_{yz}.
| |
| </math></center>
| |
| | |
| | |
| :Dla płaszczyzny <math>O_x, O_y</math> nie posiadamy podziału na część punktów należących do <math>n'</math> i <math>n''</math> i możemy jedynie wnioskować, że
| |
| | |
| | |
| <center><math>
| |
| n'_{xy}\leq n_{xy} </math> oraz <math> n''_{xy}\leq n_{xy}.
| |
| </math></center>
| |
| | |
| | |
| :Zaczynamy przekształcenia mające udowodnić pożądaną nierówność
| |
| | |
| | |
| <center><math>
| |
| \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
| |
| </math></center>
| |
| | |
| | |
| :używając założenia indukcyjnego i nierówności pomiędzy projekcjami na płaszczyznę <math>O_x, O_y</math>. Kontynuujemy używając nierówności pomiędzy średnią algebraiczną i geometryczną
| |
| | |
| | |
| <center><math>
| |
| \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
| |
| </math></center>
| |
| | |
| | |
| :W ostatnim kroku wystarczy wykorzystać zależności pomiędzy projekcjami na pozostałe dwie współrzędne i
| |
| | |
| | |
| <center><math>
| |
| n^2\leq n_{xy}(n'_{xz} + n''_{xz})(n'_{yz}+n''_{yz})=
| |
| n_{xy}n_{xz}n_{yz}.
| |
| </math></center>
| |
| | |
| | |
| :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 <u>'''Euclid of Alexandria'''</u> a my prezentujemy go w wersji podanej
| |
| przez Ernst'a Kummera.
| |
| | |
| {{twierdzenie|[Istnieje nieskończenie wiele liczb pierwszych]||
| |
| | |
| }}
| |
| | |
| {{dowod|||
| |
| | |
| Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych
| |
| <math>p_0,\dotsc,p_n</math>. Zdefiniujmy liczbę
| |
| | |
| <center><math>
| |
| k = p_0\cdot p_1\cdot\dotsb\cdot p_n
| |
| </math></center>
| |
| | |
| i rozważmy <math>k+1</math>. Liczba <math>k+1</math> posiada dzielnik pierwszy, a
| |
| ponieważ jedynymi pierwszymi liczbami są liczby <math>p_0,\dotsc,p_n</math>
| |
| wnioskujemy, że <math>p_i</math> dzieli <math>k+1</math> dla pewnego <math>i</math>. Liczba <math>p_i</math>
| |
| dzieli również <math>k</math>, a więc <math>p_i</math> dzieli <math>(k+1)-k=1</math> co jest
| |
| sprzecznością.
| |
| }}
| |
| | |
| {{cwiczenie|3.1||
| |
| Wykaż, że nie istnieje największa liczba naturalna.
| |
| | |
| '''Solution.''' Załóżmy, niewprost, że istnieje największa liczba
| |
| naturalna i oznaczmy ją przez <math>n</math>. Niewątpliwie <math>n+1</math> jest liczbą
| |
| naturalną większą od <math>n</math>, co jest sprzecznością z naszym
| |
| założeniem.
| |
| | |
| Koniec ćwiczenia 3.1
| |
| | |
| }}
| |
| | |
| {{cwiczenie|3.2||
| |
| | |
| Wykaż, że <math>\sqrt{2}</math> jest liczbą niewymierną.
| |
|
| |
| '''Solution.''' Załóżmy, niewprost, że <math>\sqrt{2}</math> jest liczbą wymierną, czyli, że istnieją dwie naturalne, względnie pierwsze liczby <math>k</math> i <math>l</math> takie, że
| |
| <math>\sqrt{2}=k/l</math>. Przekształcając ostatnie wyrażenie otrzymujemy <math>k^2=2l^2</math>. Skoro <math>2</math> dzieli lewą stronę równości dzieli też i prawą, a ponieważ dwa jest liczbą pierwszą wnioskujemy, że <math>2</math> dzieli <math>k</math>. Jeśli <math>2</math> dzieli <math>k</math> to <math>4</math> dzieli <math>k^2</math> i na podstawie równości <math>4</math> dzieli <math>2l^2</math>. Wnioskujemy stąd, że <math>2</math>
| |
| dzieli <math>l^2</math> i, na podstawie pierwszości liczby <math>2</math>, że <math>2</math> dzieli
| |
| <math>l</math>. Udowodniliśmy, że <math>2</math> dzieli zarówno <math>k</math> jak i <math>l</math>, 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.
| |
| }}
| |
