Matematyka.pl

Chyba tu nie chodzi o zwykłą indukcję matematyczną.
Mógłby ktoś wytłumaczyć jak robić takie zadania?

Dla każdego z ciągów zdefiniowanych rekurencyjnie wyznaczyć trzeci, piąty i dziesiąty wyraz
oraz udowodnić podaną nierówność:

\(\displaystyle{ a_0=1,a_1=2,a_2=3 \\ a_n=a_{n-2}+2a_{n-3}}\)

Trzeba udowodnić tą nierówność:

\(\displaystyle{ a_n \ge \left( \frac{3}{2} \right) ^n}\) dla \(\displaystyle{ n \ge 1}\)


wiem jak wyliczyć wyrazy, ale jak udowodnić nierówność?
pewnie trzeba znaleźć jawny wzór na \(\displaystyle{ a_n}\), zamiast rekurencyjny. jak to zrobić?

Zrób to indukcyjne.
Wskazówka : \(\displaystyle{ 56>54}\)

*Tę nierówność.

Nie trzeba wcale znajdować wzoru jawnego (choć można), wystarczy indukcja o następującym schemacie: najpierw sprawdzamy prawdziwość \(\displaystyle{ T(0), \ T(1), \ T(2)}\), a następnie pokazujemy, że jeśli dla pewnego \(\displaystyle{ n\in \NN}\) prawdziwe są \(\displaystyle{ T(n-2)}\) i \(\displaystyle{ T(n-3)}\), to prawdziwe jest także \(\displaystyle{ T(n)}\).
\(\displaystyle{ T(0)}\) wygląda tak: \(\displaystyle{ a_0 \ge \left( \frac 3 2\right)^0}\), po wstawieniu za \(\displaystyle{ a_0}\) z danych mamy prawdziwą zależność \(\displaystyle{ 1\ge 1}\). Podobnie sprawdzamy \(\displaystyle{ T(1)}\) oraz \(\displaystyle{ T(2)}\). Krok indukcyjny: jeśli dla pewnego \(\displaystyle{ n \in \NN, \ n\ge 3}\)
zachodzi \(\displaystyle{ a_{n-2}\ge \left( \frac 3 2\right)^{n-2}}\) oraz \(\displaystyle{ a_{n-3}\ge \left( \frac 3 2\right)^{n-3}}\), to z zależności rekurencyjnej mamy
\(\displaystyle{ a_n=a_{n-2}+2a_{n-3}\ge \left( \frac 3 2\right)^{n-2}+2 \left( \frac 3 2\right)^{n-3}=\left( \frac 3 2\right)^{n-3}\left( \frac 3 2+2\right) =\\=\frac 7 2 \cdot \left( \frac 3 2\right)^{n-3}>\frac{27}{8}\cdot \left( \frac 3 2\right)^{n-3}=\left( \frac 3 2\right)^n.}\)

hmm wygląda to logicznie i dość prosto, tylko nie mogę sobie w głowie poukładać dlaczego to się tak robi?
mógłbyś wytłumaczyć dlaczego właśnie tak?
zawsze indukcyjnie dowodziłem inaczej tj. Sprawdzałem czy dla jakiegoś \(\displaystyle{ n \ge 1}\) zdanie jest prawdziwe, a potem dla \(\displaystyle{ n+1}\). tu jest inaczej. Dlaczego?

kamilm758 pisze:zawsze indukcyjnie dowodziłem inaczej tj. Sprawdzałem czy dla jakiegoś \(\displaystyle{ n \ge 1}\) zdanie jest prawdziwe, a potem dla \(\displaystyle{ n+1}\).

Jeżeli tak robiłeś, to niedobrze, bo to niepoprawne podejście. Dowód tzw. kroku indukcyjnego (w podstawowej wersji indukcji matematycznej) polega na tym, że dla dowolnie ustalonego \(\displaystyle{ n\in\NN}\) ZAKŁADASZ (a nie sprawdzasz!), że warunek zachodzi i starasz się uzasadnić, że z tego założenia wynika, iż warunek ten zachodzi także dla \(\displaystyle{ n+1}\).

kamilm758 pisze:tu jest inaczej. Dlaczego?

