Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » log(n) wächst langsamer als sqrt(n) beweisen

log(n) wächst langsamer als sqrt(n) beweisen

Universität / Fachhochschule

Differentiation

Funktionalanalysis

Funktionen

Grenzwerte

Graphentheorie

Differentialtopologie

Mengentheoretische Topologie

Tags: Differentialtopologie, Differentiation, Funktion, Funktionalanalysis, Graphentheorie, Grenzwert, Mengentheoretische Topologie

Probot aktiv_icon

18:16 Uhr, 04.12.2009

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

f (n) = l o g (n)

g (n) = \sqrt{(} n)

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

\forall n, n \in ℕ, n \geq n_{0} : ∣ f (n) ∣ < c * g (n)

Also man muss ein

n_{0}

und ein c finden, wo

\sqrt{(} n)

immer größer als

l o g (n)

ist. Das wäre z.B.

c = 1

und

n_{0} = 1

. Aber wie beweise ich das?

Könntet ihr mir da weiterhelfen?
Danke

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Grenzwert (Mathematischer Grundbegriff)
Regel von l'Hospital (Mathematischer Grundbegriff)
Wichtige Grenzwerte
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Ableiten mit der h-Methode
Einführung Funktionen
Grenzwerte - Linksseitiger/rechtsseitiger Grenzwert an einer Polstelle
Grenzwerte - Verhalten im Unendlichen
Grenzwerte im Unendlichen
e-Funktion

Zu diesem Thema passende Musteraufgaben einblenden

Ableitung an einer Stelle

Wie bestimmt man die Ableitung

f' (x)

einer Funktion

f (x)

an der Stelle

x_{0}

Grenzwert einer Funktion

Wie bestimmt man den Grenzwert einer Funktion?

Grenzwert mit l'Hospital bestimmen

Wie bestimmt man einen Grenzwert mit der Regel von l'Hospital?

Wie bestimmt man einen Grenzwert, bei dem

\frac{0}{0}

oder

\frac{\infty}{\infty}

herauskommt?

Kurvendiskussion einer ganzrationalen Funktion 3. Grades

Wie führt man eine Kurvendiskussion einer ganzrationalen Funktion 3. Grades durch?

Kurvendiskussion einer ganzrationalen Funktion 5. Grades

Wie führt man eine Kurvendiskussion einer ganzrationalen Funktion 5. Grades durch?

arrow30

18:34 Uhr, 04.12.2009

wie wäre mit :

log (\sqrt{n}) < \sqrt{n} \forall n \in ℕ

(kannst du auch beweisen )

Probot aktiv_icon

19:45 Uhr, 04.12.2009

aber dann wäre die aufgabe ja nur für

l o g (\sqrt{(} n))

gezeigt, aber nicht für

l o g (n)

. Sehe ich das falsch?

arrow30

19:47 Uhr, 04.12.2009

achte drauf

\sqrt{n} = n^{\frac{1}{2}}

und

log (n^{a}) = a \cdot log (n)

Probot aktiv_icon

13:05 Uhr, 05.12.2009

Das heißt dann, dass ich beweise, dass

l o g (n) < 2 \sqrt{n}

?
Das c wäre dann 2.
Gibt es für

l o g (\sqrt{(} n)) < \sqrt{(} n)

ein Gesetz oder Satz, mit dem man das beweisen kann?
Bitte beachte, dass der log eine beliebige basis haben kann und dass das Gesetz für

∣ l o g (\sqrt{(} n)) ∣ < \sqrt{(} n)

gelten muss (siehe Aufgabenstellung)

hagman aktiv_icon

13:21 Uhr, 05.12.2009

Übrigens scheint deine angegebene Definition eher

f \in O (g)

statt

f \in o (g)

zu bedeuten

. .

. ?

Probot aktiv_icon

13:32 Uhr, 05.12.2009

Nein, das müsste schon

f \in o (g)

sein:
Definition von

f \in o (g)

\forall c, c \in ℝ, c > 0 : \exists n_{0}, n_{0} \in ℕ : \forall n, n \in ℕ, n \geq n_{0} : ∣ f (n) ∣ < c \cdot g (n)

