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

[Rozbitek]

\(\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?

[scyth]

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.

[Rozbitek]

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]

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]

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)}\)

[Rozbitek]

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ę. :/

[scyth]

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.

[Rozbitek]

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}\)
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]

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)}\)

jeśli jeszcze tego nie rozumiesz to nie podglądaj. Zobacz czy samodzielnie jesteś w stanie dokończyć ten dowód.:    

Zostało pokazać tylko

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

To jest równoważne

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

a to po przekształceniu zwija się do

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

tu stop. Wiemy z nierówności Bernulliego (którą też można pokazać indukcyjnie) że ciąg \(\displaystyle{ \left( 1+ \frac{1}{k} \right)^{k+1}}\) jest malejący łatwo też pokazać że \(\displaystyle{ \left( 1+ \frac{1}{k} \right)^{k+1} \rightarrow e}\).
Co kończy dowód

[Premislav]

Zakładam, że:
Dla każdego \(\displaystyle{ k \in \NN}\) prawdą jest, że \(\displaystyle{ k! \le ke \left( \frac{k}{e} \right) ^k}\)

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ń):
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]

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.

[bosa_Nike]

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}\).

[Rozbitek]

\(\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?

[a4karo]

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}\).

[Jan Kraszewski]

A więc zakładam, że po prostu, że dla jakiegoś naturalnego \(\displaystyle{ k}\) - Teza jest prawdziwa?

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.

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