Vollständige Induktion mit 2 Variabeln

Question

Aufgabe:

Hallo zusammen. Ich habe solche Aufgabe bekommen:

$$\forall (n, k\in\mathbb{Z}), (n \geq 1, k\geq 0) : \sum_{i = -k}^{n - 1}2^i = 2^n - 2^{-k}$$

Problem/Ansatz:

Das muss man mit der vollständige Induktion beweisen.

Ich weiß nicht wie man es beweist, da es 2 Variabeln gibt.

Vielen Dank im Voraus

Answer 1

Aloha :)

Wir zeigen zuerst durch vollständige Induktion:$$\sum\limits_{i=0}^{N-1}2^i=2^N-1\quad\text{für }N\ge1$$

Verankerung bei \(N=1\):$$\sum\limits_{i=0}^{N-1}2^i=\sum\limits_{i=0}^{1-1}2^i=2^0=1=2^1-1=2^N-1\quad\checkmark$$

Induktionsschritt von \(n\) auf \((n+1)\):$$\sum\limits_{i=0}^{(N+1)-1}\!\!\!2^i=\sum\limits_{i=0}^N2^i=\sum\limits_{i=0}^{N-1}2^i+2^N\stackrel{\text{(Ind.Vor.)}}{=}(2^N-1)+2^N=2\cdot2^N-1=2^{N+1}-1\quad\checkmark$$

Damit folgt die Behauptung aus einer einfachen Indexverschiebung. Mit \(n\ge1\) und \(k\ge0\) ist \(N=n+k\ge1\), sodass wir das gerade gefundene Ergebnis auf \(N=n+k\) anwenden können:$$\sum\limits_{i=-k}^{n-1}2^i=\sum\limits_{i=0}^{(n+k)-1}2^{i-k}=2^{-k}\sum\limits_{i=0}^{(n+k)-1}2^i\stackrel{(N=n+k)}{=}2^{-k}\left(2^{n+k}-1\right)=2^n-2^{-k}$$