Das '<' bedeutet ja, dass log(n) kleiner aber nicht gleich schnell, also echt langsamer als sqrt(n) wächst?

arrow30

14:01 Uhr, 05.12.2009

naja

\sqrt{n} < a^{\sqrt{n}} . \forall a > 1

\Leftrightarrow {log}_{a} \sqrt{n} < \sqrt{n} \cdot {log}_{a} (a) = \sqrt{n}

\Leftrightarrow {log}_{a} (n) < 2 \sqrt{n}

Probot aktiv_icon

14:27 Uhr, 05.12.2009

Ok Danke!!
Jetzt habe ich es verstanden.
wenn man für

n_{0}

jetzt eine Zahl größer gleich 1 einsetzt ist die bedingung immer erfüllt, da die Nullstelle von log immer auf 1 ist, egal welche basis.

hagman aktiv_icon

15:02 Uhr, 05.12.2009

Die richtige Definition für

o ()

statt

O ()

ist in der Tat

\forall c > 0 : \exists n_{0} \in ℕ : . .

.
Aber im ersten Post hieß es "indem man *ein*

c

ud ein

n_{0}

...", also

\exists c > 0 : \exists n_{0} \in ℕ : . .

.
Daher kam mein Einwand.

Es ist wegen

ln (n) \geq 0

für

n \in ℕ

| ln (n) | < c \cdot \sqrt{n}

\Leftrightarrow ln (n) < c \cdot \sqrt{n}

\Leftrightarrow n < e x p (c \cdot \sqrt{n})

Wegen

e x p (x) \geq 1 + x

für alle

x \in ℝ

ist auch

e x p (x) = {(e x p (\frac{x}{3}))}^{3} \geq {(1 + \frac{x}{3})}^{3},

was zumindest für

x > 0

wiederum

> 1 + \frac{1}{27} x^{3}

ist (die

\frac{1}{27}

ist übertrieben klein, aber das ist egal)
Somit haben wir

e x p (c \cdot \sqrt{n}) > 1 + \frac{c^{3} \cdot \sqrt{n}}{27} \cdot n

.
Um zu erreichen, dass dies

> n

ist, reicht

n > n_{0}

mit

n_{0} \geq {(\frac{27}{c^{3}})}^{2},

denn dann ist der Vorfaktor

> 1

.
Somit

\forall c > 0 : E n_{0} \in ℕ : \forall n > n_{0} : | ln (n) | < c \cdot \sqrt{n}

Probot aktiv_icon

15:31 Uhr, 05.12.2009

@arrow30
ich habe mir nochmals deine Angabe

\sqrt{(} n) < a^{\sqrt{n}}

angeschaut. Dort definiertst du, dass die Basis a > 1 sein muss. Dann ist aber die Basis nicht mehr beliebig. Und für a<1 ist die aussage nicht mehr ganz korrekt.

@hagman
Wie kommst du auf folgende ungleichung

(1 + \frac{x}{3})^{3} > 1 + \frac{1}{27} x^{3}

Du hast die Angaben nur für den ln gemacht, aber nicht für einen logarithmus mit beliebiger basis

hagman aktiv_icon

18:13 Uhr, 05.12.2009

{(1 + \frac{x}{3})}^{3} = 1 + 3 \cdot \frac{x}{3} + 3 \cdot {(\frac{x}{3})}^{2} + {(\frac{x}{3})}^{3}

> 1 + {(\frac{x}{3})}^{3}

falls

x > 0

= 1 + \frac{1}{27} x^{3}

Da der Logarithmus zu einer anderen Basis lediglichein Vielfaches des natürlichen Logarithmus ist, ändert sich nichts, da

o (g)

ein Vektorraum ist. Insbesondere: Für

a \in ℝ \ {0}

gilt

f \in o (g) \Leftrightarrow a \cdot f \in o (g)

Probot aktiv_icon

12:42 Uhr, 06.12.2009

Aber wenn ich eine andere Basis wähle, verschiebt sich ja auch das

n_{0}

? Ist die formel trotzdem korrekt?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

691379

690747

	Status: nicht eingeloggt	Noch nicht registriert?