Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweisen oder Gegenbeispiel
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Beweisen oder Gegenbeispiel
 
Autor Nachricht
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 02 Jun 2006 - 22:15:04    Titel: Beweisen oder Gegenbeispiel

Hallo zusammen,

Sei k,n natürliche Zahnlen mit 2 <= k <= n. Beweisen oder widerlegen:

* Es gibt eine Konstante c, damit folgende Ungeleichung erfüllt ist:

k^2 log n <= c*n^2 log k
take
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 03.11.2005
Beiträge: 1018

BeitragVerfasst am: 03 Jun 2006 - 07:24:56    Titel:

k² * log(n) <= c*n² * log(k)

einfaches Gegenbeispiel:
Sei k = 1 und n > 1 => k² * log(n) > 0, aber c * n² * log(k) = 0 für alle c, da log(k) = 0
=> 1² * log(n) = log(n) > 0 = c * n² * 0 = c*n² log 1
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 03 Jun 2006 - 08:56:05    Titel:

schau mal bitte die Bedingung: 2 <= k !!!!!!!!

take hat folgendes geschrieben:
k² * log(n) <= c*n² * log(k)

einfaches Gegenbeispiel:
Sei k = 1 und n > 1 => k² * log(n) > 0, aber c * n² * log(k) = 0 für alle c, da log(k) = 0
=> 1² * log(n) = log(n) > 0 = c * n² * 0 = c*n² log 1
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 03 Jun 2006 - 09:01:18    Titel:

daxiaoaixad hat folgendes geschrieben:
!!!!!!!!


Evil or Very Mad
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 03 Jun 2006 - 09:58:31    Titel:

fas hat folgendes geschrieben:
daxiaoaixad hat folgendes geschrieben:
!!!!!!!!


Evil or Very Mad


war ich irgendwie ruppig? Habe nicht boeses gemeint, tut mir leid SmileSmileSmile
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 03 Jun 2006 - 11:12:03    Titel:

Hallo !

k^2 log n <= c*n^2 log k

2 <= k <= n , folglich 0 < 2/n <= k/n <= 1

Ungleichung mit 1/(n^2 * log(n)) multiplizieren.

(k/n)^2 <= c*(log(k)/log(n)) = c*(1 + log(k/n)/log(n)) <= c

Da 0 < k/n <= 1 , erfüllt jedes c >= 1 die Ungleichung.
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 03 Jun 2006 - 17:42:28    Titel:

Winni hat folgendes geschrieben:
Hallo !

k^2 log n <= c*n^2 log k

2 <= k <= n , folglich 0 < 2/n <= k/n <= 1

Ungleichung mit 1/(n^2 * log(n)) multiplizieren.

(k/n)^2 <= c*(log(k)/log(n)) = c*(1 + log(k/n)/log(n)) <= c

Da 0 < k/n <= 1 , erfüllt jedes c >= 1 die Ungleichung.


cool...., danke Smile
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 03 Jun 2006 - 20:33:06    Titel:

daxiaoaixad hat folgendes geschrieben:

cool...., danke Smile


Aber wenn man es genau nochmal sieht, ist es leider falsch! Deine Abschatzung sagt doch nix!?
daxiaoaixad
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.02.2006
Beiträge: 20

BeitragVerfasst am: 03 Jun 2006 - 20:38:35    Titel:

Winni hat folgendes geschrieben:
Hallo !

k^2 log n <= c*n^2 log k

2 <= k <= n , folglich 0 < 2/n <= k/n <= 1

Ungleichung mit 1/(n^2 * log(n)) multiplizieren.

(k/n)^2 <= c*(log(k)/log(n)) = c*(1 + log(k/n)/log(n)) <= c

Da 0 < k/n <= 1 , erfüllt jedes c >= 1 die Ungleichung.


jedes c >= 1 erfüllt die Ungleichung:

(k/n)^2 <= c,

aber nicht offensichtlich die originale Ungleichung!
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 03 Jun 2006 - 21:30:49    Titel:

Hast Recht, da war ich zu voreilig.

Die Bedingung ist:
k^2 log n <= c*n^2 log k mit 2 <= k <= n

Setzen wir x:=k/n , so dass 2/n<=x<=1
und -log(n)+log(2) <= log(x) <= 0 .

x² <= c*(1 + log(x)/log(n))
bzw. c >= x²/(1 + log(x)/log(n))

Damit muss c >= Maximum(x²/(1 + log(x)/log(n))
und unabhängig(!) von n sein.

-log(n)+log(2) <= log(x) <= 0
-1+log(2)/log(n) <= log(x)/log(n) <= 0
=> log(2)/log(n) <= 1 + log(x)/log(n) <= 1

=> x²log(n)/log(2) >= x²/(1 + log(x)/log(n)) >= x²

Da x²log(n)/log(2) wegen ln(n) beliebig groß werden kann,
gibt es kein c zur Beschränkung von x²/(1 + log(x)/log(n)),
das unabhängig von n ist.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Beweisen oder Gegenbeispiel
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum