Zeigen Sie die Summenformel

Question

Aufgabe:

Zeigen Sie die Summenformel

1 + 2 + 4 + . . . + 2^n-1= 2ⁿ − 1

für n ∈ N ∖ {0}, indem Sie die Anzahl Möglichkeiten doppelt abzählen, eine Treppe mit n + 1

Stufen zu erklimmen, wobei die Schritte beliebig groß sein können und man am Ende auf Stufe
n + 1 steht.

Problem:

Das ist eine Übungsaufgabe die mir über den Weg gelaufen ist und ich habe keine Ahnung was ich machen muss, kann mir Vorstellen, dass es mega simpel ist. Würd mich freuen wenn mir jemand helfen könnte.

Comments

Hier stand Falsches.

---

Welche 3 Möglichkeiten gibt es denn, eine Treppe mit n+1 = 2 Stufen zu erklimmen ?

---

Nachdem R seinen Beitrag zurückgezogen hat geht der nächste Kommentar an den Fragesteller : Berichtige den (kleinen aber entscheidenden) Fehler in der Aufgabenstellung .

---

In der Aufgabenstellung muss es korrekt heißen wobei die Schritte beliebig aber höchstens n groß sein können und man am Schluss auf Stufe n+1 steht.

Das doppelte Abzählen geht nun folgendermaßen :

Für die rechte Seite
Wenn die Treppe erklommen wird, wird jede der n Stufen (die vor dem Ziel, der (n+1)ten Stufe liegen) entweder betreten oder nicht betreten, man hat also n nein-ja-Entscheidungen, das ergibt 2^n Möglichkeiten, allerdings muss eine Möglichkeit (jedesmal "nein") wieder abgezogen werden, da man ja gemäß der Korrektur nicht in einem Schritt auf die (n+1)-te Stufe gelangen kann.

Für das Folgende sei bemerkt, dass gerade festgestellt wurde, dass es also 2^k-1 Möglichkeiten gibt, die k-te Stufe einer Treppe zu erreichen (k = 1 ... n).

Für die linke Seite
Da man nicht in einem Schritt auf die (n+1)-te Stufe gelangen kann, gibt es eine letzte Stufe davor, das kann irgendeine der Stufen k=1 bis k=n sein, von der kann man dann in einem einzigen letzten Schritt auf Stufe Nr. n+1 gelangen. Die Anzahl der Möglichkeiten ist also nach dem Vorherstehenden 2^1-1 + 2^2-1 + 2^3-1 + 2^4-1 + ... + 2^n-1 =  1 + 2 + 4 + 8 + ... + 2^n-1.

Answer 1

Die Zahl der Möglichkeiten eine n-stufige Treppe zu besteigen:

Treppe mit 1 Stufe: (1) (1 Möglichkeit)
Treppe mit 2 Stufen: (2),(1-2) (2 Möglichkeiten)
Treppe mit 3 Stufen: (3),(1-3),(2-3),(1-2-3) (4 Möglichkeiten)
Treppe mit 4 Stufen: (4),(1-4),(2-4),(3-4),(1-2-4), (1-3-4), (2-3-4), (1-2-3-4) (8 Möglichkeiten)
Treppe mit 5 Stufen: (5),(1-5),(2-5),(3-5),(4-5),(1-2-5),(1-3-5),(1-4-5),(2-3-5),(2-4-5),(3-4-5),(1-2-3-5),(1-2-4-5),(1-3-4-5),(1-2-3-4-5) (16 Möglichkeiten)

allgemein: Treppe mit n Stufen: \( 2^{n-1} \) Möglichkeiten, denn mit jeder Stufe verdoppeln sich die Möglichkeiten.

--------------------------------------------------------------------------------------------------------------------------

Nächste Überlegung:

Treppe mit 6 Stufen: das ist die Summe aller Möglichkeiten für 1-5 Stufen plus die eine (neue Stufe), d.h.

Treppe mit 6 Stufen: (1+2+4+8+16+1) = (2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 1) = 32 Möglichkeiten

allgemein:

Treppe mit (n+1) Stufen: \( \sum\limits_{k=0}^{n-1}{2^k} + 1 \) Möglichkeiten

Daraus folgt (linke Seite bereits oben bewiesen)

\( 2^{n} = \sum\limits_{k=0}^{n-1}{2^k} + 1 \)

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