Vollständige Induktion Doppelsumme Indizes voneinander abhängig

Question

Text erkannt:

Für \( n \in \mathbb{N} \) sei
\( S(n):=\sum \limits_{k=1}^{n} \sum \limits_{i=1}^{k} 2^{n-k} . \)
Zeigen Sie, dass für alle \( n \in \mathbb{N} \) gilt:
(a) \( S(n)=2^{n+1}-(n+2) \).
(b) \( 2 S(n)+n+1=S(n+1) \).
Hinweis: Schreiben Sie zunächst \( S(n) \) als einen Ausdruck auf, in de zeichen vorkommt.
\( [6+2=8 \text { Punkte }] \)

Aufgabe:

Vollständige Induktion

Problem/Ansatz:

Doppelsumme zu einer Summe umschreiben, allerdings verstehe ich nicht wie. Anscheinend ist der zweite Index vom ersten abhängig, was eine Arte Summe mehrerer geometrischer Reihen erzeugt.

Answer 1

Aloha :)

Die Summanden \((2^{n-k})\) sind vom Laufindex \(i\) der inneren Summe unabhängig. Daher wird in der inneren Summe einfach \(k\)-mal der Wert \((2^{n-k})\) addiert:$$S(n)\coloneqq\sum\limits_{k=1}^n\sum\limits_{i=1}^k2^{n-k}=\sum\limits_{k=1}^nk\cdot2^{n-k}$$

zu a) Mit vollständiger Induktion zeigen wir nun:$$S(n)=2^{n+1}-(n+2)$$

Verankerung bei \(n=1\):$$S(1)=\sum\limits_{k=1}^1k\cdot 2^{n-k}=1\cdot2^{1-1}=1\quad;\quad S(1)=2^{1+1}-(1+2)=4-3=1\quad\checkmark$$

Induktionsschritt von \(n\) auf \((n+1)\):$$S(n+1)=\sum\limits_{k=1}^{(n+1)}k\cdot2^{(n+1)-k}=(n+1)\cdot\underbrace{2^{(n+1)-(n+1)}}_{=2^0=1}+\sum\limits_{k=1}^{n}k\cdot 2^{(n+1)-k}$$$$\phantom{S(n+1)}=(n+1)+2\cdot\underbrace{\sum\limits_{k=1}^nk\cdot2^{n-k}}_{=\pink{S(n)}}\stackrel{\text{(Ind.Vor.)}}{=}(n+1)+2\cdot\left(\pink{2^{n+1}-(n+2)}\right)$$$$\phantom{S(n+1)}=(n+1)+2^{n+2}-2n-4=2^{(n+1)+1}-\left((n+1)+2\right)\quad\checkmark$$

zu b) Hier würde ich beide Ausdrücke vereinfachen, sodass sie offensichtlich gleich sind.$$2S(n)+n+1=2\cdot\left(2^{n+1}-(n+2)\right)+n+1=2^{n+2}-n-3$$$$S(n+1)=2^{(n+1)+1}-((n+1)+2)=2^{n+2}-n-3$$Also gilt:\(\quad 2S(n)+n+1=S(n+1)\)

Answer 2

Es ist

        \(\sum\limits_{i=1}^{k}2^{n-k}=k\cdot 2^{n-k}\)

weil die Summe aus \(k\) Summanden besteht, die alle \(2^{n-k}\) lauten.