szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 00:38 
Użytkownik

Posty: 10
Lokalizacja: Wrocław
Witam,


Prosiłbym o pomoc w indukcyjnym dowodzie dla nierówności:

n \cdot 2 ^{n} < 3 ^{n}

To co zrobiłem (i na razie nie daje rezultatu)

1 Krok indukcyjny dla n=1:
1 \cdot 2 ^ {1} < 3 ^ {1}  \Leftrightarrow 2 < 3

2. Założenie, że nierówność n \cdot 2 ^{n} < 3 ^{n} jest prawdziwa
Teza:
(n+1) \cdot 2 ^{n+1} < 3 ^{n+1} \Leftrightarrow \\
(n+1) \cdot 2^{n} \cdot 2 < 3 ^ {n+1}  \Leftrightarrow (z zal. indukcyjnego)\\
(2n+2) \cdot 2^{n} < (2n+2) \cdot 3 ^ {n} \Leftrightarrow \\
I tu problem:
(2n+2) \cdot 3 ^ {n} > 3 ^ {n+1} = 3 ^ {n} \cdot 3

Z góry dziękuję za pomoc.
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 00:53 
Administrator

Posty: 22973
Lokalizacja: Wrocław
_tommy_ napisał(a):
(n+1) \cdot 2^{n} \cdot 2 < 3 ^ {n+1}  \Leftrightarrow (z\ zal.\ indukcyjnego)\\
(2n+2) \cdot 2^{n} < (2n+2) \cdot 3 ^ {n}

Skąd to się wzięło? Bo na pewno nie z założenia indukcyjnego...

Poza tym nie przekształcaj tezy, bo to jest śliskie, tylko zacznij od lewej strony tej nierówności i dojdź do prawej.

JK
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 01:06 
Użytkownik

Posty: 10
Lokalizacja: Wrocław
Witam Pana,

Dziękuję za odpowiedź i proszę o wyrozumiałość. Skąd wziąłem to na co zwrócił Pan uwagę:
prawą stronę przekształcam (mnożę przez (2n+2)) aby wykazać, że po takim przekształceniu będzie ona mniejsza lub równą od indukcyjnego 3^{n+1}
i jak sądziłem to jest prawidłowe postępowanie jeśli wykazałbym, że (2n+2) \cdot 3 ^ {n}  \le 3 \cdot 3 ^ {n} czyli (2n+2) \le 3. To ostatnie rzecz jasna jest nieprawdą dla n naturalnych.
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 01:38 
Administrator

Posty: 22973
Lokalizacja: Wrocław
Postępujesz niepoprawnie. Skoro przekształcasz tezę, to możesz wykonywać tylko przejścia równoważne. Tymczasem Ty wykonałeś przekształcenie, polegające na zastąpieniu 3 przez 2n+2, co po pierwsze nijak nie jest przejściem równoważnym, a po drugie nijak nie wynika z założenia indukcyjnego.

A to przecież proste jest:

(n+1)2^{n+1} =(2n+2)2^n=2\cdot n2^n+2^{n+1}<\mbox{(zał. ind.) }\\
<\red 2\cdot 3^n+2^{n+1}\le 2\cdot 3^n+3^n\black=3\cdot 3^n=3^{n+1},

przy czym czerwona nierówność zachodzi dla n\ge 2. By zatem dowód był kompletny trzeba jeszcze sprawdzić, że nierówność jest prawdziwa dla n=2. Ale jest.

JK
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 12:23 
Użytkownik

Posty: 2287
Lokalizacja: Warszawa
Dowiedzenie tej nierówności bez użycia indukcji jest trywialne: wystarczy zlogarytmować obie jej strony. :)
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 16:14 
Użytkownik

Posty: 10
Lokalizacja: Wrocław
Witam,


Dziękuję za odpowiedzi!
Góra
Mężczyzna Offline
PostNapisane: 4 sty 2015, o 12:52 
Użytkownik
Avatar użytkownika

