Landau-Symbole √n ∉ Ω(n) beweisen

Question

Ich bin mir beim folgenden Beweis nicht so ganz sicher, ob er reicht, da mich das Endergebnis verunsichert hat.

Behauptung: $$ \sqrt{n}\notin\Omega(n) $$

Beweis (durch Widerspruch).

$$ \text{Angenommen es gelte }\sqrt{n}\in\Omega(n).\text{ Dann gilt }\exists \ \beta >0 \ \exists \ n_0\in\mathbb{N} \ \forall \ n\geq n_0: \ \sqrt{n}\geq \beta \cdot n\geq 0.\\\text{ Löse nun diese Ungleichung nach n auf:}\\\sqrt{n}\geq \beta \cdot n\geq 0\Rightarrow \sqrt{n}\geq \beta \cdot n\Rightarrow n\geq \beta^2\cdot n^2\Rightarrow \beta^2\cdot n^2-n\leq 0 \stackrel{\beta^2>0}{\Rightarrow }n^2-\frac{1}{\beta^2}\cdot n\leq 0\\[15pt]n_1\leq \frac{1}{2\cdot \beta^2}+\sqrt{\Bigg(\frac{1}{2\cdot \beta^2}\Bigg)^2}=\frac{1}{\beta^2}\\n_2\geq \frac{1}{2\cdot \beta^2}-\sqrt{\Bigg(\frac{1}{2\cdot \beta^2}\Bigg)^2}=0$$

$$ \text{Dann gibt es mit einem beliebigen }\beta>0\text{ also ein }n_0\leq \frac{1}{\beta^2},\text{ sodass für alle }n \leq n_0\\\text{die Ungleichung }\sqrt{n}\geq \beta \cdot n\geq 0\text{ erfüllt ist.}\\\text{Diese Ungleichung muss aber für alle } n \geq n_0 \\\text{erfüllt sein. Das ist ein Widerspruch zur Voraussetzung.}$$

Reicht das?

Answer 1

Hallo

ich seh zwar keinen Fehler, aber dein Weg ist ziemlich schlimm.

eine quadratische Gleichung x^2-ax<0 löst man nicht mit pq Formel. sondern mit x*(x-a)<0  gilt nur wenn einer der Faktoren pos, der andere negativ ist, bei dir x=n> 0 folgt x-a<0, x<a

schneller wärst du mit √n/n>β -> n/n^2>β ->1/n>β

Gruß lul