vollständige Induktion, Induktionsbeweis

Neue Frage »

10.10.2014, 21:18	sevenelf	Auf diesen Beitrag antworten »
vollständige Induktion, Induktionsbeweis Hallo, ich habe ein Problem mit dem Induktionsbeweis. Die Aufgabe besteht darin, dass man beweisen soll, dass für alle n $\begin{eqnarray} \in \mathbb N \end{eqnarray}$ gilt: $\begin{eqnarray} \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} 2^{n} \end{eqnarray}$ Angefangen habe ich so: Induktionsanfang: n=1 $\begin{eqnarray} \sum\limits_{k=0}^1 \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{eqnarray}$ + $\begin{eqnarray} \sum\limits_{k=0}^1 \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} 2^{1} \end{eqnarray}$ Induktionsvoraussetzung: Für n=m gelte: $\begin{eqnarray} \sum\limits_{k=0}^m \begin{pmatrix} m \\ k \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} 2^{m} \end{eqnarray}$ Induktionsbehauptung: Für n= m+1 gilt: $\begin{eqnarray} \sum\limits_{k=0}^{m+1} \begin{pmatrix} m+1 \\ k \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} 2^{m+1} \end{eqnarray}$ Aber wie lautet nun der Induktionsbeweis? Danke
10.10.2014, 21:30	Gast11022013	Auf diesen Beitrag antworten »
Kennst du den binomischen Lehrsatz?
11.10.2014, 16:06	sevenelf	Auf diesen Beitrag antworten »
eigentlich schon, aber ich stehe irgendwie auf dem Schlauch..
11.10.2014, 16:18	Iorek	Auf diesen Beitrag antworten »
Wenn dir der binomische Lehrsatz zur Verfügung steht, dann kannst du dir die Induktion hier sparen. Du könntest ja mal versuchen, $\begin{eqnarray} 2^n \end{eqnarray}$ in eine Form zu bringen, auf die sich der binomische Lehrsatz anwenden lässt.
12.10.2014, 10:41	sevenelf	Auf diesen Beitrag antworten »
vollständige Induktion meinst du für "in eine andere Form bringen" $\begin{eqnarray} (1+1)^{n} \end{eqnarray}$ für $\begin{eqnarray} 2^{n} \end{eqnarray}$ ? Dann ist $\begin{eqnarray} (1+1)^{n} \end{eqnarray}$ = $\begin{eqnarray} \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray}$ * $\begin{eqnarray} 1^{n} \end{eqnarray}$ * $\begin{eqnarray} 1^{n} \end{eqnarray}$ oder?
12.10.2014, 10:44	Gast11022013	Auf diesen Beitrag antworten »
Die Exponenten der 1 würden zwar nicht direkt denen des binomischen Lehrsatz entsprechen, aber das ist hier eigentlich irrelevant. Ansonsten war es so gemeint, ja. Und nun?
Anzeige

12.10.2014, 12:55	sevenelf	Auf diesen Beitrag antworten »
nun müsste ich wohl den binomischen Lehrsatz beweisen... aber wie
12.10.2014, 13:02	Gast11022013	Auf diesen Beitrag antworten »
Wenn ihr ihn in der Vorlesung bewiesen habt dann nicht. Wenn du ihn nicht bewiesen hast, dann kannst du die Aufgabe wahrscheinlich besser gleich mit Induktion lösen, weil der Induktionsbeweis für den binomischen Lehrsatz schwieriger sein sollte.
12.10.2014, 14:26	sevenelf	Auf diesen Beitrag antworten »
Ja, dass der Beweis des binomischen Lehrsatzes schwierig ist, habe ich auch bemerkt. Kannst du mir einen Tipp geben oder einen Ansatz für den Induktionsbeweis geben? Ich komme mit dieser Aufgabe überhaupt nicht klar
12.10.2014, 14:30	Gast11022013	Auf diesen Beitrag antworten »
Hattet ihr den binomischen Lehrsatz nun in der Vorlesung oder nicht?
12.10.2014, 14:48	sevenelf	Auf diesen Beitrag antworten »
Nein ich hatte noch keine Vorlesung
12.10.2014, 15:03	Gast11022013	Auf diesen Beitrag antworten »
Achso. Wenn du den binomischen Lehrsatz mit Induktion beweisen möchtest, dann ist es hilfreich folgenden Zusammenhang des Binomialkoeffizienten zu kennen $\begin{eqnarray} \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1} \end{eqnarray}$ Außerdem muss man auch sonst geschickt mit den auftretenden Summen rechnen. Zum Beispiel Indexverschiebung oder "rausrechnen" von Summengliedern. Aber wie gesagt, dann kannst du lieber die Aufgabe direkt mit Induktion lösen, weil das einfacher sein sollte als den binomischen Lehrsatz zu beweisen. Du kannst dir aber trotzdem noch mal überlegen wieso die Aussage direkt aus dem binomischen Lehrsatz folgen würde.

Neue Frage »

Antworten »

vollständige Induktion, Induktionsbeweis

Verwandte Themen