Zu Zeigen: i^k wächst genauso schnell wie n^(k+1)

08.12.2014, 21:08

loci

Zu Zeigen: i^k wächst genauso schnell wie n^(k+1)

Hallo,

kämpfe gerade mit folgender Aufgabe:

Man soll beweisen, dass

$\begin{eqnarray*} \sum\limits_{i=1}^n i^{k} = \Theta (n^{k+1}) \end{eqnarray*}$ für alle k $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ .

Das ganze ist mit hoher Wahrscheinlichkeit mit vollständiger Induktion zu machen.

Wenn ich aber die Induktionsannahme mache, habe ich dort:

$\begin{eqnarray*} \sum\limits_{i=1}^n i^{k} = \Theta (1^{k+1}) \end{eqnarray*}$ für n=1. Das sieht mir aber schon arg komisch aus und ich weiß damit nicht wirklich etwas anzufangen.

Hat jemand eine Idee wie man das besser aufziehen kann?

Theta heißt ja "wächst genauso schnell wie". Aber das bringt mich nicht so wirklich weiter hier.

08.12.2014, 21:14

URL

Auf diesen Beitrag antworten »

RE: Zu Zeigen: i^k wächst genauso schnell wie n^(k+1)
Kann man da nicht ganz grob $\begin{eqnarray*} i^k\leq n^k \end{eqnarray*}$ abschätzen?

08.12.2014, 21:16

loci

Auf diesen Beitrag antworten »

Hallo und Danke für deine Antwort. Als Tipp haben wir bekommen:

Stur nach Definition Theta zeigen, eine Richtung ist einfach, die Abschätzung nach unten aber schwieriger. Trick beim Abschätzen nach unten: Summanden weglassen um Summe groß zu machen.

Allerdings hilft mir das trotzdem nicht wirklich weiter da ich scheinbar noch nicht mal den Ansatz verstehe. Ich scheitere schon an der Induktionsannahme.

PS: bei deiner Annahme mit der Abschätzung wäre für mich jetzt beides gleich groß, da i zu n wird, da es ja dagegen läuft, oder??

08.12.2014, 21:25

URL

Auf diesen Beitrag antworten »

Meine Abschätzung ist der leichte Teil und beschert dir, dass die Summe $\begin{eqnarray*} \mathcal{O}(n^{k+1}) \end{eqnarray*}$ ist.

08.12.2014, 21:28

HAL 9000

Auf diesen Beitrag antworten »

Tipp: Für $\begin{align*} n=2m \end{align*}$ ist einfach

$\begin{align*} \sum_{i=1}^{2m} i^k \geq \sum_{i=m}^{2m} i^k > \sum_{i=m}^{2m} m^k > m\cdot m^k = m^{k+1} = \frac{n^{k+1}}{2^{k+1}} \end{align*}$

und für ungerade $\begin{align*} n=2m+1 \end{align*}$ geht das so ähnlich. Und mit diesem Weg braucht man gar keine Induktion.

08.12.2014, 21:35

loci

Auf diesen Beitrag antworten »

Ok, ich versuche das gerade mal so zu durchdenken.

D.h. man macht 2 Fälle, einen für die geraden Zahlen wie 2m, und einen Fall für die ungeraden mit 2m+1?

Kann ich das also so anfangen, dass ich auf der linken Seite die geraden Zahlen behandle, auf der rechten die ungeraden, dann sozusagen eine Gleichung aufstelle (gerade Zahlen links, ungerade rechts), und dann so umforme dass auf beiden das gleiche rauskommt? Wobei man das ja auch so bei der Induktion macht. Das man eben beweist, dass beide Seiten identisch sind (oder dass man von der linken auf die rechte Seite kommt, das geht auch).

Für ungerade hätte ich dann als obere Grenze der Summe 2m+1 bzw. setze ich dort für alle m = m+1 ein, oder? Und müsste dann nach Umformung ebenso auf $\begin{eqnarray*} \frac{n^{k+1} }{2^{k+1}} \end{eqnarray*}$ kommen?

Die Induktionsannahme kann ich mir dann ja sparen wenn ich eh nicht mit Induktion löse.

EDIT: Nochmal gemäß Tipp die Theta-Notation bzw. Definition:

$\begin{eqnarray*} \Theta \end{eqnarray*}$ (g(n))={f(n): es existieren 2 Konstanten c1 und c2 größer 0 und ein n0 aus den natürlichen Zahlen, sodass c1 |g(n)| $\begin{eqnarray*} \leq \end{eqnarray*}$ |f(n)| $\begin{eqnarray*} \leq \end{eqnarray*}$ c2|g(n)| für alle n $\begin{eqnarray*} \geq \end{eqnarray*}$ n0}.