Bo akurat w tym dowodzie potrzebny jest inny schemat indukcji - taki, który opisał Ci Premislav. "Zwykły" schemat po prostu nie wystarcza.

Problem z zastosowaniem indukcji polega na ogół na tym, że osoby, które ją stosują, nie rozumieją, na czym ona polega - znają tylko algorytm, który aplikują. Gdybyś rozumiał istotę zasady indukcji matematycznej, to nie dziwiłaby Cię ta inna jej wersja.

JK

chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
\(\displaystyle{ n=1}\)
Później zakładam że zachodzi dla jakiegoś \(\displaystyle{ n \ge 1}\) i to powinno implikować że zachodzi także dla \(\displaystyle{ n+1}\).

A mógłbyś wytłumaczyć dlaczego w schemacie Premislava jest inaczej? nie chciałbym uczyć się na pamięć, tylko zrozumieć to. może jakiś filmik lub prezentację? lub czy mógłbyś wytłumaczyć tu na forum.

W schemacie Premislava jest inaczej, bo potrzeby dowodowe są inne. Definicja rekurencyjna ciągu odwołuje się nie do wyrazu poprzedniego (wtedy wystarczyłaby "zwykła" indukcja), tylko do wyrazów o numerach mniejszych o dwa i trzy. Nic dziwnego zatem, że i schemat indukcji potrzebujemy inny.

Ważniejsze jest zrozumienie, jak indukcja działa. Wyobraź sobie rząd kostek domina (nieskończenie wielu), ustawionych jedna za drugą. Jak (bez testowania) zapewnić, by wszystkie kostki wywróciły się? Trzeba je "dobrze" ustawić, czyli tak, by upadek poprzedniej powodował upadek następnej. Jak już będziemy to mieli zapewnione, to wystarczy wywrócić pierwszą kostkę.

Sprawdzanie założeń zasady indukcji matematycznej odpowiada dokładnie powyższemu schematowi. To co piszesz

kamilm758 pisze:Później zakładam że zachodzi dla jakiegoś \(\displaystyle{ n \ge 1}\) i to powinno implikować że zachodzi także dla \(\displaystyle{ n+1}\).

to sprawdzenie, że upadek kostki \(\displaystyle{ n}\) implikuje upadek kostki \(\displaystyle{ n+1}\), a sprawdzenie warunku początkowego to popchnięcie pierwszej kostki. Jak się to zrozumie, to można modyfikować (wedle potrzeb) warunek "dobrego ustawienia" kostek. Można np. oczekiwać, że do wywrócenia danej kostki niezbędne będzie wywrócenie dwóch poprzedzających ją kostek (wtedy dla ustalonego \(\displaystyle{ n\in\NN}\) zakładasz prawdziwość warunku dla \(\displaystyle{ n}\) i \(\displaystyle{ n+1}\) i pokazujesz, że implikuje to prawdziwość warunku dla \(\displaystyle{ n+2}\)). Trzeba tylko pamiętać, że to może zmienić warunki początkowe, które trzeba sprawdzić - we wspomnianym przed chwilą wariancie trzeba sprawdzić warunek nie tylko dla \(\displaystyle{ n=1}\), ale też dla \(\displaystyle{ n=2}\), bo dopiero te dwie kostki razem będą w stanie wywrócić kostkę nr \(\displaystyle{ 3}\).

Takich modyfikacji można wymyślać bardzo dużo - jedną z nich jest ta zaproponowana przez Premislava. Jak jej się dobrze przyjrzysz, to zobaczysz, że idealnie pasuje to rozpatrywanego zadania. Na Twoim poziomie raczej nikt nie oczekuje, byś dowodził poprawności takiego schematu (choć można to oczywiście zrobić) - ważniejsze jest byś rozumiał, że jest to schemat poprawny (tzn. "działający" - wszystkie kostki wywrócą się).

JK

