Co z tą indukcją? (próbuję ogarnąć)
-
- Użytkownik
- Posty: 486
- Rejestracja: 22 lut 2017, o 14:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 114 razy
- Pomógł: 8 razy
Co z tą indukcją? (próbuję ogarnąć)
\(\displaystyle{ n!\le ne\left( \frac n e\right)^n}\)
OK, może się nie nadaję na studenta matematyki, albo mam zbyt duże zaległości, ale właśnie jestem w trakcie nadrabiania. Chciałbym ogarnąć o co chodzi z dowodzeniem indukcyjnym.
Weźmy przykład, który akurat jest mi potrzebny (podrzucony przez pewnego użytkownika):
\(\displaystyle{ n!\le ne\left( \frac n e\right)^n}\). Dla każdego elementu \(\displaystyle{ n \in \NN}\).
Pierwszy krok:
Sprawdzam prawdziwość stwierdzenia (nierówności) dla \(\displaystyle{ n = 1}\).
\(\displaystyle{ 1! \le e \left( \frac{1}{e} \right)}\)
Zatem:
\(\displaystyle{ 1 = 1}\).
Stwierdzenie więc jest prawdziwe.
Drugi krok:
ustalmy \(\displaystyle{ k \in \NN}\)
I tutaj nie rozumiem za bardzo co robimy i dlaczego. No bo, to tak jakbyśmy za szukali dowodu, że:
\(\displaystyle{ 2 + 2 = 4}\) i stwierdzili, że tak, bo \(\displaystyle{ \frac{4}{2} + 2 = \frac{8}{2} = 4}\) i uznali to za dowód. Więc czegoś tu nie widzę. :/
i sprawdzamy czy działa dla (k+1), przecież nie udowodniliśmy tego dla k, więc dlaczego zakładamy (o ile zakładamy), że to poprawne?
OK, może się nie nadaję na studenta matematyki, albo mam zbyt duże zaległości, ale właśnie jestem w trakcie nadrabiania. Chciałbym ogarnąć o co chodzi z dowodzeniem indukcyjnym.
Weźmy przykład, który akurat jest mi potrzebny (podrzucony przez pewnego użytkownika):
\(\displaystyle{ n!\le ne\left( \frac n e\right)^n}\). Dla każdego elementu \(\displaystyle{ n \in \NN}\).
Pierwszy krok:
Sprawdzam prawdziwość stwierdzenia (nierówności) dla \(\displaystyle{ n = 1}\).
\(\displaystyle{ 1! \le e \left( \frac{1}{e} \right)}\)
Zatem:
\(\displaystyle{ 1 = 1}\).
Stwierdzenie więc jest prawdziwe.
Drugi krok:
ustalmy \(\displaystyle{ k \in \NN}\)
I tutaj nie rozumiem za bardzo co robimy i dlaczego. No bo, to tak jakbyśmy za szukali dowodu, że:
\(\displaystyle{ 2 + 2 = 4}\) i stwierdzili, że tak, bo \(\displaystyle{ \frac{4}{2} + 2 = \frac{8}{2} = 4}\) i uznali to za dowód. Więc czegoś tu nie widzę. :/
i sprawdzamy czy działa dla (k+1), przecież nie udowodniliśmy tego dla k, więc dlaczego zakładamy (o ile zakładamy), że to poprawne?
- scyth
- Użytkownik
- Posty: 6392
- Rejestracja: 23 lip 2007, o 15:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 1087 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Pierwszy krok indukcyjny: sprawdzamy czy działa dla najmniejszej wartości (np. dla 1).
Drugi krok indukcyjny: przyjmijmy że jest to prawda dla jakiegoś (bliżej nieokreślonego) \(\displaystyle{ k}\) - czy będzie to też prawdą dla \(\displaystyle{ k+1}\)?
Jeśli uda ci się wykazać punkt pierwszy (zazwyczaj trywialne) i punkt drugi (w tym kłopot) to masz takie dwie informacje:
1. Jest to prawda dla najmniejszej wartości.
2. Jest to prawda dla kolejnej wartości, o ile poprzednia była prawdziwa.
Zatem skoro jest to prawda dla najmniejszej, to też dla najmniejszej+1, a więc też dla najmniejszej+2, najmniejszej+3 itd. itd. - to jest właśnie indukcja.
Drugi krok indukcyjny: przyjmijmy że jest to prawda dla jakiegoś (bliżej nieokreślonego) \(\displaystyle{ k}\) - czy będzie to też prawdą dla \(\displaystyle{ k+1}\)?
Jeśli uda ci się wykazać punkt pierwszy (zazwyczaj trywialne) i punkt drugi (w tym kłopot) to masz takie dwie informacje:
1. Jest to prawda dla najmniejszej wartości.
2. Jest to prawda dla kolejnej wartości, o ile poprzednia była prawdziwa.
Zatem skoro jest to prawda dla najmniejszej, to też dla najmniejszej+1, a więc też dla najmniejszej+2, najmniejszej+3 itd. itd. - to jest właśnie indukcja.
-
- Użytkownik
- Posty: 486
- Rejestracja: 22 lut 2017, o 14:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 114 razy
- Pomógł: 8 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
OKi, to sporo wyjaśnia, dziękuję. Mam jednak jeszcze wątpliwość: skąd wiadomo, że dla tego bliżej nieokreślonego \(\displaystyle{ k}\) to jest prawda?
- scyth
- Użytkownik
- Posty: 6392
- Rejestracja: 23 lip 2007, o 15:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 1087 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Nie wiadomo, zakładamy po prostu że tak jest i z tego założenia chcemy wyciągnąć wniosek, że dla kolejnej liczby też tak będzie. I tak naprawdę nie musisz się tym martwić czy dla wybranego \(\displaystyle{ k}\) to jest prawda czy nie - bo potem przyjmujesz \(\displaystyle{ k=1}\) dla którego wcześniej wykazałeś że jest to prawda. Ale ważne - przyjmujesz to potem, bo gdybyś od razu przyjął \(\displaystyle{ k=1}\) to jedyne co wykażesz to to, że jest to prawda dla \(\displaystyle{ k=1}\) i \(\displaystyle{ k=2}\). Stąd potrzeba liczenia "na literach".
- Janusz Tracz
- Użytkownik
- Posty: 4105
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1409 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Nie wiadomo, dlatego to zakładamy. W indukcji nie pokazujesz bezpośrednio tezy pokazujesz prawdziwość implikacji pomiędzy tezą dla dowolnego \(\displaystyle{ k}\) i tezą dla \(\displaystyle{ k+1}\). Czyli wiesz że prawdą jest \(\displaystyle{ T(k) \Rightarrow T(k+1)}\) wiesz również że dla \(\displaystyle{ k=1}\) teza jest prawdziwa dlatego:
\(\displaystyle{ T(1) \Rightarrow T(2)}\)
ale potem
\(\displaystyle{ T(2) \Rightarrow T(3)}\)
\(\displaystyle{ T(3) \Rightarrow T(4)}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ T(n) \Rightarrow T(n+1)}\)
\(\displaystyle{ T(1) \Rightarrow T(2)}\)
ale potem
\(\displaystyle{ T(2) \Rightarrow T(3)}\)
\(\displaystyle{ T(3) \Rightarrow T(4)}\)
\(\displaystyle{ ...}\)
\(\displaystyle{ T(n) \Rightarrow T(n+1)}\)
-
- Użytkownik
- Posty: 486
- Rejestracja: 22 lut 2017, o 14:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 114 razy
- Pomógł: 8 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Sprytne.
Wracając więc do zadania:
Dla \(\displaystyle{ n = 1}\), dowiodłem(?), że to prawda.
Teraz drugi krok indukcji:
Zakładam, że:
Dla każdego \(\displaystyle{ k \in \NN}\) prawdą jest, że \(\displaystyle{ k! \le ke \left( \frac{k}{e} \right) ^k}\)
Chcę wykazać, że jest to prawdziwa nierówność również dla \(\displaystyle{ (k+1)}\)
\(\displaystyle{ (k+1)! \le (k+1)e \left( \frac{k+1}{e}\right)^{k+1}}\)
Wiemy, że \(\displaystyle{ (k+1) > 0}\), więc dzielimy przez nie obie strony.
\(\displaystyle{ k! \le e \left( \frac{k+1}{e}\right) ^{k+1}}\)
\(\displaystyle{ k! \le \frac{(k+1)^{k+1}}{e^k} = \frac{(k+1)^{k} (k+1)}{e^k}}\)
\(\displaystyle{ 1 \le \frac{(k+1)^{k} (k+1)}{e^k k!}}\)
dzielę przez k:
\(\displaystyle{ 1 \le \frac{2(k+1)^{k}}{e^k (k-1)!}}\)
Dobra lipę mam, nie wymyślę. :/
Wracając więc do zadania:
Dla \(\displaystyle{ n = 1}\), dowiodłem(?), że to prawda.
Teraz drugi krok indukcji:
Zakładam, że:
Dla każdego \(\displaystyle{ k \in \NN}\) prawdą jest, że \(\displaystyle{ k! \le ke \left( \frac{k}{e} \right) ^k}\)
Chcę wykazać, że jest to prawdziwa nierówność również dla \(\displaystyle{ (k+1)}\)
\(\displaystyle{ (k+1)! \le (k+1)e \left( \frac{k+1}{e}\right)^{k+1}}\)
Wiemy, że \(\displaystyle{ (k+1) > 0}\), więc dzielimy przez nie obie strony.
\(\displaystyle{ k! \le e \left( \frac{k+1}{e}\right) ^{k+1}}\)
\(\displaystyle{ k! \le \frac{(k+1)^{k+1}}{e^k} = \frac{(k+1)^{k} (k+1)}{e^k}}\)
\(\displaystyle{ 1 \le \frac{(k+1)^{k} (k+1)}{e^k k!}}\)
dzielę przez k:
\(\displaystyle{ 1 \le \frac{2(k+1)^{k}}{e^k (k-1)!}}\)
Dobra lipę mam, nie wymyślę. :/
- scyth
- Użytkownik
- Posty: 6392
- Rejestracja: 23 lip 2007, o 15:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 1087 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Musisz skorzystać gdzieś z założenia indukcyjnego. Może zacznij od:
\(\displaystyle{ (k+1)! = (k+1) \cdot k! \le (k+1) \cdot ke\left( \frac{k}{e}\right)^k \le \ldots}\)
No i teraz kombinuj co może być większe od tego co tam jest po prawej - miej na uwadze do czego chcesz ostatecznie dojść, drobnymi krokami jedno podstawienie za drugim i to dostaniesz.
\(\displaystyle{ (k+1)! = (k+1) \cdot k! \le (k+1) \cdot ke\left( \frac{k}{e}\right)^k \le \ldots}\)
No i teraz kombinuj co może być większe od tego co tam jest po prawej - miej na uwadze do czego chcesz ostatecznie dojść, drobnymi krokami jedno podstawienie za drugim i to dostaniesz.
-
- Użytkownik
- Posty: 486
- Rejestracja: 22 lut 2017, o 14:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 114 razy
- Pomógł: 8 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
\(\displaystyle{ (k+1)! = (k+1) \cdot k! \le (k+1) \cdot ke\left( \frac{k}{e}\right)^k \le}\)scyth pisze:Musisz skorzystać gdzieś z założenia indukcyjnego. Może zacznij od:
\(\displaystyle{ (k+1)! = (k+1) \cdot k! \le (k+1) \cdot ke\left( \frac{k}{e}\right)^k \le \ldots}\)
No i teraz kombinuj co może być większe od tego co tam jest po prawej - miej na uwadze do czego chcesz ostatecznie dojść, drobnymi krokami jedno podstawienie za drugim i to dostaniesz.
Nie bardzo rozumiem co się tutaj stało.
Obie strony pomnożone przez (k+1)
rozumiem, że takie jest założenie indukcyjne, ale dlaczego nie podstawiamy wszędzie tam gdzie \(\displaystyle{ k}\) - \(\displaystyle{ k+1}\) ?
- Janusz Tracz
- Użytkownik
- Posty: 4105
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1409 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Pytamy się o tezę dla \(\displaystyle{ k+1}\) przy jednoczesnym założeniu \(\displaystyle{ k! \le ke\left( \frac{k}{e} \right)^k}\). Lewa strona tezy to
\(\displaystyle{ \left( k+1\right)!=k!(k+1)}\)
ale my wiemy że \(\displaystyle{ k! \le ke\left( \frac{k}{e} \right)^k}\) dlatego:
\(\displaystyle{ k!(k+1) \le (k+1)ke\left( \frac{k}{e} \right)^k}\)
To jeśli teraz pokazali byśmy że \(\displaystyle{ (k+1)ke\left( \frac{k}{e} \right)^k \le (k+1)e\left( \frac{k+1}{e} \right)^{k+1}}\)
to pokazali byśmy że
\(\displaystyle{ \left( k+1\right)! \le (k+1)e\left( \frac{k+1}{e} \right)^{k+1}}\)
czyli innymi słowy pokazali byśmy prawdziwość wynikania \(\displaystyle{ T(k) \Rightarrow T(k+1)}\)
\(\displaystyle{ \left( k+1\right)!=k!(k+1)}\)
ale my wiemy że \(\displaystyle{ k! \le ke\left( \frac{k}{e} \right)^k}\) dlatego:
\(\displaystyle{ k!(k+1) \le (k+1)ke\left( \frac{k}{e} \right)^k}\)
To jeśli teraz pokazali byśmy że \(\displaystyle{ (k+1)ke\left( \frac{k}{e} \right)^k \le (k+1)e\left( \frac{k+1}{e} \right)^{k+1}}\)
to pokazali byśmy że
\(\displaystyle{ \left( k+1\right)! \le (k+1)e\left( \frac{k+1}{e} \right)^{k+1}}\)
czyli innymi słowy pokazali byśmy prawdziwość wynikania \(\displaystyle{ T(k) \Rightarrow T(k+1)}\)
jeśli jeszcze tego nie rozumiesz to nie podglądaj. Zobacz czy samodzielnie jesteś w stanie dokończyć ten dowód.:
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Tak to nie, wówczas przecież nie ma już czego dowodzić, bo zakończyłeś "dowód" przez założenie tezy. W (nielubianym przeze mnie) podręczniku do szkoły średniej autorów Kłaczkow, Kurczab, Świda została przywołana taka analogia (cytat za stroną wazniak, , bo nie mam przy sobie tej książki, a to jest dokładnie ten przykład/ilustracja, zaś ja nie umiem ładnie budować obrazowych zdań):Rozbitek pisze:Zakładam, że:
Dla każdego \(\displaystyle{ k \in \NN}\) prawdą jest, że \(\displaystyle{ k! \le ke \left( \frac{k}{e} \right) ^k}\)
Często używaną ilustracją indukcji matematycznej jest efekt domina. Załóżmy, że ułożyliśmy bardzo dużo kostek domina, jedna za drugą. Upewniliśmy się też, że jeśli przewróci się dowolna z nich (założenie indukcyjne) to przewróci się też następna (krok indukcyjny). Wtedy, jeśli ktoś nam powie, że przewrócił czwartą kostkę (baza indukcji) to wiemy, iż wszystkie następne (poza być może pierwszymi trzema) też się przewróciły. W indukcji matematycznej liczby naturalne są niejako kostkami domina ułożonymi dostatecznie blisko siebie.
Co do rozwiązania, powyżej już Janusz Tracz się wypowiedział.
- Janusz Tracz
- Użytkownik
- Posty: 4105
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 81 razy
- Pomógł: 1409 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Ja lubię takie powiedzenie które sam wymyśliłem "sercem indukcji jest implikacja". W indukcji wszystko kręci się wokół pokazania prawdziwości implikacji przy czym wiemy że dla pierwszego klocka domina teza jest prawdziwa, potem domino rusza i leci przez wszystkie naturalne liczby.
-
- Użytkownik
- Posty: 1668
- Rejestracja: 16 cze 2006, o 15:40
- Płeć: Kobieta
- Podziękował: 71 razy
- Pomógł: 447 razy
Co z tą indukcją? (próbuję ogarnąć)
Co w tej analogii jest wyraźne i bardzo mi się podoba, to zastosowanie pojęcia krok indukcyjny - nie jeden z etapów dowodu indukcyjnego (więc nie pierwszy, drugi krok itd.), ale konkretny etap tegoż dowodu, czyli przejście od \(\displaystyle{ k}\) do \(\displaystyle{ k+1}\).
-
- Użytkownik
- Posty: 486
- Rejestracja: 22 lut 2017, o 14:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 114 razy
- Pomógł: 8 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
\(\displaystyle{ (k+1)ke\left( \frac{k}{e} \right)^k \le (k+1)e\left( \frac{k+1}{e} \right)^{k+1}}\)
\(\displaystyle{ ke\left( \frac{k}{e} \right)^k \le e\left( \frac{k+1}{e} \right)^{k+1}}\)
\(\displaystyle{ kek^k \le (k+1)^{k+1}}\)
\(\displaystyle{ \sqrt[k]{ke} \le 1 + \frac{1}{k} (k+1)}\)
\(\displaystyle{ ke \le (1 + \frac{1}{k})^k (k+1)^k}\)
I dalej mam problem.
@Premislav
A więc zakładam, że po prostu, że dla jakiegoś naturalnego \(\displaystyle{ k}\) - Teza jest prawdziwa?
\(\displaystyle{ ke\left( \frac{k}{e} \right)^k \le e\left( \frac{k+1}{e} \right)^{k+1}}\)
\(\displaystyle{ kek^k \le (k+1)^{k+1}}\)
\(\displaystyle{ \sqrt[k]{ke} \le 1 + \frac{1}{k} (k+1)}\)
\(\displaystyle{ ke \le (1 + \frac{1}{k})^k (k+1)^k}\)
I dalej mam problem.
@Premislav
A więc zakładam, że po prostu, że dla jakiegoś naturalnego \(\displaystyle{ k}\) - Teza jest prawdziwa?
-
- Użytkownik
- Posty: 22276
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3765 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Krok indukcyjny polega na tym, żeby udowodnić \(\displaystyle{ \frac{(k+1)^{k+1}}{e^k}\geq k!}\) korzystając z założenia indukcyjnego, że \(\displaystyle{ \red{ \frac{k^k}{e^{k-1}}\geq (k-1)!}}\). Sprawdź, że to jest równoważne sformułowanie dowodzonej nierówności).
Żeby skorzystać z czerwonego, trzeba je jakoś "wyprodukować" Najprościej chyba tak
\(\displaystyle{ \frac{(k+1)^{k+1}}{e^k}=\frac{1}{e}\frac{(k+1)^{k+1}}{k^k}\cdot \red{ \frac{k^k}{e^{k-1}}}}\)
Dalej już prosto, o ile wykorzystasz fakt, że \(\displaystyle{ \frac{(k+1)^{k+1}}{k^{k+1}}>e}\).
Żeby skorzystać z czerwonego, trzeba je jakoś "wyprodukować" Najprościej chyba tak
\(\displaystyle{ \frac{(k+1)^{k+1}}{e^k}=\frac{1}{e}\frac{(k+1)^{k+1}}{k^k}\cdot \red{ \frac{k^k}{e^{k-1}}}}\)
Dalej już prosto, o ile wykorzystasz fakt, że \(\displaystyle{ \frac{(k+1)^{k+1}}{k^{k+1}}>e}\).
-
- Administrator
- Posty: 34486
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5220 razy
Re: Co z tą indukcją? (próbuję ogarnąć)
Krok indukcyjny jest stwierdzeniem warunkowym. Ustalasz dowolne \(\displaystyle{ k\in\NN}\) i teraz sprawdzasz, czy jeśli teza jest prawdziwa dla \(\displaystyle{ k}\), to jest też prawdziwa dla \(\displaystyle{ k+1}\) (w analogii z dominem jest to sprawdzenie, czy kostki są dobrze ustawione). Nie jest to zatem absolutne założenie, że teza jest prawdziwa dla \(\displaystyle{ k}\) (kostka nr \(\displaystyle{ k}\) upadła), tylko gdybanie - czy gdyby kostka \(\displaystyle{ k}\) upadła, to kostka \(\displaystyle{ k+1}\) też upadnie.Rozbitek pisze:A więc zakładam, że po prostu, że dla jakiegoś naturalnego \(\displaystyle{ k}\) - Teza jest prawdziwa?
Tak naprawdę tzw. dowód indukcyjny polega przede wszystkim na sprawdzeniu, czy spełnione są założenia Zasady indukcji matematycznej. Na końcu powinno się tę Zasadę zastosować, ale na ogół zapomina się to zrobić...
JK