Summenindex

09.04.2012, 11:41

bandchef

Summenindex

Hi Leute!

Ich hab hier eine Frage zur geometrischen Reihe:

Es gilt ja: $\begin{eqnarray*} \sum_{k=0}^{i} 2^k = \frac{2^{i+1}-1}{2-1} = 2^{i+1}-1 \end{eqnarray*}$

Wie aber muss ich nun den Term auf der rechten Seite verändern, wenn ich diesen Summenindex habe:

Es gilt: $\begin{eqnarray*} \sum_{k=0}^{i-1} 2^k = ... \end{eqnarray*}$

09.04.2012, 11:44

Cel

Auf diesen Beitrag antworten »

RE: Summenindex
Moin!

Wie das mit der anderen Summe funktioniert? Nun, guck dir mal das Ende der Summe an (i) und was rechts vorkommt: i+1. Offenbar wird diese Zahl, bei der die Summe endet, einfach um 1 erhöht ... Idee!

09.04.2012, 11:47

bandchef

Auf diesen Beitrag antworten »

Danke! Ich denke jetzt ist mir wirklich ein Licht aufgegangen. Sollte es so aussehen:

$\begin{eqnarray*} \sum_{k=0}^{i-1} 2^k = \frac{2^{i+2}-1}{2-1} = 2^{i+2}-1 \end{eqnarray*}$

09.04.2012, 11:49

Cel

Auf diesen Beitrag antworten »

Nee. Du hast jetzt den Index um 3 erhöht: (i-1)+3 = i+2. Nur um 1 erhöhen. Augenzwinkern

09.04.2012, 11:55

bandchef

Auf diesen Beitrag antworten »

Wenn also als Grenze für den Laufindex bei der Summe i-1 steht, dann muss ich bei der Formel den Laufindex der Summe plus 1 rechnen? Wenn jetzt bspw. bei der Summe i-7 steht, dann muss ich bei der Formel den Laufindex der Summe plus 7 rechnen usw?

Stimmt's so: $\begin{eqnarray*} \sum_{k=0}^{i-1} 2^k = \frac{2^{(i-1)+1)}-1}{2-1} = 2^i-1 \end{eqnarray*}$

09.04.2012, 12:01

Cel

Auf diesen Beitrag antworten »

RE: Summenindex

Zitat:

Original von bandchef
Stimmt's so: $\begin{eqnarray*} \sum_{k=0}^{i-1} 2^k = \frac{2^{(i-1)+1)}-1}{2-1} = 2^i-1 \end{eqnarray*}$

Ja.

Zitat:

Original von bandchef
Wenn also als Grenze für den Laufindex bei der Summe i-1 steht, dann muss ich bei der Formel den Laufindex der Summe plus 1 rechnen? Wenn jetzt bspw. bei der Summe i-7 steht, dann muss ich bei der Formel den Laufindex der Summe plus 7 rechnen usw?

Nein. Denn dann würde die Formel von ganz oben ja Quatsch sein. Statt des i setzt du dann $\begin{eqnarray*} \hat i = i-7 \end{eqnarray*}$ ein. Und dann steht dort eben

$\begin{eqnarray*} \sum_{k=0}^{\hat i} 2^k = \frac{2^{\hat i+1}-1}{2-1} = 2^{\hat i+1}-1 = 2^{i-6} - 1 \end{eqnarray*}$

Dabei muss das obere Ende der Summe >=0 sein, sonst haben wir eine leere Summe.

09.04.2012, 12:04

bandchef

Auf diesen Beitrag antworten »

Und wie sieht jetzt dann die rechte Formel aus, wenn ich diese Summe hab:

$\begin{eqnarray*} \sum_{k=0}^{log_2(n)-1} 2^k = 2^{log_2(n)}-1 \end{eqnarray*}$

Stimmt das so?

09.04.2012, 12:05

Cel

Auf diesen Beitrag antworten »

Jo, wenn $\begin{eqnarray*} \log_2(n) \end{eqnarray*}$ eine natürliche Zahl ist, dann schon. Sonst ist diese Summe überhaupt nicht definiert.

09.04.2012, 12:07

bandchef

Auf diesen Beitrag antworten »

n kommt aus den natürlichen Zahlen und ist für alle n größer 1.

09.04.2012, 12:08

Cel

Auf diesen Beitrag antworten »

Ein allgemeines n können wir da nicht einsetzen, oder ist dort noch eine Gaußklammer dabei, die abrundet? Wenn wir jetzt bei einer konkreten Aufgabe sind, dann poste deren Wortlaut, wie immer. Augenzwinkern

09.04.2012, 12:23

bandchef

Auf diesen Beitrag antworten »

Aufgabe: Bestimmen Sie die exakte Schranke für die folgende Rekursionsgleichung von Algorithmen mit Hilfe der Iterationsmethode: $\begin{eqnarray*} T(1)=1; T(n) = 4T(\frac{n}{2})+n, \forall n>1 \end{eqnarray*}$

$\begin{eqnarray*} T(n) = 4T(\frac{n}{2})+n = <br /> 4(4T(\frac{n}{4})+\frac{n}{2})+n =<br /> 4(4(4T(\frac{n}{8})+\frac{n}{4})+\frac{n}{2}+n = 4^iT(\frac{n}{2^i})+\sum_{k=0}^{i-1} 2^k \end{eqnarray*}$

Rekursionsbasis: $\begin{eqnarray*} \frac{n}{2^i}=1 \Rightarrow 2^i =n \Rightarrow i=log_2(n) \end{eqnarray*}$

$\begin{eqnarray*} 4^{log_2(n)}T(\frac{n}{2^{log_2(n)}})+\sum_{k=0}^{log_2(n)-1} 2^k = 4^{log_2(n)}T(\frac{n}{2^{log_2(n)}}) + \frac{2^{log_2(n)-1}}{2-1} = 4^{log_2(n)}T(\frac{n}{2^{log_2(n)}}) + 2^{log_2(n)}-1 = \Theta(2^{log_2(n)}) \end{eqnarray*}$

Bei der Rekursionsbasis bin ich mir nicht sicher ob ich da nicht =2 schreiben hätte müssen, da $\begin{eqnarray*} \forall n > 1 \end{eqnarray*}$ gilt... Stimmt das alles soweit?

09.04.2012, 13:28

Cel

Auf diesen Beitrag antworten »

Puh - da bin ich überfragt. Rekursionen sind nicht so meines, diskrete Mathematik ist länger her und so viel haben wir da nicht gemacht. Mal schauen, wer noch was dazu sagen möchte. Ich bin raus und gebe den Thread frei.

Gewöhne dir am besten an, direkt am Anfang zu schreiben, worum es geht - denn bei den Indizes konnte ich dir noch helfen, hier steige ich aus - dabei wolltest du doch von Anfang an auf die Rekursionen hinaus. Augenzwinkern

09.04.2012, 14:17

bandchef

Auf diesen Beitrag antworten »

Ok! Dennoch danke für deine Hilfe! Du hast mir doch sehr viel weitergeholfen. Ich hoffe, es meldet sich noch jemand zu Wort :-)!

Neue Frage »

Antworten »

Summenindex

Verwandte Themen