Summe aus Zweierpotenzen

01.11.2018, 15:04

Summe22

Summe aus Zweierpotenzen

Hallo

Sei N eine natürliche Zahl und $\begin{eqnarray*} X:=\left\{ (m,n) \in \mathbb N_0 \times \mathbb N_0 | m<n\leq N \right\} \end{eqnarray*}$

Zu berechnen ist die Summe $\begin{eqnarray*} S_N=\sum\limits_{(m,n) \in X} 2^{n-m} \end{eqnarray*}$

Mein Ansatz ist wie folgt:

Ich habe mir zunächst die Menge X für ein paar natürliche Zahlen N aufgeschrieben und vermute daher den Zusammenhang:

$\begin{eqnarray*} S_N=\sum\limits_{k=1}^{N} k \cdot 2^{N-k+1}=2^{N+1} \cdot \sum\limits_{k=1}^{N} k \cdot (\frac{1}{2})^k \ ~ \ ~ \ ~ \ ~ (**) \end{eqnarray*}$

Da ich vermute, dass "berechne" hier impliziert, dass ich einen geschlossenen Ausdruck in N erzeugen soll, habe ich mich erinnert, dass ich in vorigen Übungsaufgaben mittels abelscher partieller Summationsformel den Zusammenhang $\begin{eqnarray*} \sum\limits_{k=1}^{N} k \cdot q^{k}=q \cdot \frac{1-q^n}{1-q}-q \cdot \frac{n-1}{1-q}+q \cdot \frac{q-q^n}{(1-q)^2} \end{eqnarray*}$ gezeigt hatte (bei Differentialrechnung sind wir noch nicht).

Mit $\begin{eqnarray*} q=\frac{1}{2} \end{eqnarray*}$ führt das eingesetzt und umgeformt bei mir zu $\begin{eqnarray*} S_N=2^{N+2}-2(N+2) \end{eqnarray*}$

Das passt auch ganz gut zu meinen in der Vorarbeit gewählten Beispielen für N=1, N=2, N=3 und N=4.

Müsste ich den obigen Zusammenhang (**) noch z.B. mittels Induktion beweisen, oder reicht es wenn ich es sauber in meinen Beispielen darstelle und markiere, woher meine Vermutung herrührt ?

Habe ich irgendwo falsch/schwammig argumentiert ?

01.11.2018, 15:16

HAL 9000

Auf diesen Beitrag antworten »

Wenn ich direkt rechne $\begin{eqnarray*} S_N = \sum_{n=1}^N \sum_{m=0}^{n-1} 2^{n-m} \end{eqnarray*}$ , und da erst die innere m-Summe, und anschließend die äußere n-Summe auswerte, dann benötige ich eigentlich nur jeweils die geometrische Partialsummenformel $\begin{eqnarray*} \sum_{j=0}^r q^j = \frac{q^{r+1}-1}{q-1} \end{eqnarray*}$ . Insofern ist mir nicht ganz klar, wieso du (**) brauchst. Aber wenn du (**) wirklich brauchst, dann musst du es auch nachweisen, ja.

01.11.2018, 16:43

Summe22

Auf diesen Beitrag antworten »

Ja, das sieht eleganter und direkter aus. Freude

Ich werde deinen Weg später auch austesten.

Nun möchte ich meinen Ansatz noch eben zu Ende führen und bitte um Korrektur.
Da keine Einwände kamen, probiere ich es mal mit Induktion.

Induktionsanfang z.B. mit N=2:

$\begin{eqnarray*} 2^{1-0}+2^{2-0}+2^{2-1}=8=2^{2+2}-2(2+2)=16-8 \ ~ (w) \end{eqnarray*}$

Kommen wir also zum Induktionsschritt $\begin{eqnarray*} S_N \rightarrow S_{N+1} \end{eqnarray*}$

Offenbar kommen mit wachsendem N immer eine bestimmte Anzahl an Zweierpotenzen dazu.
Für die neue Grenze N+1 kommen N+1 neue Potenzen hinzu.
Es gilt also $\begin{eqnarray*} S_{N+1}=S_N+\sum\limits_{k=0}^{N} 2^{k+1}=S_N+2 \cdot (2^{N+1}-1)=2^{N+2}-2(N+2)+2 \cdot (2^{N+1}-1)=2^{N+3}-2N-6 \end{eqnarray*}$

Betrachtet man nun meine Vermutung in (**), so erhält man :

$\begin{eqnarray*} S_{N+1}=2^{N+1+2}-2(N+1+2)=2^{N+3}-2N-6 \end{eqnarray*}$

Passt das ?

01.11.2018, 20:46

Leopold

Auf diesen Beitrag antworten »

Der Induktionsbeweis stimmt. Allerdings verwendest du in seinem Verlauf die Formel für eine geometrische Summe. Und da kannst du ja gleich den von HAL vorgeschlagenen Ansatz verfolgen.

01.11.2018, 22:57

Summe22

Auf diesen Beitrag antworten »

In Ordnung, dann hier noch der Lösungsweg mit der Doppelsumme:

$\begin{eqnarray*} S_N = \sum_{n=1}^N \sum_{m=0}^{n-1} 2^{n-m}= \sum_{n=1}^N 2^n\sum_{m=0}^{n-1} (\frac{1}{2})^{m}= \sum_{n=1}^N 2^n \cdot( 2(1-2^{-n-1})-2^{-n})=\sum_{n=1}^N (2^{n+1}-2)=2 \cdot \sum_{n=1}^N (2^n-1)=2 \cdot (2^{N+1}-1-2^0-N)=2^{N+2}-2 \cdot (N+2) \end{eqnarray*}$

Puh, etwas anstrengend mit dem ganzen Indexrumgespiele - für mich (noch) nicht ganz leicht da den Überblick zu behalten.
Aber gut, dann hab ich das auch mal auf diesem Weg gemacht und was dazu gelernt (Doppelsummen waren noch nicht in der Vorlesung).

Soweit alles passend oder irgendwo unnötig kompliziert umgeformt ?

02.11.2018, 08:31

klarsoweit

Auf diesen Beitrag antworten »

Nun ja, die Umformung $\begin{eqnarray*} \sum_{m=0}^{n-1} (\frac{1}{2})^{m} = 2(1-2^{-n-1})-2^{-n} \end{eqnarray*}$ erscheint mir etwas kompliziert.

02.11.2018, 08:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Summe22
(Doppelsummen waren noch nicht in der Vorlesung).

Ist ja nicht so, dass es dafür einer eigenen Theorie bedarf. Augenzwinkern

02.11.2018, 09:06

Summe22

Auf diesen Beitrag antworten »

Stimmt schon Big Laugh

Kann auf jeden Fall wertvoll sein, wenn mal mehrere Dimensionen im Spiel sind, wie hier beim kartesischen Produkt.
Vielen Dank auf jeden Fall für diesen Ansatz. Freude

@ klarsoweit

Hast du einen Alternativorschlag ? Ich sehe da gerade leider nichts.
Mein Gedanke war halt die Summe in $\begin{eqnarray*} \sum_{m=0}^n ... \ ~ - \ ~ \text{n-tes Glied} \end{eqnarray*}$ aufzusplitten, damit ich die Summenformel benutzen kann, weil dort ja nicht bis n sondern nur bis n-1 aufsummiert wurde.

02.11.2018, 09:13

Leopold

Auf diesen Beitrag antworten »

$\begin{align*} n \end{align*}$ durch $\begin{align*} n-1 \end{align*}$ substituieren.

Neue Frage »

Antworten »

Summe aus Zweierpotenzen

Verwandte Themen