Äquivalenz von Folgen bezüglich O-Ordnung

Question

Aufgabe:

Gegeben sei d in ℕ. Es gilt zu zeigen, dass für die Folgen

g = ∑_{i = 1}ⁿ i^d und $f = n^d+1 gilt, dass g ≡_Ο f

Problem/Ansatz:

Um zu zeigen, dass g ≡Ο f genügt es zu zeigen, dass g ≤_O f und f ≤_O g.

Zeigen wir also zunächst g ≤_O f. Es gilt, dass ∑_{i = 1}ⁿ i^d ≤ ∑_{i = 1}ⁿ n^d = n * n^d = n^d+1

Ich bin mir relativ sicher, dass diese Richtung somit gezeigt worden ist, jedoch habe ich keinen Ansatz für f ≤_O g.

Comments

Das war leider Quatsch!, sorry

---

Habe ich nicht gezeigt, dass g <= f? Es gilt ja nicht, dass ∑_{i = 1}ⁿ i^d = ∑i _{= 1}ⁿ n^d