der etwas andere Induktionsbeweis

Neue Frage »

04.05.2011, 19:32	Rose_xx	Auf diesen Beitrag antworten »
der etwas andere Induktionsbeweis folgende Summe soll auf Korrektheit überprüft werden: für jedes positive k gilt: $\begin{eqnarray} \sum\limits_{i=0}^n i^{k} = O(n^{k+1}) \end{eqnarray}$ ich weiß nicht, ob der Induktionsanfang "stimmt", aber ich schätze mal, dass $\begin{eqnarray} 0^{k} = O(0^{k+1}) = 0 \end{eqnarray}$ ist? dann komme ich mit Induktionsschritt und Einsetzen der Induktionsvoraussetzung genau bis hierhin: $\begin{eqnarray} O(n^{k+1}) + (n+1)^{k} = O((n+1)^{k+1}) \end{eqnarray}$ bin ich ansatzweise richtig oder überseh ich etwas grundlegendes? Dankeeee
04.05.2011, 19:35	Huy	Auf diesen Beitrag antworten »
1. Sollte nicht n > 0 gelten? Für n = 0 kriegst du beim Induktionsanfang eine Division durch 0. 2. Wie kommst du auf die Gleichung beim Induktionsschritt? (aber ja, er ist richtig) MfG
04.05.2011, 19:50	Rose_xx	Auf diesen Beitrag antworten »
für n habe ich keine Angabe, es ist nur "jedes positive k" angegeben. achso, ja, n steht ja eh grundsätzlich für die natürlichen Zahlen. 1 für n wäre dann: $\begin{eqnarray} 1^{k} = 1<br /> und<br /> O(1^{k+1}) = O(1) \end{eqnarray}$ klingt auch richtig. auf die Gleichung komme ich, wenn ich die Summe nicht bis n, sondern bis n+1 gehen lassen und anschließend aufglieder in die Summe von i=0 bis n plus (n+1)^k. Und für die Summe setze ich die Voraussetzung ein. (War das verständlich? Wenn nicht, dann schreibe ich es ausführlich in latex) Aber ab jetzt komme ich kein Stück weiter. ich war schon am überlegen, ob ich überhaupt wirklich das n nehmen muss oder vielleicht doch das k ? Ich habe auch schon an geometrische Reihe, binomischen Lehrsatz etc. gedacht, aber passt ja alles nicht. Ich gehe auch davon aus, dass der Term gar nicht korrekt ist - aber bis jetzt hatte ich nur Induktionsbeweise, die im Endeffekt auch gestimmt haben. Ich weiß gar nicht, wie ich mit einem Induktionsbeweis etwas widerlegen kann. Ob ich da einfach abbrechen und sagen kann: ne, ist falsch? (:
04.05.2011, 20:00	Huy	Auf diesen Beitrag antworten »
Ich verstehe nicht ganz, was du mit O(1^(k+1)) = O(1) aussagen möchtest. Das ist zwar eine richtige Aussage, sagt aber nichts über das zu beweisende aus. Ich mache dir mal ausführlich den Induktionsanfang vor, damit du weisst, wie man das zeigen sollte - den Induktionsschritt solltest du dann selber schaffen. Behauptung: $\begin{eqnarray} \sum_{i=0}^n i^k = \mathcal O(n^{k+1}) \; \forall k > 0 \end{eqnarray}$ Beweis: (Induktion) Für n=1 ist $\begin{eqnarray} \sum_{i=0}^1 i^k = 1 \end{eqnarray}$ und es ist $\begin{eqnarray} \left\| \frac{1}{1} \right\| = 1 < \infty \end{eqnarray}$ , also $\begin{eqnarray} \sum_{i=0}^1 i^k \in \mathcal O(1) \end{eqnarray}$ . [... Induktionsschritt ...] Du musst im Induktionsschritt also einfach wieder $\begin{eqnarray} \limsup_{x \to \infty} \left\| \frac{f(x)}{g(x)} \right\| < \infty \end{eqnarray}$ überprüfen. MfG
04.05.2011, 20:33	Rose_xx	Auf diesen Beitrag antworten »
ah, gut, etwas klarer ist es jetzt auf jeden Fall schonmal! Beim Induktionsbeweis komm ich beim Schritt jedoch trotzdem nicht weiter als wie beim ersten Beitrag. Ich komme zwar auf die die Idee $\begin{eqnarray} (n+1)^{k+1} mit (n+1)^{k} (n+1) \end{eqnarray}$ zu ersetzen, bringt mich aber auch noch nicht so wirklich weiter. Mal was ganz pauschales zum "Rechnen". Kann ich das O "ignorieren" bzw. was muss ich beachten, um mit $\begin{eqnarray} O(n^{k+1}) + (n+1)^{k} = O((n+1)^{k+1}) \end{eqnarray}$ weiterzumachen? theoretisch gesehen würde ich jetzt sonst mit $\begin{eqnarray} \frac {n^{k+1} + (n+1)^{k}} {(n+1)^{k+1}} \end{eqnarray}$ bzw. $\begin{eqnarray} \frac {n^{k+1} + (n+1)^{k}} {(n+1)^{k} * (n+1)} \end{eqnarray}$ weitermachen durch kürzen: $\begin{eqnarray} \frac { \frac {n^{k+1} }{(n+1)^{k}} + 1} {(n+1)} \end{eqnarray}$ was zu: $\begin{eqnarray} \frac {n^{k+1} + 1} {(n+1) \cdot (n+1)^{k}} \end{eqnarray*}$ führen würde.
05.05.2011, 11:21	Rose_xx	Auf diesen Beitrag antworten »
nach oben push weil ich immernoch hartnäckig an der Aufgabe bin
Anzeige

05.05.2011, 14:05	EinGast	Auf diesen Beitrag antworten »
willst du die Aufgabe unbedingt mit Induktion lösen? Man kann einfach die Summe nach oben abschätzen...
05.05.2011, 14:48	Rose_xx	Auf diesen Beitrag antworten »
nene, aber mir ist nichts besseres eingefallen. nach oben einschätzen? also ein c finden, so dass f(n) <= c * g(n)?
05.05.2011, 15:01	Rose_xx	Auf diesen Beitrag antworten »
erneuter Lösungsversuch: $\begin{eqnarray} <br /> f(n) = \sum\limits_{i=0}^n i^{k}<br /> g(n) = n^{k+1}<br /> <br /> f(n) \in O(g(n)) <br /> \end{eqnarray}$ denn mit c = 1 und n0 = 1 gilt: $\begin{eqnarray} <br /> \sum\limits_{i=0}^n i^{k} \leq c \cdot n^{k+1}<br /> \end{eqnarray}$ Rechnung: $\begin{eqnarray} <br /> 0^{k} + 1{k} = 1<br /> 1 \cdot 1^{k+1} = 1<br /> <br /> 1 \leq 1<br /> \end{eqnarray}$ da n0 = 1 sieht man, dass es egal ist, welchen positiven Wert k einnimmt.
05.05.2011, 15:27	EinGast	Auf diesen Beitrag antworten »
ich verstehe nicht, was du gemacht hast. Eine Summe ist kleiner oder gleich wie die Anzahl Summanden mal den grössten Summanden...

Neue Frage »

Antworten »

der etwas andere Induktionsbeweis

Verwandte Themen