Zeigen Sie, dass für alle Funktionen ƒ, g : ℕ → ℝ >0 die folgende Äquivalenz gilt

Question

Aufgabe:

Zeigen Sie, dass für alle Funktionen ƒ, g : ℕ → ℝ _>0  die folgende Äquivalenz gilt:

$$ f ( n ) \in \circ ( g ( n ) ) \Leftrightarrow \lim _ { n \rightarrow \infty } \frac { f ( n ) } { g ( n ) } = 0 $$

Der Kreis \( \circ \) steht für Verknüpfung (Komposition) von Funktionen.

Comments

Mir ist nicht klar, wie man die Folge (g(n)) verknüpfen soll, dass f(n) ein Element davon sein soll. Mit sich selbst? f und g haben als Wertebereich R⁺ Der Definitionsbereich ist aber nur N, man kann also nicht jeden Wert aus R einsetzen.

Rechts in der Äquivalenz werden ja einzelne Folgenglieder durcheinander dividiert. 

Answer 1

Da sollte wohl jemand mal wieder zur Vorlesung gehen. ;-)

 

Mit Kompositionen kann das kaum was zu tun haben, zumindest dann nicht, wenn das jetzt die richtige "Aufgabe" ist.

Es handelt sich wahrscheinlich eher um Aussagen der Komplexitätstheorie über das asymptotische Verhalten der Funktionen f und g.

Dann sind das allerdings keine Aufgaben, sondern Definitionen!
Man nennt f gegenüber g bei n gegen Unendlich asymptotisch vernachlässigbar, wenn gilt

lim_n→∞ f(n)/g(n) = 0

und schreibt dann (nach Definition!)

f(n) ∈ o(g(n))

 

Möglich ist natürlich, dass ihr diese sogenannten Landau-Symbole anders definiert habt, zum Beispiel so:

f ∈ o(g) :⇔ ∀ε<0∃n₀∀n>n₀: f(n) ≤ ε*g(n)

Diese Zeile ist äquivalent zu

∀ε<0∃n₀∀n>n₀: f(n)/g(n) ≤ ε

und mit a_n = f(n)/g(n) drückt das gerade die Eigenschaft der Folge (a_n) aus, Nullfolge zu sein.

Das ist aber gerade das, was zu beweise war.