Co z tą indukcją? (próbuję ogarnąć)

Ze względu na specyfikę metody - osobny dział.
Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 29 paź 2017, o 12:18

Czyli:
Pierwszy krok:
Sprawdzam prawdziwość stwierdzenia (nierówności) dla n = 1.
\(\displaystyle{ 1! \le e \left( \frac{1}{e} \right)}\)
Zatem:
\(\displaystyle{ 1 = 1}\).
Stwierdzenie więc jest prawdziwe.

Drugi krok:

Sprawdzam czy jeżeli dla jakieś k, dla którego zachodzi:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k}\)
to zachodzi to dla \(\displaystyle{ k+1}\):
\(\displaystyle{ (k+1)! = k! \cdot (k+1) \le (k+1)e \left( \frac{k+1}{e} \right)^{k+1}}\)

\(\displaystyle{ k! \le e \left( \frac{(k+1)^{k+1}}{e^{k+1}} \right) = (k+1) \left( \frac{(k+1)^{k}}{e^{k}} \right) = (k+1) \left( \frac{k+1}{e} \right)^k}\)

\(\displaystyle{ ke \left( \frac{k}{e} \right)^k \le (k+1) \left( \frac{k+1}{e} \right)^k \\ kek^k \le (k+1)^{k+1} \\ ek^{k+1} \le (k+1)^{k+1} \\ \sqrt[k+1]{e} \le 1 + \frac{1}{k} \\ e \le \left( 1 + \frac{1}{k} \right)^k+1}\)

Dalej mam problem, ale chyba użyłem założenia indukcyjnego.
Ostatnio zmieniony 29 paź 2017, o 14:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3145
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 73 razy
Pomógł: 1070 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Janusz Tracz » 29 paź 2017, o 17:02

ale chyba użyłem założenia indukcyjnego.
A to dobrze czy źle?
\(\displaystyle{ (k+1)! = k! \cdot (k+1) \le (k+1)e \left( \frac{k+1}{e} \right)^{k+1}}\)
Tego nie wiesz, możesz się tylko o to spytać ale nie wolno Ci tego zakładać.
Dlatego to co jest dalej jest chyba niepoprawne Ty to dopiero chcesz pokazać
\(\displaystyle{ ke \left( \frac{k}{e} \right)^k \le (k+1) \left( \frac{k+1}{e} \right)^k}\)
To jest oczywiste i nieprzydatne w dowodzie.
Zobacz co pisałem wcześniej (text ukryty) bo cały dowód jest już spisany w tym poście.
Nie bój używać się też języka polskiego w dowodach bo to pomoże i Tobie i sprawdzającemu.

Jan Kraszewski
Administrator
Administrator
Posty: 27289
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4594 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Jan Kraszewski » 29 paź 2017, o 17:41

Janusz Tracz pisze:Nie bój używać się też języka polskiego w dowodach bo to pomoże i Tobie i sprawdzającemu.
Dokładnie. Na razie jest ściana znaczków. Nie wiadomo, czy zakładasz tezę (fatalnie), czy przekształcasz tezę równoważnie (dozwolone), a jeśli przekształcasz, to jak to robisz. Pamiętaj, że dowód piszesz dla czytelnika i nie jest jego rolą domyślać się, co autor miał na myśli.

JK

Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 29 paź 2017, o 23:31

Chciałbym sam do tego dojść, bo dowód Twój niby rozumiem,a wychodzi, że nie rozumiem.

Oczywiście spróbuję opisywać co robię.

Drugi krok:

Zakładam, że dla jakiegoś k zachodzi:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k}\)
I sprawdzam czy zachodzi:
\(\displaystyle{ (k+1)! = k! \cdot (k+1) \le (k+1)e \left( \frac{k+1}{e} \right)^{k+1}}\)
Pozwolę sobie uprościć:
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1}}\)

Rozumiem, że skoro zakładam:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k}\), to mam prawo z tego korzystać jak mi się podoba?

Wyjdę więc z tej postaci i spróbuję dojść do postaci, którą mam udowodnić:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k = e \left( \frac{k+1}{e} \right)^k}\)
No i tutaj właściwie moje pomysły się kończą. Pewnie dlatego, że źle zacząłem, ale od czego mam zacząć, żeby nie korzystać z tezy? A może da się to jakoś dalej z założenia wyprowadzić, a ja po prostu nie widzę?

