0 Daumen
256 Aufrufe

Ich habe folgenden Beweis zur Behauptung gemacht und wollte wissen, ob er passt. Ich habe keine Idee gehabt, wie ich das direkt beweisen könnte. Zunächst habe ich an Induktion gedacht, indem ich es für alle Grade n zeige. Aber wenn ich nun diese Aussage für ein beliebiges, aber festes n voraussetzen würde und dann auf n+1 schließe, muss ja nichtmehr zwangläufig meine Konstante α>0 aus der Induktionsvoraussetzung aussreichend sein, sowie, dass mein l_0 auch nicht mehr gültig sein muss für Grad n+1. Deshalb dachte ich an einen Widerspruchsbeweis.

$$ \text{Es sei }P(l)=\sum_{k=0}^n a_k\cdot l^k \text{ ein Polynom vom Grad n in der Variablen }l\\\text{mit reellen Koeffizienten }a_k\text{ und } a_n>0. \text{ Dann gilt }(l\mapsto P(l))\in \mathcal{O}(l^n).$$

Beweis (durch Widerspruch.)

$$ \text{Es sei }P(l)=\sum_{k=0}^n a_k\cdot l^k \text{ein Polynom vom Grad n in der Variablen }l\\\text{mit reellen Koeffizienten }a_k\text{ und } a_n>0. \text{ Angenommen es gelte } (l\mapsto P(l))\notin \mathcal{O}(l^n).\\\text{Dann gilt für alle }\alpha >0 \text{ und für alle } l_0\in \mathbb{N},\text{ dass es ein }l\in \mathbb{N} \text{ mit }l\geq l_0 \\\text{gibt, sodass die Abschätzung }0>P(l)>\alpha\cdot l^n\text{ erfüllt ist.}\\\text{Für }l=l_0=0 \text{ ist }0>P(0)=a_0>\alpha\cdot 0^n=0 \text{ bereits ein Widerspruch.}\\\text{Betrachte nun }l\geq l_0>0 \text{ beliebig groß. Dann gilt auch }0>\frac{P(l)}{l^n}>\alpha\text{ bzw.,}\\0>\underbrace{a_0\cdot \frac{l^0}{l^n}+a_1\cdot \frac{l^1}{l^n}+...+a_{n-1}\cdot \frac{l^{n-1}}{l^n}}_{\substack{l \rightarrow \infty \\\longrightarrow 0}}+a_n>\alpha.\\\text{Daraus folgt }0>a_n>\alpha.\text{ Es ist aber }a_n>0\text{ und }\alpha>0,\\\text{was demnach ein Widerspruch zur Voraussetzung ist.}\\\text{Damit folgt die Behauptung.}$$

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community