Wydaje mi się, że lepiej to zrozumieć z tzw. mocnej indukcji. To znaczy, zakładamy, że teza działa dla \(\displaystyle{ 1,...,n}\), a więc w szczególności dla \(\displaystyle{ n-2}\) i \(\displaystyle{ n-3}\) mamy odpowiednio \(\displaystyle{ a_{n-2}\ge \left( \frac 3 2\right)^{n-2}}\) oraz \(\displaystyle{ a_{n-3}\ge \left( \frac 3 2\right)^{n-3}}\). I teraz dopiero \(\displaystyle{ a_n=a_{n-2}+2a_{n-3}\ge ...}\). Oczywiście, jest to to samo, co napisał Premislav, ale, przynajmniej dla mnie, bardziej intuicyjne (to znaczy bardziej intuicyjny jest krok indukcyjny, bo nasze założenie bardziej "pasuje" do tezy).

niunix98 pisze:Wydaje mi się, że lepiej to zrozumieć z tzw. mocnej indukcji. To znaczy, zakładamy, że teza działa dla \(\displaystyle{ 1,...,n}\),

Błąd - właśnie założyłeś tezę. W kroku indukcyjnym zajmujesz się \(\displaystyle{ a_n}\), więc jak już, to zakładasz prawdziwość tezy dla \(\displaystyle{ \red 0,\black 1,...,\red n-1}\). Problem polega na tym, że to nie jest wystarczające założenie (trzeba jeszcze powiedzieć, dla jakich \(\displaystyle{ n}\) tak zakładasz), co powoduje, że Twój dowód nie jest poprawny.

niunix98 pisze:a więc w szczególności dla \(\displaystyle{ n-2}\) i \(\displaystyle{ n-3}\) mamy odpowiednio \(\displaystyle{ a_{n-2}\ge \left( \frac 3 2\right)^{n-2}}\) oraz \(\displaystyle{ a_{n-3}\ge \left( \frac 3 2\right)^{n-3}}\). I teraz dopiero \(\displaystyle{ a_n=a_{n-2}+2a_{n-3}\ge ...}\). Oczywiście, jest to to samo, co napisał Premislav, ale, przynajmniej dla mnie, bardziej intuicyjne (to znaczy bardziej intuicyjny jest krok indukcyjny, bo nasze założenie bardziej "pasuje" do tezy).

Problem polega na tym, że wcale nie pasuje lepiej. Dowód Premislava korzystał dokładnie z takiej indukcji, jaka była potrzebna w tym zadaniu i był dodatkowo poprawny. Twój nie jest poprawny ze względu na niefrasobliwość w używaniu indeksów. Skoro piszesz o \(\displaystyle{ a_{n-2}}\) i \(\displaystyle{ a_{n-3}}\), to musisz zapewnić, że używane przez Ciebie \(\displaystyle{ n}\) jest \(\displaystyle{ \ge 3}\), a tego nigdzie nie zrobiłeś (no i oczywiście sprawdzić \(\displaystyle{ T(0), T(1)}\) i \(\displaystyle{ T(2)}\)).

Używanie "mocnej indukcji" niczego nie uprasza, a zaciemnia obraz rzeczy, przez co łatwiej popełnić błąd, tak jak Ty to zrobiłeś. A koniec końców co byś nie robił, i tak musisz zrobić to, co zrobił Premislav...

JK

Jan Kraszewski pisze: Błąd - właśnie założyłeś tezę. W kroku indukcyjnym zajmujesz się \(\displaystyle{ a_n}\), więc jak już, to zakładasz prawdziwość tezy dla \(\displaystyle{ \red 0,\black 1,...,\red n-1}\).

Faktycznie, napisałem \(\displaystyle{ ..., n}\) zamiast \(\displaystyle{ ..., n-1}\), ale nie to miałem na myśli.

EDIT:

kamilm758 pisze:Trzeba udowodnić tą nierówność:

\(\displaystyle{ a_n \ge \left( \frac{3}{2} \right) ^n}\) dla \(\displaystyle{ n \ge 1}\)

Ze słów autora posta wnioskuję, że mamy sprawdzić prawdziwość zdań \(\displaystyle{ T(n)}\) dla \(\displaystyle{ n \ge 1}\), dlatego też nie pisałem \(\displaystyle{ 0,...}\) ale \(\displaystyle{ 1,...}\). Czy to błąd?