Jan Kraszewski
Administrator
Administrator
Posty: 27289
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4594 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Jan Kraszewski » 29 paź 2017, o 23:44

Rozbitek pisze:Rozumiem, że skoro zakładam:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k}\), to mam prawo z tego korzystać jak mi się podoba?
Tak.
Rozbitek pisze:Wyjdę więc z tej postaci i spróbuję dojść do postaci, którą mam udowodnić:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k \red=\black e \left( \frac{k+1}{e} \right)^k}\)
A ta równość to skąd?

JK

Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 29 paź 2017, o 23:46

Jan Kraszewski pisze:
Rozbitek pisze:Wyjdę więc z tej postaci i spróbuję dojść do postaci, którą mam udowodnić:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k \red=\black e \left( \frac{k+1}{e} \right)^k}\)
A ta równość to skąd?
Ojej, masakra. To błąd oczywiście.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3145
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 73 razy
Pomógł: 1070 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Janusz Tracz » 30 paź 2017, o 00:09

I sprawdzam czy zachodzi:
\(\displaystyle{ (k+1)! = k! \cdot (k+1) \le (k+1)e \left( \frac{k+1}{e} \right)^{k+1}}\)
Pozwolę sobie uprościć:
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
No jesteś już bardzo blisko bo teraz problem pokazania
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
na mocy założenia indukcyjnego powinieneś sprowadzić do nierówności mocniejszej tj.
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
I spróbować udowodnić
\(\displaystyle{ ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
jeśli okaże się to prawdą to z przechodniości nierówności prawdą okaże się również
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
czyli
\(\displaystyle{ (k+1)!\le (k+1)e \left( \frac{k+1}{e} \right)^{k+1}}\)
I dowód będzie można uznać za zakończony.

To działa tak że chcesz pokazać że
\(\displaystyle{ a<c}\) ale tego nie wiesz...
wiesz jednak że \(\displaystyle{ a<b}\)
to teraz zadajesz pytanie "A może \(\displaystyle{ b<c}\)? Warto to sprawić... "
Sprawdzasz czy \(\displaystyle{ b<c}\)
Hura! Udaje Ci się.
Teraz jasne jest że \(\displaystyle{ a<c}\)
CND

Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 1 lis 2017, o 13:18

\(\displaystyle{ ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\)
Mnożę obie strony przez \(\displaystyle{ e^k}\)

\(\displaystyle{ kek^k \le (k+1)^{k+1}}\)
\(\displaystyle{ kek^k \le (k+1)^{k} (k+1)}\)

Dzielę przez \(\displaystyle{ k}\):
\(\displaystyle{ ek^k \le (k+1)^{k} (1 + \frac{1}{k})}\)
Teraz dzielę przez \(\displaystyle{ k^k}\) obie strony.

\(\displaystyle{ e \le \left(1 + \frac{1}{k} \right)^k (1 + \frac{1}{k})}\)

I tutaj wracam do tego samego problemu. Jedyne co mi przychodzi do głowy, to podstawienie pierwszych liczb i powołania się na to, że jest to ciąg rosnący. Druga sprawa, to oczywiście to, że granicą tego ciągu jest liczba \(\displaystyle{ e}\), tylko nie wiem jak mógłbym skorzystać z tego faktu?


Ponadto nie rozumiem jaką mamy pewność, że jest tak:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\),
a nie może być tak:
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1} \le ke \left( \frac{k}{e} \right)^k}\) ?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15207
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5046 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Premislav » 1 lis 2017, o 14:15

