Vollständige Induktion

04.11.2010, 16:04

Legostein

Vollständige Induktion

Induktionsvorraussetzung: $\begin{eqnarray*} \sum_{k=0}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom n k \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ = $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ ; Induktionsbehauptung: $\begin{eqnarray*} \sum_{k=0}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ = $\begin{eqnarray*} 3^{n+1} \end{eqnarray*}$

Induktionsanfang: $\begin{eqnarray*} \sum_{k=0}^{0} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom 0 k \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ = $\begin{eqnarray*} 3^{0} \end{eqnarray*}$ = $\begin{eqnarray*} ~\binom 0 0 \end{eqnarray*}$ $\begin{eqnarray*} 2^{0} \end{eqnarray*}$ = 1

Induktionsschritt: $\begin{eqnarray*} \sum_{k=0}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ = $\begin{eqnarray*} \sum_{k=0}^{0} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=n+1}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$
=1 + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ + $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$
=1 + $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k-1} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$
=3 + $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$

habe ich bis hierhin einen Fehler gemacht? Ansonsten müsste ich jetzt ja irgendwie auf = $\begin{eqnarray*} 3^{n+1} \end{eqnarray*}$ , aber weiß nicht wie ichs umformen soll..

04.11.2010, 19:57

galois

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Hallo,

In diesem Ausdruck ist ein Fehler: $\begin{eqnarray*} \sum_{k=0}^{0} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n+1} {k} \cdot 2^{k} \end{eqnarray*}$ . Dieser Ausdruck sollte 1 ergeben.

galois

04.11.2010, 20:16

galois

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Sorry, habe mich verkuckt. Das hast du ja bereits schon als 1 hingeschrieben.

05.11.2010, 10:11

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Legostein
=1 + $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k-1} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$
=3 + $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ + $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} ~\binom {n} {k} \end{eqnarray*}$ $\begin{eqnarray*} 2^{k} \end{eqnarray*}$

Mir ist nicht klar, wie du von der oberen zur unteren Zeile kommst.

05.11.2010, 19:17

Legostein

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum_{k=1}^{n} \binom {n}{k-1} 2^{k} \end{eqnarray*}$

Na wenn ich da k=1 einsetze steht dort $\begin{eqnarray*} \binom {n}{0} 2^{1} \end{eqnarray*}$ = 1*2
Diese 2 habe ich dann zur 1 im nächsten Schritt addiert.

06.11.2010, 08:43

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Hmm. Hätte dann nicht das da stehen müssen:

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

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

06.11.2010, 16:39

Legostein

Auf diesen Beitrag antworten »

Hm, ja, stimmt eigentlich... wies dann weitergeht weiß ich allerdings nicht...

06.11.2010, 16:59

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Bleiben wir mal bei:

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

In die 1. Summe kannst du die 1 wieder reinnehmen.
In der 2. Summe machst du eine Indexverschiebung k = m+1.

06.11.2010, 17:26

Legostein

Auf diesen Beitrag antworten »

Meinst du so?:

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

Das wäre dann gleich

$\begin{eqnarray*} 2^{n+1} + 3^{n} + \sum_{k=m+2}^{n} ~\binom n {m} 2^{k} \end{eqnarray*}$

06.11.2010, 18:38

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Das mit der Indexverschiebung mußt du nochmal üben. Ersetze dazu alle k in dem Summanden der Summe $\begin{eqnarray*} \sum_{k=1}^{n}~\binom {n}{k-1} 2^{k} \end{eqnarray*}$ durch m+1. Überlege dir dann, welche die untere und obere Grenzen der Summe sind.

06.11.2010, 19:22

Legostein

Auf diesen Beitrag antworten »

Ich habe mich mal an der Formel oben bei Wikipedia orientiert.. http://de.wikipedia.org/wiki/Indexverschiebung
$\begin{eqnarray*} \sum_{k=m+1}^{n+m}~\binom {n-m} {k-1-m} 2^{k-m} \end{eqnarray*}$ ?

06.11.2010, 22:17

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Du hast die Wiki-Formel nicht richtig angewendet. Setze da z=-1 und dann folgt:

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

Mache dir klar, daß das die gleiche Summe ist, indem du einfach mal die Summanden vergleichst.

06.11.2010, 23:12

Legostein

Auf diesen Beitrag antworten »

Ok, das habe ich glaube ich verstanden. Aber was bringt denn diese Indexerweiterung? Eigentlich läuft es doch auf das selbe, nämlich auf "2" hinaus, oder?

07.11.2010, 09:54

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Du mußt schon noch ein bißchen rechnen:

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

Ziehe nun aus der Summe den Faktor 2 raus und wende nochmal die Induktionsvoraussetzung an.

07.11.2010, 12:30

Legostein

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum_{k=0}^{n} \binom n k 2^{k+1} = 2^1 \sum_{k=0}^{n} \binom n k 2^k = 2 \cdot 3^n \end{eqnarray*}$

$\begin{eqnarray*} 2\cdot3^n + 3^n = 3 * 3^n = 3 ^{n+1} \end{eqnarray*}$

Ich glaub ich habs... tausend Dank fürs auf die ErklärungSchubsen und die Geduld. ! Freude

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen