szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 18:20 
Użytkownik
Avatar użytkownika

Posty: 154
Lokalizacja: Białystok
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ść:

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

Trzeba udowodnić tą nierówność:

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


wiem jak wyliczyć wyrazy, ale jak udowodnić nierówność?
pewnie trzeba znaleźć jawny wzór na a_n, zamiast rekurencyjny. jak to zrobić?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 18:41 
Użytkownik

Posty: 15037
Lokalizacja: Bydgoszcz
Zrób to indukcyjne.
Wskazówka : 56>54
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 18:42 
Użytkownik

Posty: 12305
Lokalizacja: Presslaw
*Tę nierówność.

Nie trzeba wcale znajdować wzoru jawnego (choć można), wystarczy indukcja o następującym schemacie: najpierw sprawdzamy prawdziwość T(0), \ T(1), \ T(2), a następnie pokazujemy, że jeśli dla pewnego n\in \NN prawdziwe są T(n-2) i T(n-3), to prawdziwe jest także T(n).
T(0) wygląda tak: a_0 \ge \left( \frac 3 2\right)^0, po wstawieniu za a_0 z danych mamy prawdziwą zależność 1\ge 1. Podobnie sprawdzamy T(1) oraz T(2). Krok indukcyjny: jeśli dla pewnego n \in \NN, \ n\ge 3
zachodzi a_{n-2}\ge \left( \frac 3 2\right)^{n-2} oraz a_{n-3}\ge \left( \frac 3 2\right)^{n-3}, to z zależności rekurencyjnej mamy
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.
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 19:03 
Użytkownik
Avatar użytkownika

Posty: 154
Lokalizacja: Białystok
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ś n \ge 1 zdanie jest prawdziwe, a potem dla n+1. tu jest inaczej. Dlaczego?
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 19:10 
Administrator

Posty: 22534
Lokalizacja: Wrocław
kamilm758 napisał(a):
zawsze indukcyjnie dowodziłem inaczej tj. Sprawdzałem czy dla jakiegoś n \ge 1 zdanie jest prawdziwe, a potem dla 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 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 n+1.

kamilm758 napisał(a):
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
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 19:17 
Użytkownik
Avatar użytkownika

Posty: 154
Lokalizacja: Białystok
chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
n=1
Później zakładam że zachodzi dla jakiegoś n \ge 1 i to powinno implikować że zachodzi także dla 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.
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2018, o 19:45 
Administrator

Posty: 22534
Lokalizacja: Wrocław
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 napisał(a):
Później zakładam że zachodzi dla jakiegoś n \ge 1 i to powinno implikować że zachodzi także dla n+1.

to sprawdzenie, że upadek kostki n implikuje upadek kostki 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 n\in\NN zakładasz prawdziwość warunku dla n i n+1 i pokazujesz, że implikuje to prawdziwość warunku dla 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 n=1, ale też dla n=2, bo dopiero te dwie kostki razem będą w stanie wywrócić kostkę nr 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
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2018, o 11:29 
Użytkownik
Avatar użytkownika

Posty: 24
Lokalizacja: Warszawa
Wydaje mi się, że lepiej to zrozumieć z tzw. mocnej indukcji. To znaczy, zakładamy, że teza działa dla 1,...,n, a więc w szczególności dla n-2 i n-3 mamy odpowiednio a_{n-2}\ge \left( \frac 3 2\right)^{n-2} oraz a_{n-3}\ge \left( \frac 3 2\right)^{n-3}. I teraz dopiero 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).
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2018, o 15:46 
Administrator

Posty: 22534
Lokalizacja: Wrocław
niunix98 napisał(a):
Wydaje mi się, że lepiej to zrozumieć z tzw. mocnej indukcji. To znaczy, zakładamy, że teza działa dla 1,...,n,

Błąd - właśnie założyłeś tezę. W kroku indukcyjnym zajmujesz się a_n, więc jak już, to zakładasz prawdziwość tezy dla \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 n tak zakładasz), co powoduje, że Twój dowód nie jest poprawny.

niunix98 napisał(a):
a więc w szczególności dla n-2 i n-3 mamy odpowiednio a_{n-2}\ge \left( \frac 3 2\right)^{n-2} oraz a_{n-3}\ge \left( \frac 3 2\right)^{n-3}. I teraz dopiero 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 a_{n-2} i a_{n-3}, to musisz zapewnić, że używane przez Ciebie n jest \ge 3, a tego nigdzie nie zrobiłeś (no i oczywiście sprawdzić T(0), T(1) i 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
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2018, o 16:39 
Użytkownik
Avatar użytkownika

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


Faktycznie, napisałem ..., n zamiast ..., n-1, ale nie to miałem na myśli.

EDIT:

kamilm758 napisał(a):
Trzeba udowodnić tą nierówność:

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


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

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


Dla pewnego n naturalnego. Wydało to mi się oczywiste...

Jan Kraszewski napisał(a):
niunix98 napisał(a):
a więc w szczególności dla n-2 i n-3 mamy odpowiednio a_{n-2}\ge \left( \frac 3 2\right)^{n-2} oraz a_{n-3}\ge \left( \frac 3 2\right)^{n-3}. I teraz dopiero 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 a_{n-2} i a_{n-3}, to musisz zapewnić, że używane przez Ciebie n jest \ge 3, a tego nigdzie nie zrobiłeś (no i oczywiście sprawdzić T(0), T(1) i 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 (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 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 napisał(a):
chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
n=1
Później zakładam że zachodzi dla jakiegoś n \ge 1 i to powinno implikować że zachodzi także dla 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.
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2018, o 17:24 
Administrator

Posty: 22534
Lokalizacja: Wrocław
niunix98 napisał(a):
Dla pewnego 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 n\ge 3 i trzeba to wyraźnie zaznaczyć. Zatem nie "dla pewnego n", tylko "dla dowolnie ustalonego 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 napisał(a):
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ć

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

niunix98 napisał(a):
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 (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 T(n)  \Rightarrow T(n+1).

Ale to, co zrobiłeś, jest niedokładne. Napisałeś "zakładamy, że teza działa dla 1,...,n-1, a więc w szczególności dla n-2 i n-3", co wobec Twego zastrzeżenia, że "Dla pewnego 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 napisał(a):
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 napisał(a):
EDIT: zacytuję też słowa autora posta, który napisał:
kamilm758 napisał(a):
chodziło mi się sprawdzam czy w ogóle zachodzi dla np:
n=1
Później zakładam że zachodzi dla jakiegoś n \ge 1 i to powinno implikować że zachodzi także dla 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
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2018, o 17:49 
Użytkownik
Avatar użytkownika

Posty: 24
Lokalizacja: Warszawa
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.
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2018, o 18:10 
Administrator

Posty: 22534
Lokalizacja: Wrocław
niunix98 napisał(a):
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
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Udowodnij, że dla n naturalnych zachodzi 100n<2^n+577  m  1
 Udowodnij ze dla kazdego n nalezacego do N.......  Anonymous  2
 Uogólniona nierówność Bernoulliego  Anonymous  10
 Indukcja matematyczna. Udowodnij, że 133|(11^n+1+12^2n-1)  apacz  2
 Udowodnij wzór - zadanie 2  Tys  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl