Summenformel zeigen anhand einer Übungsaufgabe

Erste Frage Aufrufe: 207     Aktiv: 29.05.2022 um 03:50

0
Zeigen Sie die Summenformel

1 + 2 + 4 + . . . + 2n-1=2n− 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.

Hi, das ist eine Übungsaufgabe aus meinem Studium und ich habe keine Ahnung was ich genau machen soll, ich hoffe mir kann jemand helfen.
Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0
Tja, hellsehen kann ich auch nicht. Da wäre der Kontext sicherlich hilfreich, in dem die Aufgabe gestellt wurde.

Klar scheint zu sein, dass man hier nicht mit vollständiger Induktion arbeiten soll, sondern dass ein anderer Beweis gefunden werden soll.

Ich habe gegoogelt und eine Diskussion gefunden. Darin wird die Problematik erwähnt, wie man auf einen "eleganten" Beweis kommen soll ohne ihn zu kennen. Wenn man einen direkten Hinweis gäbe, dann sei es zu einfach...
Ich vermute nun, dass der Tipp mit der Treppe genau das bezweckt: helfen ohne zu viel zu verraten...

Ich habe mir also eine Treppe vorgestellt. Ich stehe auf Stufe Null (vor der Treppe), die oberste Stufe (das Ende der Treppe) ist Stufe n+1. Auch Aufzeichnen hilft.

Für mich sagt die Aufgabenstellung, dass die Strategie ist, durch zwei verschiedene Arten des systematischen Abzählens auf das gleiche Ergebnis zu kommen, wobei die eine Art der Summe $1+2+4+\ldots +2^{n-1}$ entsprechen sollte, die andere Art direkt auf die $2^n-1$. Eventuell auch mit der $1$ rechts auf der linken Seite...
Die ganz richtigen Ideen zum geeigneten Abzählen sind mir noch nicht wirklich eingefallen. Ich bin beim systematischen Abzählen bei Binomialkoeffizienten oder bei der Potenzmenge gelandet....

Ein eleganter Beweis, der mir bei der Beschäftigung damit eingefallen ist, der aber nicht wirklich zur zitierten Aufgabenstellung passt, ist dieser:
Offensichtlich gilt ja $a = 2\cdot a - 1\cdot a$.

Also hier konkret für $a=1+2+4+\ldots + 2^{n-1}$ folgt damit:

$1+2+4+\ldots + 2^{n-1} = 2\cdot (1+2+4+\ldots + 2^{n-1} ) - 1\cdot (1+2+4+\ldots + 2^{n-1} )$

Multipliziere die rechte Seite aus und führe die Subtraktion durch...

(ich zähle hier zwar etwas doppelt ab, aber es sind nicht die Möglichkeiten eine Treppe zu besteigen, sondern alle Treppe mit bis zu n+1 Stufen zu besteigen...)
Diese Antwort melden
geantwortet

Punkte: 2.25K

 

Kommentar schreiben