www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - log(n)< sqrt(n) beweisen
log(n)< sqrt(n) beweisen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

log(n)< sqrt(n) beweisen: Aufgabe
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:30 Fr 04.12.2009
Autor: Probot

Hallo!
Ich benötige eure Hilfe bei der Lösung einer Aufgabe. Ich komme einfach nicht dahinter:

$f(n)= log(n)$
$g(n)= [mm] \sqrt(n)$ [/mm]

Zeige, dass f Element von o(g) (Klein-o-Notation: "f wächst echt langsamer als g, http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c und ein [mm] n_0 [/mm] Element der Nat.Zahlen konstruiert wird, damit folgende Formel gilt:


[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c * g(n)$

Also man muss ein [mm] $n_0$ [/mm] und ein c finden, wo [mm] $\sqrt(n)$ [/mm] immer größer als $log(n)$ ist. Das wäre z.B. $c=1$ und [mm] $n_0=1$. [/mm] Aber wie beweise ich das?


Könntet ihr mir da weiterhelfen?
Danke

PS:
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.onlinemathe.de/forum/logn-w%C3%A4chst-langsamer-als-sqrtn-beweisen

        
Bezug
log(n)< sqrt(n) beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:06 Fr 04.12.2009
Autor: Al-Chwarizmi


> [mm]f(n)= log(n)[/mm]
>  [mm]g(n)= \sqrt(n)[/mm]
>  
> Zeige, dass f Element von o(g) (Klein-o-Notation: "f
> wächst echt langsamer als g,
> http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c
> und ein [mm]n_0[/mm] Element der Nat.Zahlen konstruiert wird, damit
> folgende Formel gilt:
>  
>
> [mm]\forall n, n \in \mathbb{N}, n \geq n_0 : |f(n)| < c * g(n)[/mm]
>  
> Also man muss ein [mm]n_0[/mm] und ein c finden, wo [mm]\sqrt(n)[/mm] immer
> größer als [mm]log(n)[/mm] ist. Das wäre z.B. [mm]c=1[/mm] und [mm]n_0=1[/mm]. Aber
> wie beweise ich das?


Hallo Probot,

Vorbemerkung: ich bin nicht ganz sicher, dass du
das mit dem Landau-Symbol genau verstanden hast !


Um zu zeigen, dass deine obige Ungleichung mit [mm] n_0=1 [/mm]
und c=1 passt, könntest du beispielsweise so vorgehen:

1.) zeige, dass f(n)<g(n) für n=1,2,3,4 (durch
    einfaches Ausrechnen und Vergleichen der Werte)

2.) Betrachte die Funktionen f(x) und g(x) für reelle x.
    Beide sind für alle positiven x differenzierbar.
    Zeige dann, dass f'(x)<g'(x) für alle [mm] x\in\IR [/mm] mit x>4 .
    Daraus lässt sich dann schließen (wenn es ganz strikt
    sein soll, mit Mittelwertsatz), dass f(n)<g(n) auch für
    alle n mit n>4 gelten muss.


LG      Al-Chw.  






Bezug
                
Bezug
log(n)< sqrt(n) beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:05 Fr 04.12.2009
Autor: Probot

Hallo Al-Ch
danke für die schnelle Antwort.

zu 1) Also für n=1,2,3,4 stimmt die Aussage
zu 2) $f'(x) = [mm] \frac{log(e)}{x}$ [/mm]
      $g'(x) = [mm] \frac{1}{2*sqrt(x)}$ [/mm]
      Somit muss folgendes gelten: [mm] $\frac{log(e)}{x}<\frac{1}{2*sqrt(x)}$. [/mm]
      Wie zeigt man das? Wenn ich [mm] $\infty$ [/mm] für x einsetze ergibt sich ja folgendes:
      [mm] $\frac{log(e)}{\infty}<\frac{1}{2*sqrt(\infty)} \equiv \frac{log(e)}{\infty}<\frac{1}{\infty} \equiv [/mm] log(e) < 1$
      Da hier der log eine beliebiege Basis haben kann, kann man dann sagen, dass log(e) immer kleiner als 1 ist?
      
      

Bezug
                        
Bezug
log(n)< sqrt(n) beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:52 Fr 04.12.2009
Autor: Al-Chwarizmi


> Hallo Al-Ch
>  danke für die schnelle Antwort.
>  
> zu 1) Also für n=1,2,3,4 stimmt die Aussage
>  zu 2) [mm]f'(x) = \frac{log(e)}{x}[/mm]
>        [mm]g'(x) = \frac{1}{2*sqrt(x)}[/mm]
>  
>       Somit muss folgendes gelten:
> [mm]\frac{log(e)}{x}<\frac{1}{2*sqrt(x)}[/mm].
>        Wie zeigt man das? Wenn ich [mm]\infty[/mm] für x einsetze
> ergibt sich ja folgendes:
>        [mm]\frac{log(e)}{\infty}<\frac{1}{2*sqrt(\infty)} \equiv \frac{log(e)}{\infty}<\frac{1}{\infty} \equiv log(e) < 1[/mm]
>  
>       Da hier der log eine beliebiege Basis haben kann,
> kann man dann sagen, dass log(e) immer kleiner als 1 ist?


Guten Abend Probot,
      
Ich habe mich darauf gestützt, dass die natürlichen
Logarithmen gemeint sind. Dann ist natürlich log(e)=1 !
Die entstehende Ungleichung

        $\ [mm] \frac{1}{x}<\frac{1}{2*\sqrt{x}}$ [/mm]

lässt sich sehr leicht nach x auflösen.

Trotzdem ist dies nicht das, was in der vorliegenden
Aufgabe verlangt ist. Um zu zeigen dass $\ [mm] f\in [/mm] o(g)$ ,
kannst du zum Beispiel zeigen, dass [mm] $\limes_{x\to\infty}\frac{f(x)}{g(x)}=0$ [/mm]


LG     Al-Chw.

Bezug
                                
Bezug
log(n)< sqrt(n) beweisen: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 21:14 Fr 04.12.2009
Autor: Probot

Aufgabe
Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n,  n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen.

PS: Ich habe jetzt mal die gesamte Aufgabenstellung angegeben!
---------
Das heißt dann, dass ich den Satz von l'Hospital anwenden kann/muss:

Wenn beide Funktionen nach unendlich gehen:

[mm] $\limes_{n\rightarrow\infty}\frac{f(x)}{g(x)} [/mm] = [mm] \limes_{n\rightarrow\infty}\frac{f'(x)}{g'(x)}$ [/mm]

daraus folgt:

[mm] $\limes_{n\rightarrow\infty}\frac{2*log(e)}{sqrt(n)} [/mm] $

Laut definition von l'Hospital ist das dann das selbe wie [mm] $\frac{c}{\infty}$. [/mm] Dies ist dann 0. Somit wäre der limes für gezeigt. Aber ist damit die Aufgabe gelöst?
Wie beweise ich jetzt, dass ich das richtige [mm] $n_0$ [/mm] gewählt habe? Denn wenn ich für [mm] $n_0$ [/mm] z.B. 0 wähle, darf n auch 0 sein $(n [mm] \geq n_0)$. [/mm]

Doch für n=0 stimmt die Aussage $|f(n)| < c [mm] \cdot [/mm] g(n)$ nicht:
$|f(0)| = |log(0)| = [mm] \infty$ [/mm]
$g(0) = sqrt(0) = 0$

Hier ist $|f(n)| > c * g(n) $

Bezug
                                        
Bezug
log(n)< sqrt(n) beweisen: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:20 Di 08.12.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
log(n)< sqrt(n) beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:19 Fr 04.12.2009
Autor: HJKweseleit


> [mm]f(n)= log(n)[/mm]
>  [mm]g(n)= \sqrt(n)[/mm]
>  
> Zeige, dass f Element von o(g) (Klein-o-Notation: "f
> wächst echt langsamer als g,
> http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c
> und ein [mm]n_0[/mm] Element der Nat.Zahlen konstruiert wird, damit
> folgende Formel gilt:
>  
>
> [mm]\forall n, n \in \mathbb{N}, n \geq n_0 : |f(n)| < c * g(n)[/mm]

Die letzte Angabe besagt doch nur, dass der Funktionswert (!) von f kleiner als ein Vielfaches (!) von dem entsprechenden Funktionswert von g bleibt.


Weil gilt: |5 n|<10*n für alle natürlichen Zahlen könnte man nach deiner obigen Definition nun sagen: "5n wächst echt langsamer als n" !???

Es muss wahrscheinlich so heißen:

[mm] \forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm]  
  [mm] \exists [/mm]  c mit [mm] 0\le [/mm] c <1: |f(n+o)-f(n)| < c * |g(n+o)-g(n)|

Bezug
                
Bezug
log(n)< sqrt(n) beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:59 Fr 04.12.2009
Autor: Probot

Die Angabe müsste eigentlich schon korrekt sein.

Hier die Angabe aus dem Aufgabenblatt:
-------------------
Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n,  n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen.

Bezug
                        
Bezug
log(n)< sqrt(n) beweisen: Tipp
Status: (Antwort) fertig Status 
Datum: 23:03 Fr 04.12.2009
Autor: HJKweseleit

Zeige zunächst, dass es zu jedem c ein [mm] n_1 [/mm] gibt, so dass für alle [mm] n>n_1 [/mm] gilt:

[mm] c*\wurzel{n}>\wurzel[4]{n}. [/mm]

Dan ist [mm] c*\wurzel{n}-log(n)>\wurzel[4]{n}-log(n). [/mm] Zeige nun, dass es ein [mm] n_2 [/mm] gibt, so dass der rechte Teil der Ungleichung für alle [mm] n>n_2 [/mm] positiv wird.

Damit ist für alle n, die gleichzeitig größer als [mm] n_1 [/mm] und [mm] n_2 [/mm] sind, c*wurzel{n}>log(n).

Damit hast du nicht direkt einen Wert von [mm] n_0 [/mm] = [mm] max(n_1|n_2) [/mm] angegeben, aber zumindest einige Eigenschaften davon.

(Aus dem ersten Teil folgt z.B. [mm] n_1 [/mm] > [mm] 1/c^4.) [/mm]

Bezug
                                
Bezug
log(n)< sqrt(n) beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:28 Fr 04.12.2009
Autor: Probot

Danke für die Antwort. Aber mir ist nicht ganz klar, wie ich da vorgehen soll.

Wie kommst du auf diese Formel:
$ [mm] c\cdot{}\wurzel{n}>\wurzel[4]{n}. [/mm] $

Wie kann ich für die angegebenen Formeln zeigen, dass für alle [mm] $n>n_1$ [/mm] bzw. [mm] $n>n_2$? [/mm]

Bezug
                                        
Bezug
log(n)< sqrt(n) beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 23:58 Fr 04.12.2009
Autor: HJKweseleit

Ich wollte zunächst das c rauswerfen, da es sehr klein oder sehr groß sein kann. Für [mm] n>1/c^4 [/mm] ist [mm] c^4 [/mm] n > 1 und damit [mm] c^4 n^2 [/mm] > n, somit [mm] c*\wurzel{n} [/mm] > [mm] \wurzel[4]{n}. [/mm]

Jetzt hat man eine Formel unabhängig von c und muss nur noch dasjenige n finden, bei dem [mm] \wurzel[4]{n} [/mm] > log(n) wird. Dabei hängt das n von der Basis des logarithmus ab. Ist dieser z.B. ln, so kann man mit dem Taschenrechner und Ausprobieren bestimmen, dass für n=3 bereits gilt: [mm] \wurzel[4]{3} [/mm] > ln(3).

Das ist zwar auch schon für n=2 erfüllt, aber dabei ist der ln negativ; deswegen sollte man zur Vermeidung von Fallunterscheidungen das n immer größer als die Basis wählen, damit der log positiv wird.