I tutaj wracam do tego samego problemu. Jedyne co mi przychodzi do głowy, to podstawienie pierwszych liczb i powołania się na to, że jest to ciąg rosnący. Druga sprawa, to oczywiście to, że granicą tego ciągu jest liczba e, tylko nie wiem jak mógłbym skorzystać z tego faktu?
\(\displaystyle{ \left( 1+\frac{1}{k+1}\right)^{k+2}<\left( 1+ \frac{1}{k} \right)^{k+1} \Leftrightarrow\left( 1+\frac{1}{k+1}\right)^{k+1} \cdot \left( 1+\frac{1}{k+1}\right) <\left( 1+\frac 1 k\right)^{k+1} \Leftrightarrow \\ \Leftrightarrow 1+\frac{1}{k+1}<\left( \frac{1+\frac 1 k}{1+\frac 1{k+1}} \right)^{k+1} \Leftrightarrow 1+\frac 1 {k+1}<\left( 1+\frac{1}{(k+1)^2}\right)^{k+1}}\),
a ta ostatnia nierówność jest prawdziwa, ponieważ kładąc w nierówności Bernoulliego:
\(\displaystyle{ (1+x)^a\ge 1+ax, \ x\ge -1, a\ge 1}\) (dla \(\displaystyle{ x}\) dodatnich i \(\displaystyle{ a>1}\) - jak tutaj - nierówność jest ostra)
za \(\displaystyle{ x:=\frac{1}{k(k+1}}, \ a:=k+1}\), mamy
\(\displaystyle{ \left( 1+\frac{1}{(k+1)^2}\right)^{k+1} > 1+ \frac{k+1}{(k+1)^2} =1+\frac{1}{k+1}}\)

Pokazaliśmy w ten sposób z definicji, że ciąg \(\displaystyle{ a_k=\left( 1+\frac{1}{k}\right)^{k+1}}\) jest malejący. Ponadto jego granicą jest \(\displaystyle{ e}\).
Zatem dla każdego \(\displaystyle{ k \in \NN^+}\) jest
\(\displaystyle{ \left(1+\frac{1}{k} \right)^{k+1}\ge e}\), a to jest, jak wynika z Twoich przekształceń, równoważne nierówności
\(\displaystyle{ ek^k \le (k+1)^{k} (1 + \frac{1}{k})}\), zatem jest ona prawdziwa dla każdego \(\displaystyle{ k \in \NN^+}\).
Ponadto nie rozumiem jaką mamy pewność, że jest tak:
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\),
a nie może być tak:
\(\displaystyle{ k! \le e \left( \frac{k+1}{e} \right)^{k+1} \le ke \left( \frac{k}{e} \right)^k}\)
Nie rozumiem pytania.
Pokazujesz, że \(\displaystyle{ \textbf{Jeśli}}\) dla pewnego \(\displaystyle{ k \in \NN^+}\) zachodzi nierówność
\(\displaystyle{ k!\le ke\left( \frac k e\right)^k, \ \textbf{to}}\) prawdziwa jest też nierówność
\(\displaystyle{ (k+1)!\le (k+1)e\left( \frac{k+1}{e}\right)^{k+1}}\)
Nierówność
\(\displaystyle{ k! \le ke \left( \frac{k}{e} \right)^k}\) to nasze założenie indukcyjne.
Chcesz pokazać, że z tego wynika
\(\displaystyle{ (k+1)! \le (k+1)e\left( \frac{k+1}{e}\right)^{k+1}}\),
co jest istotnie równoważne nierówności
\(\displaystyle{ k!\le e\left( \frac{k+1}{e}\right)^{k+1}}\)
i oczywiście jeśli pokażemy, że istnieje takie \(\displaystyle{ A_k}\), iż
\(\displaystyle{ k!\le A_k \le e\left( \frac{k+1}{e}\right)^{k+1}}\),
to sprawa załatwiona, bo nierówności są przechodnie. No to próbujemy korzystać z założenia indukcyjnego, by podać takie \(\displaystyle{ A_k}\).
Gdyby się okazało, że jednak jest
\(\displaystyle{ e \left( \frac{k+1}{e} \right)^{k+1} \le ke \left( \frac{k}{e} \right)^k}\)
dla pewnego \(\displaystyle{ k}\), to by znaczyło, że teza zadania jest fałszywa lub mamy za słabe założenie indukcyjne, by udowodnić tezę (i trzeba je wzmocnić) lub nieumiejętnie szacowaliśmy.

Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 2 lis 2017, o 07:48

Dziękuję za wyjaśnienie.

