Induktionsbeweis

11.11.2008, 18:12

Roflkopter

Induktionsbeweis

Hi Leute

Ich soll volgendes beweisen: $\begin{eqnarray*} \sum_{k=1}^n~ \begin{pmatrix} n \\ k \end{pmatrix} = 2^n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$

Ich will das mit vollständiger Induktion beweisen.
Induktionsanfang,-schritt,-vorraussetzung ist trivial.

Dann bekomme ich die Summe: $\begin{eqnarray*} \sum_{k=1}^{n+1}~ \begin{pmatrix} {n+1} \\ k \end{pmatrix} \end{eqnarray*}$

Mein Problem. Wie splitte ich nun die Summe auf, damit ich mit der Induktionsvorraussetzung weiterarbeiten kann?

Gruß

11.11.2008, 18:24

Duedi

Auf diesen Beitrag antworten »

Benutze: $\begin{eqnarray*} \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1} \end{eqnarray*}$

11.11.2008, 18:25

Leopold

Auf diesen Beitrag antworten »

Erstens: Die Summation muß mit $\begin{eqnarray*} k=0 \end{eqnarray*}$ beginnen.

Zweitens: Verwende

$\begin{eqnarray*} {{n+1} \choose k} = {n \choose {k-1}} + {n \choose k} \end{eqnarray*}$

Beachte besonders die Randfälle $\begin{eqnarray*} k=0 \end{eqnarray*}$ und $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ oder definiere

$\begin{eqnarray*} {n \choose {-1}} = 0 \, , \ \ {n \choose {n+1}} = 0 \end{eqnarray*}$

Denn dann gilt die obige Beziehung auch in diesen Randfällen.

Drittens: "Folgendes"

Viertens: "Voraussetzung"

11.11.2008, 18:29

Roflkopter

Auf diesen Beitrag antworten »

Achja...Dankeschön an euch beiden...Hab da gerade noch mit gerechnet und dann komm ich da nicht drauf :-P
Manchmal ist man einfach blind^^

Gruß

11.11.2008, 19:02

Roflkopter

Auf diesen Beitrag antworten »

Hmm...ich habe hier glaube ich doch noch ein Problem.
Ich habe bis jetzt:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} {n+1} \\ k \end{pmatrix} = \sum_{k=0}^n~\begin{pmatrix} n \\ k \end {pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} + \end{eqnarray*}$ $\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ {k-1}\end{pmatrix} \end{eqnarray*}$

Nach Induktionsvorausetzung ist dann:

$\begin{eqnarray*} 2^n + \sum_{k=0}^n~\begin{pmatrix} n \\ {k-1}\end{pmatrix} \end{eqnarray*}$

jetzt komme ich aber nicht auf den Schritt, dass dieser Ausdruck $\begin{eqnarray*} =2^{n+1} \end{eqnarray*}$ ist

11.11.2008, 19:54

Reksilat

Auf diesen Beitrag antworten »

Dann mach eine Indexverschiebung k->k+1 und verwende dazu das, was Leopold oben zu den Binomialkoeffizienten über -1 und n+1 geschrieben hat.

11.11.2008, 20:01

Roflkopter

Auf diesen Beitrag antworten »

schnall ich nicht unglücklich

11.11.2008, 22:20

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Roflkopter
$\begin{eqnarray*} \sum_{k=0}^{n+1}~\begin{pmatrix} {n+1} \\ k \end{pmatrix} = \sum_{k=0}^n~\begin{pmatrix} n \\ k \end {pmatrix} \end{eqnarray*}$ $\begin{eqnarray*} + \end{eqnarray*}$ $\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ {k-1}\end{pmatrix} \end{eqnarray*}$

Das kann schon mal nicht sein. Vorher ging die Summe von k=0 bis n+1. Nachher nur noch bis n.

11.11.2008, 23:25

Reksilat

Auf diesen Beitrag antworten »

Da hat klarsoweit recht, das muss natürlich auch noch ausgebessert werden.

Zur Indexverschiebung:
Erst ein Beispiel zur Veranschaulichung:
$\begin{eqnarray*} \sum_{n=2}^5 n=\sum_{n=1}^4 (n+1) \end{eqnarray*}$ (=2+3+4+5)

und allgemein gilt dann:
$\begin{eqnarray*} \sum_{n=r}^s a(n)=\sum_{n=r+x}^{s+x} a(n-x) \end{eqnarray*}$

Du verschiebst also die Summationsgrenzen und veränderst im gleichen Maße das, worüber Du summierst. Jeder einzelne Summand bleibt also gleich, die Summe sieht nur etwas anders aus.

Neue Frage »

Antworten »

Induktionsbeweis

Verwandte Themen