Jan Kraszewski pisze:Problem polega na tym, że to nie jest wystarczające założenie (trzeba jeszcze powiedzieć, dla jakich \(\displaystyle{ n}\) tak zakładasz), co powoduje, że Twój dowód nie jest poprawny.

Dla pewnego \(\displaystyle{ n}\) naturalnego. Wydało to mi się oczywiste...

Jan Kraszewski pisze:

niunix98 pisze:a więc w szczególności dla \(\displaystyle{ n-2}\) i \(\displaystyle{ n-3}\) mamy odpowiednio \(\displaystyle{ a_{n-2}\ge \left( \frac 3 2\right)^{n-2}}\) oraz \(\displaystyle{ a_{n-3}\ge \left( \frac 3 2\right)^{n-3}}\). I teraz dopiero \(\displaystyle{ a_n=a_{n-2}+2a_{n-3}\ge ...}\). Oczywiście, jest to to samo, co napisał Premislav, ale, przynajmniej dla mnie, bardziej intuicyjne (to znaczy bardziej intuicyjny jest krok indukcyjny, bo nasze założenie bardziej "pasuje" do tezy).

Problem polega na tym, że wcale nie pasuje lepiej. Dowód Premislava korzystał dokładnie z takiej indukcji, jaka była potrzebna w tym zadaniu i był dodatkowo poprawny. Twój nie jest poprawny ze względu na niefrasobliwość w używaniu indeksów. Skoro piszesz o \(\displaystyle{ a_{n-2}}\) i \(\displaystyle{ a_{n-3}}\), to musisz zapewnić, że używane przez Ciebie \(\displaystyle{ n}\) jest \(\displaystyle{ \ge 3}\), a tego nigdzie nie zrobiłeś (no i oczywiście sprawdzić \(\displaystyle{ T(0), T(1)}\) i \(\displaystyle{ T(2)}\)).

Używanie "mocnej indukcji" niczego nie uprasza, a zaciemnia obraz rzeczy, przez co łatwiej popełnić błąd, tak jak Ty to zrobiłeś. A koniec końców co byś nie robił, i tak musisz zrobić to, co zrobił Premislav...

JK

