O-Notation formal Beweisen

Question

ich komme leider bei dieser Aufgabe nicht weiter. Könnte jemand mir helfen oder zumindest einen Ansatz zeigen?

Aufgabe:

$$ \text{Beweisen Sie formal, dass für } f : \mathbb{N}  \rightarrow \mathbb{R} ^{\gt 0}, n \rightarrow (n + 9)^{2} \text{ die Eigenschaft } f\in Ο (n^{2}) \text{ gilt.} $$

Comments

\( \text{Beweisen Sie formal } \dots \)

Ist das das Gegenteil von "Beweisen sie mittels eines Hand-waving-Argumentes"? :-)

Answer 1

Für \(n \geq 18\) gilt \(n^2 \geq 18n\) und \(n^2 \geq 81\).

Für \(n \geq 18\) ist also

        \((n+9)^2 = n^2 + 18n+81\leq n^2 + n^2 + n^2 = 3n^2\).

Comments

Danke dir auf jeden Fall erstmal für die schnelle Antwort. Wie würde man diesen Ansatz noch als mathematisch korrekten Beweis verfassen? Haben Beweise erst vor kurzem gemacht, deswegen bin ich da noch ein bisschen Ahnunglos :D

---

Das ist ein mathematisch korrekter Beweis.

Was du noch machen könntest ist, darzulegen, warum die Ungleichungen \(n^2 \geq 18n\) und \(n^2 \geq 81\) gültig sind und wie die Ungleichung \((n+9)^2 \leq 3n^2\) zu der Definition on \(O(n^2)\) passt, was also in

        \(f\in O(g) \iff \exists N\in\mathbb{N}, c>0 \forall n\geq N: \left|f(n)\right|\leq c\cdot \left|g(n)\right|\)

das \(N\) und das \(c\) ist.