Posty: 684
Lokalizacja: Wrocław
Jan Kraszewski napisał(a):
(n+1)2^{n+1} =(2n+2)2^n=2\cdot n2^n+2^{n+1}<\mbox{(zał. ind.) }\\
<\red 2\cdot 3^n+2^{n+1}\le 2\cdot 3^n+3^n\black=3\cdot 3^n=3^{n+1},


Według mnie, to przejście 2^{n+1}\le 3^n nie jest oczywiste i nie można tak sobie przejść (chyba że osobno się udowodni, np. przy pomocy indukcji łatwo można udowodnić, ale to niepotrzebna komplikacja).

Takie rozwiązanie wydaje mi się lepsze:
(n+1)2^{n+1} =(2n+2)2^n=2\cdot n2^n+2\cdot2^n<\mbox{(zał. ind.) }\\
<\red 2\cdot 3^n+2\cdot2^n\le 2\cdot 3^n+n2^n\black < 2\cdot 3^n+3^n=3\cdot 3^n=3^{n+1},

Tutaj z tym samym założeniem, co u Ciebie, że czerwona nierówność zachodzi dla n \ge 2.
Góra
Mężczyzna Offline
PostNapisane: 4 sty 2015, o 18:08 
Administrator

Posty: 22973
Lokalizacja: Wrocław
Nie widzę dużej różnicy pomiędzy stwierdzeniem, że 2^{n+1}\le 3^n, a n2^n<3^n. Wg mnie to pierwsze jest prostsze, wynika wprost z tego, że funkcja f(x)=\left( \frac32\right)^x jest rosnąca. Jak chcesz prosto uzasadnić drugą nierówność?

JK
Góra
Mężczyzna Offline
PostNapisane: 4 sty 2015, o 22:31 
Użytkownik
Avatar użytkownika

Posty: 684
Lokalizacja: Wrocław
Pisząc "druga nierówność", masz na myśli to: n2^n<3^n ? To jest przecież założenie indukcyjne. Na tym polega dowód metodą indukcji, żeby zrobić takie przejście. W swoim dowodzie sam korzystałeś z tego przejścia, tylko we wcześniejszym etapie. Ja po prostu użyłem go dwa razy.

A to pierwsze, sam widzisz. Żeby mnie przekonać, że jest proste, posłużyłeś się funkcją rosnącą. Jest proste, ale nie oczywiste. Nie jest to żadne twierdzenie matematyczne, więc nie można stosować takiego przejścia, bez dodatkowego dowodu.

W moim dowodzie można się jedynie próbować przyczepić do przejścia 2\cdot2^n \le n\cdot2^n, ale to akurat wynika z dodatkowego, podanego przeze mnie, założeniu n \ge 2.
Góra
Mężczyzna Offline
PostNapisane: 4 sty 2015, o 23:02 
Administrator

Posty: 22973
Lokalizacja: Wrocław
Bierut napisał(a):
Pisząc "druga nierówność", masz na myśli to: n2^n<3^n ? To jest przecież założenie indukcyjne. Na tym polega dowód metodą indukcji, żeby zrobić takie przejście. W swoim dowodzie sam korzystałeś z tego przejścia, tylko we wcześniejszym etapie. Ja po prostu użyłem go dwa razy. n\cdot2^n[/tex], ale to akurat wynika z dodatkowego, podanego przeze mnie, założeniu n \ge 2.

Masz rację, w tym sensie Twoje rozwiązanie jest istotnie prostsze i bardziej eleganckie. Choć podwójne użycie założenia indukcyjnego nie jest intuicyjne...

JK
Góra
Mężczyzna Offline
PostNapisane: 7 sty 2015, o 03:29 
Użytkownik

Posty: 10
Lokalizacja: Wrocław
Dziękuję obu Panom.

-- 11 sty 2015, o 00:44 --

Witam,