Moje pytanie dotyczyło - skąd wiemy, że faktycznie tak jest: \(\displaystyle{ ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\)?
I tego jeszcze nie kumam.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15207
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5046 razy

Re: Co z tą indukcją? (próbuję ogarnąć)

Post autor: Premislav » 2 lis 2017, o 11:17

Przecież powyżej to udowodniłem. Przeoczyłeś ten fragment?
W poście poprzedzającym mój samodzielnie przekształciłeś równoważnie nierówność, którą chcemy pokazać w celu realizacji drugiego kroku indukcyjnego:
\(\displaystyle{ \left( * \right) \ ke \left( \frac{k}{e} \right)^k \le e \left( \frac{k+1}{e} \right)^{k+1}}\),
do postaci
\(\displaystyle{ e \le \left(1 + \frac{1}{k} \right)^k \left( 1 + \frac{1}{k} \right)}\)
Ciąg \(\displaystyle{ a_k= \left(1 + \frac{1}{k} \right)^k \left( 1 + \frac{1}{k} \right)}\) jest malejący (nie rosnący, wbrew temu, co wyżej pisałeś) i jego granicą jest \(\displaystyle{ e}\).
To, że jest malejący udowodniłem w poście wyżej. Skoro \(\displaystyle{ \left( a_k \right)}\) jest malejący i jego granicą jest \(\displaystyle{ e}\), to wiemy, że dla każdego \(\displaystyle{ k\in \NN}\) zachodzi nierówność \(\displaystyle{ a_k \ge e}\), a to jest właśnie równoważne naszej nierówności \(\displaystyle{ \left( * \right)}\).
Jeżeli nie wiesz, jak wywnioskować to pogrubione, to jest bardzo źle (jeszcze zrozumiałbym, gdybyś był licealistą bądź uczniem technikum/studentem pierwszego semestru). Gdyby dla pewnego \(\displaystyle{ k_0 \in \NN^+}\) było \(\displaystyle{ a_{k_0}<e}\), to oznaczałoby, że istnieje takie \(\displaystyle{ r>0}\), iż \(\displaystyle{ a_k_0 \le e-r}\). Ponieważ ciąg \(\displaystyle{ \left( a_k \right)}\) jest malejący, więc wówczas dla każdego \(\displaystyle{ k\in \NN}\) większego od \(\displaystyle{ k_0}\) mielibyśmy \(\displaystyle{ a_k \le e-r}\).
Zatem granicą \(\displaystyle{ \left( a_k \right)}\) nie mogłoby być \(\displaystyle{ e}\), ponieważ w zbiorze
\(\displaystyle{ \left( e-r, e+r\right)}\) byłoby co najwyżej skończenie wiele (nie więcej niż \(\displaystyle{ k_0-1}\)) wyrazów ciągu \(\displaystyle{ \left( a_k \right)}\).

Rozbitek
Użytkownik
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ąć)

Post autor: Rozbitek » 2 lis 2017, o 13:33

Premislav pisze:Przecież powyżej to udowodniłem.
Ahh, to by wiele wyjaśniało...
Chciałbym jakieś zadanie zrobić, może prostsze. Mam nadzieję, że tworzenie nowego tematu do tego jest zbędne?

Należy wykazać, że dla \(\displaystyle{ n \in \NN, n \ge 1}\)
\(\displaystyle{ 1+2+3+...+n = \frac{n(n+1)}{2}}\)

Sprawdzam najpierw, czy dla \(\displaystyle{ n = 1}\) wzór jest prawdziwy:

\(\displaystyle{ 1 = \frac{1(1+1)}{2} = 1}\)

Zgadza się, jest!

Krok drugi:
Zakładam, że: \(\displaystyle{ 1+2+3+...+k = \frac{k(k+1)}{2}}\).
I chcę sprawdzić, czy prawdą jest:

\(\displaystyle{ 1+2+3+...+k+(k+1) = \frac{(k+1)(k+2)}{2} = \frac{k^2 + 3k + 2}{2}}\)
Na mocy założenia indukcyjnego:
\(\displaystyle{ 1+2+3+...+k+ (k+1) = \frac{k(k+1)}{2} + (k+1)}\)(dodałem obustronnie \(\displaystyle{ (k+1)}\))
Pozostaje więc wykazać, że:
\(\displaystyle{ \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}}\)

Sprowadzam lewą stronę do wspólnego mianownika:
\(\displaystyle{ \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}}\)

Dalej robię przekształcenia:
\(\displaystyle{ \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2}}\)

\(\displaystyle{ \frac{k^2+k+2k+2}{2} = \frac{k^2 + 3k + 2}{2}}\)

\(\displaystyle{ \frac{k^2+3k+2}{2} = \frac{k^2 + 3k + 2}{2}}\)

Więc dla każdego \(\displaystyle{ n=k}\), wzór jest prawdziwy.
Jest OK?

ODPOWIEDZ