0 Daumen
405 Aufrufe

Aufgabe:

Hallo zusammen. Ich habe solche Aufgabe bekommen:

(n,kZ),(n1,k0) : i=kn12i=2n2k\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

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Aloha :)

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

Verankerung bei N=1N=1:i=0N12i=i=0112i=20=1=211=2N1\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 nn auf (n+1)(n+1):i=0(N+1)1 ⁣ ⁣ ⁣2i=i=0N2i=i=0N12i+2N=(Ind.Vor.)(2N1)+2N=22N1=2N+11\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 n1n\ge1 und k0k\ge0 ist N=n+k1N=n+k\ge1, sodass wir das gerade gefundene Ergebnis auf N=n+kN=n+k anwenden können:i=kn12i=i=0(n+k)12ik=2ki=0(n+k)12i=(N=n+k)2k(2n+k1)=2n2k\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}

Avatar von 152 k 🚀

Ein anderes Problem?

Stell deine Frage