Mam jeszcze wątpliwości co do przedstawionych rozwiazań.
W pierwszym kroku sprawdzam prawdziwość nierówności dla n=1 i faktycznie jest ona poprawna. Przeprowadzone dowody potwierdzają jednak jej prawdziwość dla n \ge 2. Treść zadania (nie podałem jej pełnej) prosi o wykazanie poprawności dla dowolnego n \in N. Czy zatem powyższe rozwiązania są OK?
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2015, o 19:46 
Użytkownik
Avatar użytkownika

Posty: 684
Lokalizacja: Wrocław
_tommy_ napisał(a):
Przeprowadzone dowody potwierdzają jednak jej prawdziwość dla n \ge 2.


Przedstawione dowody potwierdzają, że dla każdej liczby naturalnej się zgadza, a nie tylko dla większej lub równej 2. Pierwszy krok wykonałeś dla n=1 i się zgadzało, więc nie ma wątpliwości, że nierówność jest spełniona dla jedynki. Drugi krok został wykonany dla dowolnego n \ge 2. Czyli z pierwszego i drugiego kroku wynika, że nierówność zachodzi dla każdej możliwej liczby naturalnej. Jedynie co trzeba zrobić dodatkowo, to przy pisaniu kolejnych przejść w dowodzie indukcyjnym należy dopisać dodatkowe założenie, że ten dowód jest poprawny dla n \ge 2.

W tym wypadku nie trzeba robić żadnych dodatkowych sprawdzeń. Jeśli zdarzyłoby się tak, że drugi krok byłby prawdziwy np. dla dla n \ge 5, to wtedy należałoby zrobić dodatkowe sprawdzenie dla n równego 2, 3, 4 podstawiając je do nierówności i patrząc, czy się zgadza.
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2015, o 20:11 
Użytkownik

Posty: 10
Lokalizacja: Wrocław
Dziękuję. Teraz wszystko jasne.
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2015, o 23:58 
Administrator

Posty: 22973
Lokalizacja: Wrocław
Bierut napisał(a):
Pierwszy krok wykonałeś dla n=1 i się zgadzało, więc nie ma wątpliwości, że nierówność jest spełniona dla jedynki. Drugi krok został wykonany dla dowolnego n \ge 2. Czyli z pierwszego i drugiego kroku wynika, że nierówność zachodzi dla każdej możliwej liczby naturalnej.

Nieprawda. Trzeba jeszcze sprawdzić, że jest prawdą dla n=2, inaczej indukcja "nie zadziała".

Bierut napisał(a):
W tym wypadku nie trzeba robić żadnych dodatkowych sprawdzeń. Jeśli zdarzyłoby się tak, że drugi krok byłby prawdziwy np. dla dla n \ge 5, to wtedy należałoby zrobić dodatkowe sprawdzenie dla n równego 2, 3, 4 podstawiając je do nierówności i patrząc, czy się zgadza.

Nieprawda. Trzeba jeszcze sprawdzić dla n=5.

JK
Góra
Mężczyzna Offline
PostNapisane: 12 sty 2015, o 16:07 
Użytkownik

Posty: 454
Lokalizacja: Warszawa
Dla mnie taki zapis jest najprostszy :)

{\green n} \cdot 2^n<3^n \text{ założenie}

(n+1)2^{n+1}<3^{n+1} \text{ teza}

{\green \frac{2}{3} (n+1)} 2^n < 3^n

Zatem dla takich n, dla jakich {\green \frac{2}{3} (n+1) \le n}, \ n \in \NN, teza jest spełniona.

\frac{2}{3} (n+1) \le n

n- \frac{2}{3}  (n+1) \ge 0

n \ge 2

Zatem dla n \ge 2 z prawdziwości naszego założenia wynika prawdziwość naszej tezy. Teraz pokazujemy, że nierówność jest spełniona dla n=1,\ n=2 i gotowe. \blacksquare
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód dla nierówności  azusia  7
 Najmniejsza wspólna wielokrotność-dowód.  hUmanitO  8
 okreslenie znaku nierownosci  arigo  7
 indukcja-dwie nierownosci  Anonymous  1
 Przeprowadź dowód indukcyjny nierówności  Anonymous  15
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl