vollständige Induktion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich versuche folgendes zu beweisen: [m]\textstyle\sum_{k = 0}^m{\binom{m}{k}} = 2^m[/m]. Für $m = [mm] 0\!$ [/mm] ist es klar: [m]\textstyle\sum_{k = 0}^0{\binom{m}{k}} = \binom{0}{0} = 1 = 2^0[/m]. Aber der Induktionsschritt mißlingt in beide Richtungen:
[mm] $\underline{m \leadsto m - 1:}$
[/mm]
[m]\sum_{k = 0}^{m - 1}{\binom{m}{k}} = \sum_{k = 0}^m{\binom{m}{k}} - \binom{m}{m}\stackrel{\begin{subarray}{l}\texttt{Induktions-}\\\texttt{annahme}\end{subarray}}{=}2^m - \binom{m}{m} = 2^m - 1 \ne 2^{m - 1}[/m]
[mm] $\underline{m \leadsto m + 1:}$
[/mm]
[m]\sum_{k = 0}^{m + 1}{\binom{m}{k}} = \sum_{k = 0}^m{\binom{m}{k}} + \binom{m}{m+1}\stackrel{\begin{subarray}{l}\texttt{Induktions-}\\\texttt{annahme}\end{subarray}}{=}2^m + 0 = 2^m \ne 2^{m + 1}[/m]
Was mache ich falsch?
Danke für eure Hilfe!
Viele Grüße
Karl
|
|
| |
|
Hallo Karl,
> Ich versuche folgendes zu beweisen: [m]\textstyle\sum_{k = 0}^m{\binom{m}{k}} = 2^m[/m].
verwende doch die folgende Identität: [m]\textstyle\binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}[/m]
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:17 Do 02.06.2005 | | Autor: | Karl_Pech |
Hallo MathePower,
Danke für deinen Hinweis! Damit kann man die Aufgabe lösen:
[m]\sum_{k = 0}^{m + 1}{{m+1} \choose k} = \left( {\sum_{k = 0}^{m + 1} {m \choose k} } \right) + \left( {\sum_{k = 1}^{m + 1} {m \choose {k-1}} } \right)[/m]
Es ist klar, daß wir für die erste Summe nach Annahme [mm] $2^m$ [/mm] einsetzen können, nachdem wir den letzten Summanden abgespaltet haben. Den Wert der zweiten Summe kriegt man raus, wenn man sich von der Kurzschreibweise löst und die Summe ausschreibt:
[m]\sum_{k = 1}^{m + 1} {m \choose {k-1}} = {m \choose 0} + {m \choose 1} + {m \choose 2} + {m \choose 3} + {m \choose 4} + \cdots + \underbrace {m \choose {m + 1 - 1}}_{m \choose m} = \sum_{k = 0}^m {m \choose k}[/m]
Ich schreibe jetzt alles nochmal zusammen hin:
[m]\sum_{k = 0}^{m + 1} {{m+1} \choose k} = \left( {\sum_{k = 0}^{m + 1} {m \choose k} } \right) + \left( {\sum_{k = 1}^{m + 1} {m \choose {k-1}} } \right)[/m]
[m]= \left( {\sum_{k = 0}^m {m \choose k} } \right) + {m \choose {m+1}} + \sum_{k = 0}^m {m \choose k} \stackrel{\begin{subarray}{l}\texttt{Induktions-}\\\texttt{annahme}\end{subarray}}{=} 2^m + 2^m + 0 = 2*2^m = 2^{m + 1}. \quad \square[/m]
Viele Grüße
Karl
|
|
|
|