Sam napisałem, że zrobiłem dokładnie to samo, co Premislav, ale zaznaczyłem, że zrobiłem to tylko dlatego, że dla autora postu niezrozumiały był krok indukcyjny (według mnie też nieintuicyjny jest krok \(\displaystyle{ (T(n-3) \wedge T(n-2)) \Rightarrow T(n)}\), gdy korzystamy ze "zwykłej" indukcji, w której przyzwyczajeni jesteśmy do robienia kroku indukcyjnego \(\displaystyle{ T(n) \Rightarrow T(n+1)}\). Dlatego też nie zwróciłem uwagi na sprawdzenie podstawy indukcji, której sprawdzenie wydało mi się niewarte uwagi w tej sytuacji, gdyż po prostu przepisałbym słowo w słowo wypowiedź Premislava.

EDIT: zacytuję też słowa autora posta, który napisał:

kamilm758 pisze:chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
\(\displaystyle{ n=1}\)
Później zakładam że zachodzi dla jakiegoś \(\displaystyle{ n \ge 1}\) i to powinno implikować że zachodzi także dla \(\displaystyle{ n+1}\).

A mógłbyś wytłumaczyć dlaczego w schemacie Premislava jest inaczej?

.
Tak jak wcześniej napisałem, to był właśnie powód, dla którego zaproponowałem skorzystanie z tzw. "mocnej" indukcji.

niunix98 pisze:Dla pewnego \(\displaystyle{ n}\) naturalnego. Wydało to mi się oczywiste...

Problem polega na tym, że rozumowanie, które wykonujesz później w oparciu o to założenie działa tylko dla \(\displaystyle{ n\ge 3}\) i trzeba to wyraźnie zaznaczyć. Zatem nie "dla pewnego \(\displaystyle{ n}\)", tylko "dla dowolnie ustalonego \(\displaystyle{ n\ge 3}\)" (słowo "pewne" sugeruje kwantyfikator egzystencjalny, lepiej go nie używać).

Warto też wspomnieć, że już definicja ciągu podana przez kamilm758

kamilm758 pisze:\(\displaystyle{ a_0=1,a_1=2,a_2=3 \\ a_n=a_{n-2}+2a_{n-3}}\)

nie jest dokładna, bo dokładnie powinno być

\(\displaystyle{ a_0=1,a_1=2,a_2=3 \\ a_n=a_{n-2}+2a_{n-3}\mbox{ dla }n\ge 3}\)

niunix98 pisze:Sam napisałem, że zrobiłem dokładnie to samo, co Premislav, ale zaznaczyłem, że zrobiłem to tylko dlatego, że dla autora postu niezrozumiały był krok indukcyjny (według mnie też nieintuicyjny jest krok \(\displaystyle{ (T(n-3) \wedge T(n-2)) \Rightarrow T(n)}\), gdy korzystamy ze "zwykłej" indukcji, w której przyzwyczajeni jesteśmy do robienia kroku indukcyjnego \(\displaystyle{ T(n) \Rightarrow T(n+1)}\).

Ale to, co zrobiłeś, jest niedokładne. Napisałeś "zakładamy, że teza działa dla \(\displaystyle{ 1,...,n-1}\), a więc w szczególności dla \(\displaystyle{ n-2}\) i \(\displaystyle{ n-3}\)", co wobec Twego zastrzeżenia, że "Dla pewnego \(\displaystyle{ n}\) naturalnego. Wydało to mi się oczywiste..." staje się oczywistą nieprawdą. I właśnie dlatego nie warto używać "mocnej indukcji", bo łatwo przeoczyć pewne szczegóły, które sprawią, że dowód przestanie być poprawny.

niunix98 pisze:Dlatego też nie zwróciłem uwagi na sprawdzenie podstawy indukcji, której sprawdzenie wydało mi się niewarte uwagi w tej sytuacji, gdyż po prostu przepisałbym słowo w słowo wypowiedź Premislava.

W sensie zawartości merytorycznej i tak ją przepisałeś, a akurat w tym dowodzie krok pierwszy jest bardzo ważny, bo łatwo wykonać go niepoprawnie.

niunix98 pisze:EDIT: zacytuję też słowa autora posta, który napisał:

kamilm758 pisze:chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
\(\displaystyle{ n=1}\)
Później zakładam że zachodzi dla jakiegoś \(\displaystyle{ n \ge 1}\) i to powinno implikować że zachodzi także dla \(\displaystyle{ n+1}\).

A mógłbyś wytłumaczyć dlaczego w schemacie Premislava jest inaczej?

Tak jak wcześniej napisałem, to był właśnie powód, dla którego zaproponowałem skorzystanie z tzw. "mocnej" indukcji.

Podejrzewam, że kamilm758 ma dosyć typowo wąskie postrzeganie indukcji matematycznej (czyli takie, jak opisał powyżej). Gdyby rozumiał "mocną indukcję", to nie powinien mieć problemu ze zrozumieniem wersji użytej przez Premislava. Podtrzymuję zatem moje zdanie, że dowód Premislava jest optymalny, a pomysł z "mocną indukcją" nic nie wnosi, a generuje dodatkowe pułapki.

JK

Doszliśmy więc do wniosku, że obie wersje są poprawne, to znaczy poprawnie sformułowana indukcja "zwykła" i "mocna". Zostawmy więc kamilm758 wybór, która wersja jest dla niego bardziej przystępna.

niunix98 pisze:Doszliśmy więc do wniosku, że obie wersje są poprawne, to znaczy poprawnie sformułowana indukcja "zwykła" i "mocna".

Każdy poprawny dowód jest poprawny, z tym że Twojego w wersji poprawnej nie ma, jest tylko pomysł. Porównywać można dopiero wtedy, gdy cały dowód od początku do końca jest poprawnie sformułowany. Nie bardzo też wiem, co to jest indukcja "zwykła" w tym zadaniu, skoro wersja Premislava została uznana raczej za niezwykłą...

Kończąc ten wątek dodam tylko, że od swoich studentów oczekuję umiejętności dokładnego sformułowania wersji zasady indukcji matematycznej, której używają w danym zadaniu. W ten sposób można dobrze sprawdzić, czy ów student dobrze rozumie, na czym polega indukcja, czy raczej używa zaklęć...

JK