Beweis eines Zusammenhangs? < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:32 Do 28.10.2004 | | Autor: | AT-Colt |
Hallo Leute,
im Rahmen meiner Übungsaufgaben habe ich eine relativ einfache Aussage verwendet, die ich leider gar nicht so einfach, oder sagen wir besser gar nicht nachweisen konnte:
[mm] $\left(\summe_{i=0}^{n}(x^i)\right)^2 [/mm] = [mm] \summe_{i=0}^{n}(i+1)x^i [/mm] + O(n+1)$ für alle $n [mm] \in \IN_0$
[/mm]
Hierbei bezeichnet O(n+1) Terme der Ordnung n+1 und höher, die eventuell auftreten und können auch 0 sein.
Ich hatte ursprünglich an einen Beweis mit Induktion gedacht, was aber am gemischten Glied [mm] $2*\summe_{i=0}^{n}x^i*O(n+1) [/mm] = 2*O(n+1) + [mm] 2*\summe_{i=1}^{n}x^i*O(n+1)$ [/mm] scheitert, wenn man den Schritt auf n+1 macht.
Gibt es eine schnelle Möglichkeit, das elegant zu beweisen, oder muss man darauf setzen, dass die anderen Leute soviel Rechenerfahrung haben, dass sie das bestätigen?
greetz
AT-Colt
|
|
| |
|
Hallo Colt,
ich denke, dein Problem besteht darin, dass die Aussage falsch ist.
Nimm mal n=1, dann ist die linke Summe [mm]1+2x+x^2[/mm], die rechte Summe ist [mm]1+2x[/mm].
Die linke Summe ist also immer um [mm]x^2[/mm] größer.
Nehmen wir an, die Differenz der Summe wäre O(2), d.h. eine Konstante c.
Nun gibt es aber zu jeder Zahl ein x, so dass [mm]x^2>c[/mm] und somit ist deine Aussage im allgemeinen falsch.
Für beschränkte x ist deine Gleichung sicher richtig, denn man kann sich ja im Endichen nur um endlich viel verrechnen. 
Kann es sein, dass deine Abschätzung anders aussieht?
Hugo
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:17 Do 28.10.2004 | | Autor: | AT-Colt |
Hallo,
ich glaube, Du hast mich mißverstanden (oder ich habe mich unklar ausgedrückt, das kann auch sein ^^; ).
Ich würde gerne zeigen, dass das Quadrat einer Summe [mm] $\summe_{i=0}^{n}$ [/mm] zunächst einmal die Terme [mm] $(i+1)x^i$ [/mm] enthält, darüber hinaus können aber auch höhere Terme vorkommen, die weiterhin von x abhängen.
Zu Deinem Beispiel und n=1:
[mm] $\left(\summe_{i=0}^{1}x^i\right)^2 [/mm] = 1 + 2x + [mm] x^2 [/mm] = [mm] ((0+1)x^0 [/mm] + [mm] (1+1)x^1) [/mm] + O(1+1) = [mm] \summe_{i=0}^{1}(i+1)x^i [/mm] + O(2)$,
also Terme bis zur Ordnung n, die wie in der Formel aussehen und eventuell ein Restterm in Abhängigkeit von x, der aber mindestens n+1 oder größere Exponenten hat.
Mit anderen Worten: O(n) soll eine Polynomfunktion darstellen, deren kleinster Exponent n ist, nicht aber eine Konstante.
greetz
AT-Colt
|
|
|
| |
|
Hi Colt,
Wenn du andeuten willst, dass noch Terme der Ordnung [mm]x^{n+1} [/mm] dazukommen, dann musst du [mm]O(x^{n+1})[/mm] schreiben.
Dann werd ich mir mal nen Beweis überlegen...
Hugo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:39 Fr 29.10.2004 | | Autor: | AT-Colt |
Sers Hugo,
danke für Deine Gedult...
An der Uni haben wir solche Ordnungssachen auch immer nur mit O({Grad}) bezeichnet, dann war $O(n) = [mm] \summe_{i=n}^{\infty}a_i x^i$
[/mm]
greetz
AT-Colt
|
|
|
| |
|
Hallo nochmal,
das was du beschreiben willst, bezeichnet man mit [mm]\Omega(f(x))[/mm]. Das sind gerade die Funktionen die von gleicher oder höherer Ordnung sind als f(x).
O(f(x)) sind von gleicher oder niedrigerer Ordnung.
Bei deinem Problem musst du doch zeigen, dass für jede Potenz [mm]x^i[/mm] mit [mm]i\le n[/mm]auf der rechten Seite (i+1) Kombinationen im Quadrat links existieren. Im Exponenten läuft es darauf hinaus, dass du zeigst, dass es (i+1) Möglichkeiten gibt, die Zahl i als Summe von genau 2 (wegen dem Quadrat) Zahlen aus [mm]\IN_0[/mm] darzustellen.
Hugo
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:33 Mo 01.11.2004 | | Autor: | Marc |
Hallo AT-Colt,
> [mm]\left(\summe_{i=0}^{n}(x^i)\right)^2 = \summe_{i=0}^{n}(i+1)x^i + O(n+1)[/mm]
> für alle [mm]n \in \IN_0[/mm]
Allgemein gilt doch für das Produkt zweier Potenz-Summen:
[mm] $\left(\summe_{i=1}^{n} a_i*x^i\right)*\left(\summe_{j=1}^{m} b_j*x^j\right)=\summe_{k=0}^{n+m} c_k*x^k$
[/mm]
mit [mm] $c_k=\summe_{l=0}^{k} a_l*b_{k-l}$
[/mm]
Das ist doch nur die Anwendung des Distributivgesetzes: In [mm] c_k [/mm] werden alle Produkte von Potenzen zusammengefasst, die den Grad k ergeben.
In deinem speziellen Fall ist nun [mm] $a_k=b_k=1$ [/mm] für [mm] $k\in\{0,\ldots,n\}$ [/mm] und [mm] $c_k=\summe_{k=0}^{k}1*1=k+1$, [/mm] also ist
[mm] $\left(\summe_{i=0}^{n} x^i\right)^2=\summe_{i=0}^{2n} (i+1)*x^i$
[/mm]
Viele Grüße,
Marc
|
|
|
|