Für log=ln braucht man daher nur das [mm] n_0 [/mm] = max(3 | [mm] 1/c^4) [/mm] zu wählen. Vermutlich tuts auch schon gelegentlich ein kleineres [mm] n_0, [/mm] aber das ist egal. Für c = 1/1000 wählen wir also einfach [mm] n_0 [/mm] = 1 000 000 000 000 und können sicher sein, dass die Bedingung erfüllt ist.

Bezug
                                                
Bezug
log(n)< sqrt(n) beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:25 Sa 05.12.2009
Autor: Probot

Aber die Aussage [mm] $\wurzel[4]{n}>ln(n)$ [/mm] ist bereits für n=6 nicht mehr korrekt, denn da ist der ln größer als die wurzel.

Bezug
                                                        
Bezug
log(n)< sqrt(n) beweisen: Ja, aber...
Status: (Antwort) fertig Status 
Datum: 13:18 So 06.12.2009
Autor: HJKweseleit

Du hast Recht. Aber für n > 6000 ist ln(n) < [mm] \wurzel[4]{n}. [/mm]

Du musst also nachweisen, dass für n> 6000    ln(n) < [mm] \wurzel[4]{n} [/mm] ist.

Für andere Basen kann man dann den Beweis sofort übertragen:

[mm] |log_b(n)|< c*\wurzel{n} \gdw |\bruch{ln(n)}{ln(b)}|< c*\wurzel{n} \gdw [/mm] |ln(n)|< [mm] c*|ln(b)|*\wurzel{n} \gdw [/mm] |ln(n)|< [mm] c_1*\wurzel{n} [/mm]

Wobei [mm] c_1=c*|ln(b)| [/mm] ist.

Du musst also nur noch die rote Zeile beweisen. Dann kannst du sagen:

Für n sowohl >6000 als auch [mm] >1/(c*ln(b))^4 [/mm] gilt die Ungleichung.

Bezug
                                                                
Bezug
log(n)< sqrt(n) beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:14 So 06.12.2009
Autor: dayscott

wie beweist man die rote Zeile denn ?

Bezug
                                                                        
Bezug
log(n)< sqrt(n) beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:58 So 06.12.2009
Autor: HJKweseleit

Es gibt zwei naheliegende Möglichkeiten, die sich beide ähneln:

1. Bilde [mm] f(x)=\wurzel[4]{x}-ln(x) [/mm] und zeige
   a) f(6000)>0
   b) f'(x)>0 für x>6000
   Letzteres bedeutet, dass die Funktion monoton steigt und daher für x>6000
   immer >0 bleiben wird, also [mm] \wurzel[4]{x}>ln(x). [/mm]

2. Bilde f(x) = [mm] \bruch{\wurzel[4]{x}}{ln(x)} [/mm] und zeige
   a) f(6000)>1
   b) f'(x)>0 für x>6000
   Letzteres bedeutet, dass die Funktion monoton steigt und daher für x>6000
   immer >1 bleiben wird, also [mm] \wurzel[4]{x}>ln(x). [/mm]

Bezug
                                                
Bezug
log(n)< sqrt(n) beweisen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:10 So 06.12.2009
Autor: dayscott

der ln ist bei 2 nicht mehr negativ: http://uploadz.eu/images/13onjeqwta6g18g0zfkt.png

Bezug
        
Bezug
log(n)< sqrt(n) beweisen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:16 Fr 04.12.2009
Autor: Probot

Hier noch nachträglich die Aufgabenstellung:

Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n,  n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen.

Bezug
                
Bezug
log(n)< sqrt(n) beweisen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:58 Sa 05.12.2009
Autor: Al-Chwarizmi

Na eben.

Nur schade, dass du nicht gleich von Anfang an
die ganze Aufgabe in ihrem vollen Wortlaut ange-
geben hast ...


LG      Al-Chw.

Bezug
                        
Bezug
log(n)< sqrt(n) beweisen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:19 Sa 05.12.2009
Autor: Probot

Ich dachte mir, ich fasse die Aufgabenstellung etwas zusammen. Aber anscheinend war das ein Fehler von mir. :-(

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de