08.12.2014, 21:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von loci
Kann ich das also so anfangen, dass ich auf der linken Seite die geraden Zahlen behandle, auf der rechten die ungeraden, dann sozusagen eine Gleichung aufstelle (gerade Zahlen links, ungerade

Da hast du aber meinen Beitrag in den völlig falschen Hals gekriegt. Ich hab die Fallunterscheidung beim oberen Summenindex nur deswegen gemacht, weil ich die obere "Hälfte" der Summe haben will, die Zahl $\begin{align*} \frac{n}{2} \end{align*}$ aber nicht in jedem Fall als Index geeignet ist - nur aus dem Grund. Augenzwinkern

P.S.: Ich schätze mal, wenn ich gleich mit der Gaußklammer $\begin{align*} \left\lfloor \frac{n}{2}\right\rfloor +1 \end{align*}$ als unteren Index angefangen hätte, dann wäre die "Krise" bei dir noch viel schlimmer als jetzt bedauerlicherweise auch schon.

08.12.2014, 21:56

loci

Auf diesen Beitrag antworten »

Ich glaub eher dass ich zuviele Ansätze im Kopf habe.

1. Induktion
2. hatte ich noch überlegt ob man jetzt den Limes rauskramen muss und das so irgendwie beweisen soll,
3. versuche ich mich in die Tipps von dir unten reinzufuchsen mit deiner Summe.

Ich finde die Aufgabe recht schwer. Versuchs aber trotzdem. Ignorieren bringt ja nix. Davon wird mir auch nicht die Erleuchtung kommen.

Mit oberer Hälte der Summe - meinst du da die Abschätzung der Summe nach oben wenn man jetzt n auf theoretisch unendlich setzen würde?

Ich bin auch irgendwie verwirrt dass ich 3 Variablen habe.

i = der Laufindex. n dabei meine obere Grenze. i läuft quasi von 1 bis n, ich nehme mal an, auch wenns da nicht steht, dass n gegen unendlich läuft und aus den natürlichen Zahlen kommt (da ja aufsummiert wird). Dann habe ich auch noch k. da k aus den natürlichen Zahlen kommt, gehe ich jetzt mal von aus dass es ebenso bei 1 beginnt theoretisch. Da war schon mein erstes Problem - HÄTTE ich jetzt Induktion gemacht, hätte ich nicht gewusst, was ich für k generell einsetzen soll.

Irgendwie habe ich da immer noch einen Knoten der nicht platzen will...

08.12.2014, 22:00

HAL 9000

Auf diesen Beitrag antworten »

Sieht das

Zitat:

Original von HAL 9000
$\begin{align*} \sum_{i=1}^{2m} i^k \geq \sum_{i=m}^{2m} i^k~{\color{red}>}~\sum_{i=m}^{2m} m^k~{\color{red}>}~ m\cdot m^k = m^{k+1} = \frac{n^{k+1}}{2^{k+1}} \end{align*}$

nach einer Abschätzung nach oben aus? unglücklich

Eine wirkliche Abschätzung nach oben ist doch noch viel trivialer:

$\begin{align*} \sum_{i=1}^n i^k \leq \sum_{i=1}^n n^k = n\cdot n^k = n^{k+1} \end{align*}$ .

08.12.2014, 22:08

loci

Auf diesen Beitrag antworten »

Super, jetzt ist mein Post weg.

Nein, das ist eine Abschätzung nach unten. Ganz rechts ist quasi das "kleinste".

Die Abschätzung nach oben hat (neben der < -Zeichen) auch den Teiler nicht mehr, muss also größer sein.

Ich muss da mal grad drüber nachdenken, dann platzt der Knoten vielleicht. Find das echt etwas happig.

08.12.2014, 22:19

HAL 9000

Auf diesen Beitrag antworten »

Eigentlich sind das Basisaufgaben, um ein Gefühl für die Landau-Symbole zu entwickeln. Von feinsinnigen Abschätzungen kann keine Rede sein, bisher in deinen beiden Threads reichen da wie gesehen ganz grobe Methoden.

Natürlich könntest du auch einen Induktionsbeweis für

$\begin{align*} \sum_{i=1}^n i^k > \frac{n^{k+1}}{k+1} \end{align*}$

aufziehen, aber das ist m.E. noch viel umständlicher - wenn auch machbar.

08.12.2014, 22:22

loci

Auf diesen Beitrag antworten »

Bekomme in der Tat häufig gesagt dass ich Sachen viel zu umständlich mache, weil ich auch immer denke dass es recht kompliziert sein muss. Und dann wäre es oft einfacher gegangen. Keine Ahnung warum ich immer davon ausgehe, dass so eine Rechnung 4 Seiten min. lang sein muss. Vllt erwarte ich noch zu viel von UniMathe und denke es muss schwer sein, sonst wärs kein Uni-Mathe... verwirrt

Oft schieße ich mir damit aber ins Knie... unglücklich

Neue Frage »

Antworten »

Zu Zeigen: i^k wächst genauso schnell wie n^(k+1)

Verwandte Themen