Problem am Ende des Induktionsbeweises zur summe aus n über k = 2^n

19.10.2011, 21:55	Martin L	Auf diesen Beitrag antworten »
Problem am Ende des Induktionsbeweises zur summe aus n über k = 2^n Hey, ich habe das Gefühl, eigentlich fast fertig zu sein. Ich komm aber nicht drauf. Ich muss ja zeigen: $\begin{eqnarray} \sum\limits_{k=0}^{n+1} \begin{pmatrix}n+1 \\ k \end{pmatrix} = 2^{n+1} \end{eqnarray}$ Ich habe jetzt mit der rechten Seite angefangen: $\begin{eqnarray} 2^{n+1} = 2^n 2 \end{eqnarray}$ Jetzt habe ich die Induktionsannahme eingesetzt: $\begin{eqnarray} =2* \sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} =\sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} + \sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} \end{eqnarray}$ Jetzt erst den Anfangswert von k erhöhen und dann zeigen, dass sich nichts tut, wenn man wieder von 0 anfängt, da der erste Summand dann eh 0 ist da man n über -1 hätte. $\begin{eqnarray} =\sum\limits_{k=1}^{n} \begin{pmatrix}n \\ k-1 \end{pmatrix} + \sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} =\sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k-1 \end{pmatrix} + \sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} \end{eqnarray}$ Jetzt habe ich die Summen zusammen gezogen und erhalte: $\begin{eqnarray} =\sum\limits_{k=0}^{n} \begin{pmatrix}n+1 \\ k \end{pmatrix} \end{eqnarray*}$ Sieht ja soweit ganz toll aus, nur fehlt mir halt über der Summe noch ein kleines aber feines "+1". Wie krieg ich das da hin? Oder ist vorher was falsch gelaufen? Wäre toll, wenn mir da jemand helfen könnte. Ich hab auch schon andere Beweise zum Thema gefunden, aber die sind halt alle irgendwo irgendwie anders geführt. Ich kann die zwar nachvollziehen aber ich wüsste jetzt gerne, wie es hier bei mir weitergeht, oder ob ich einen Fehler gemacht habe. Gruß Martin
19.10.2011, 22:13	Helferlein	Auf diesen Beitrag antworten »
Beim Übergang von k zu k-1 unterschlägst Du einen Summanden.
19.10.2011, 22:18	Martin L	Auf diesen Beitrag antworten »
oh, zufällig $\begin{eqnarray} \begin{pmatrix}n \\ n\end{pmatrix} \end{eqnarray}$ ? Weil der würde ja am Ende noch kommen, wenn k bei 0 gestartet wäre. Das wäre aber 1 und genau das ist auch das, was ich am Ende überbehalte wenn ich meinen Index verschieben würde. Passt das so? Müsste ja eigentlich. Ansonsten hab ich mich gerade blamiert :-D.
20.10.2011, 00:33	Helferlein	Auf diesen Beitrag antworten »
RE: Problem am Ende des Induktionsbeweises zur summe aus n über k = 2^n Na Du hast doch $\begin{eqnarray} \sum\limits_{k=0}^{n} \begin{pmatrix}n \\ k \end{pmatrix} \end{eqnarray}$ und gehst über zu $\begin{eqnarray} \sum\limits_{k=1}^{n} \begin{pmatrix}n \\ k-1 \end{pmatrix} \end{eqnarray}$ Die erste Summe fängt bei k=0 an und geht bis k=n. Willst Du stattdessen k-1 verwenden, so musst Du den Laufindex jeweils um eins erhöhen. Sie läuft also von k=1 bis k=n+1.
20.10.2011, 00:47	Martin L	Auf diesen Beitrag antworten »
Joa so kann man es natürlich auch machen. Ist etwas geschickter. Ich habe das aber ja eigentlich genau so gemacht. Ich habe halt gesagt: Wenn ich k-1 verwende, dann ist der letzte Summand ja (n über n-1). Ansonsten war der letzte Summand (n über n). Also nehme ich diesen Summanden einfach und ergänze den hinten. Also das gleiche, als hätte ich erst den Laufindex erhöht und dann den n+1-ten Summanden herausgezogen. Gruß Martin

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »