Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Folgen gleiche Laufzeitkomplexität (Big-O)

Folgen gleiche Laufzeitkomplexität (Big-O)

Universität / Fachhochschule

Folgen und Reihen

Tags: Folgen, Folgen und Reihen, Grenzwert, Laufzeitkomplexität, Ungleichung

zeitoptimierer aktiv_icon

15:41 Uhr, 10.06.2023

Gegeben sei

d \in ℕ

. Es gilt zu zeigen, dass

\sum_{i = 1}^{n} i^{d} \equiv_{O} n^{d + 1}

wobei beide als Folgen in

n

zu verstehen sind.

Meine bisherige Lösung sieht wie folgt aus:
Um zu zeigen, dass

\sum_{i = 1}^{n} i^{d} \equiv_{O} n^{d + 1}

, genügt zu zeigen,
dass

\sum_{i = 1}^{n} i^{d} \leq_{O} n^{d + 1}

und

n^{d + 1} \leq_{O} \sum_{i = 1}^{n} i^{d}

.

Es gilt, dass

\sum_{i = 1}^{n} i^{d} \leq \sum_{i = 1}^{n} n^{d} = n \cdot n^{d} = n^{d + 1}

.
Somit ist gezeigt, dass

\sum_{i = 1}^{n} i^{d} \leq_{O} n^{d + 1} .

Leider weiß ich nicht ganz, wie ich nun die zweite Richtung zeigen kann.
Uns wurde zusätzlich mitgeteilt, dass eine genaue Lösung für den Term

\sum_{i = 1}^{n} i^{d}

nicht erwünscht ist.

Über Hilfe bin ich sehr dankbar!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

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

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

Ableiten mit der h-Methode
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