Induktionsbeweis

30.10.2011, 14:21

Bumppo

Auf diesen Beitrag antworten »

Induktionsbeweis

Meine Frage:
Hallo. Ich habe hier folgende Aufgabe. Beweisen Sie mithilfe vollständiger Induktion, dass : (Summe von k=0 bis n) von (n über k) = (2 hoch n). Wobei n ? natürlichen Zahlen mit 0

Meine Ideen:
Mein Gedankengang ist folgender:
Induktionsschritt: Summe von (0 bis n+1) von (n über k) = (2 hoch n) + Summe von (0 bis n) von (n über k).... aufgelöst komme ich jetzt auf
1=(2 hoch n) + 1. Was falsch ist. Kann mir jemand helfen?!? brauche umbedingt Hilfe. Danke

30.10.2011, 14:51

Iorek

Auf diesen Beitrag antworten »

Bitte schreibe das einmal ordentlich unter Verwendung von LaTeX auf (du kannst auch unseren Formeleditor verwenden). So kann man das nicht entziffern.

30.10.2011, 15:03

Bumppo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} <br /> \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} \end{eqnarray*}$
Das gilt zu beweisen, für n >= 0 ! meinr Rechnung :

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} + \sum\limits_{k=0}^n \begin{pmatrix} n \\ k \\ \end{pmatrix} \end{eqnarray*}$

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

Edit: keinen geschriebenen Text in die LaTeX-Umgebung schreiben, das führt zu Fehlern. LG Iorek

30.10.2011, 15:07

Iorek

Auf diesen Beitrag antworten »

Steht dir der binomische Lehrsatz zur Verfügung? Damit wäre das in zwei Zeilen erledigt.

Ansonsten sind mehrere Sachen zu beanstanden, wie ziehst du die Summe auseinander, wo sind Induktionsanfang und Induktionsvoraussetzung? Wo kommen die 1er her?

30.10.2011, 15:12

Bumppo

Auf diesen Beitrag antworten »

Der Beweis durch binomischen Lehrsatz steht mir nicht zur Verfügung.
Die Zwischenschritte habe ich weggelassen, weil die recht leicht sind. Die 1er bekomme ich daher, da k=0 ist und da jegliches n über 0 immer gleich 1 ist. Mein Beweis ist aber somit falsch ?!?! unglücklich

unglücklich

30.10.2011, 15:13

Iorek

Auf diesen Beitrag antworten »

Ja, dein Beweis ist falsch. Und die "leichten Zwischenschritte" scheinen doch nicht so leicht zu sein.

Wie gesagt: wie ziehst du die Summe auseinander und wann wendest du die IV an? Was erhältst du danach...ohne diese Sachen ist es nur schwer dir zu helfen.

Anzeige

30.10.2011, 15:47

Bumppo

Auf diesen Beitrag antworten »

Oh tut mir Leid, hatte den ersten Induktionsschritt auch falsch aufgeschrieben. Ich meinte das so:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = \sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \\ \end{pmatrix} + \begin{pmatrix} n+1 \\ k \\ \end{pmatrix} <br /> \end{eqnarray*}$

Dann wende ich die IV an! Danach erhalte ich:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} + \begin{pmatrix} n+1 \\ k \\ \end{pmatrix} <br /> \end{eqnarray*}$
Im Endeffekt steht dann da:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} +1<br /> \end{eqnarray*}$
Was genau meinst du mit der Summe ausziehen?
Lg

30.10.2011, 15:53

Gast11022013

Auf diesen Beitrag antworten »

Wie kommst Du auf dieses +1 am Ende? verwirrt

verwirrt

30.10.2011, 15:54

Bumppo

Auf diesen Beitrag antworten »

Da k=0 ist, löst sich das n+1 über k so auf !!

30.10.2011, 15:56

Gast11022013

Auf diesen Beitrag antworten »

Wie kommst Du darauf, daß k=0 ist? verwirrt

verwirrt

30.10.2011, 15:58

BUmppo

Auf diesen Beitrag antworten »

Oh stimmt, mein Fehler... k ist ja nur in der Summe = 0. Aber wie komme ich sonst weiter?

30.10.2011, 16:02

Gast11022013

Auf diesen Beitrag antworten »

Du musst einfach mal versuchen, das zu berechnen!

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

30.10.2011, 16:11

Bumppo

Auf diesen Beitrag antworten »

Ist das denn bis hier hin überhaupt richtig?? ich bin mir unsicher ob das stimmt

30.10.2011, 16:15

Gast11022013

Auf diesen Beitrag antworten »

Das ist natürlich eine ganz andere Frage, denn es stimmt nicht.

Denn k soll ja dann bis (n+1) gehen!

30.10.2011, 16:22

Bumppo

Auf diesen Beitrag antworten »

Zitat:

Original von Bumppo
Oh tut mir Leid, hatte den ersten Induktionsschritt auch falsch aufgeschrieben. Ich meinte das so:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = \sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \\ \end{pmatrix} + \begin{pmatrix} n+1 \\ k \\ \end{pmatrix} <br /> \end{eqnarray*}$

Dann wende ich die IV an! Danach erhalte ich:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} + \begin{pmatrix} n+1 \\ k \\ \end{pmatrix} <br /> \end{eqnarray*}$
Im Endeffekt steht dann da:
$\begin{eqnarray*} <br /> \sum\limits_{k=0}^{n+1} \begin{pmatrix} n \\ k \\ \end{pmatrix} = 2^{n} +1<br /> \end{eqnarray*}$
Was genau meinst du mit der Summe ausziehen?
Lg

Da: Mein 1. Schritt. Der Müsste doch komplett richtig sein. Stehe ich total auf dem Schlauch ???

30.10.2011, 16:29

Wetal

Auf diesen Beitrag antworten »

ganz einfach. du hast vergessen das n in dem binomialkoeffizient zu erhöhen.

zu zeigen:

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

30.10.2011, 16:32

Bumppo

Auf diesen Beitrag antworten »

okay vielen Dank erstmal für eure Hilfe. Wetal du hast recht, aber das hilft mir leider auch nicht weiter.

30.10.2011, 16:45

Wetal

Auf diesen Beitrag antworten »

ist dir bekannt, dass $\begin{eqnarray*} {n+1 \choose k} = {n \choose k-1} + {n \choose k} \end{eqnarray*}$ ist? kann man sonst auch zeigen ^^

30.10.2011, 16:51

Bumppo

Auf diesen Beitrag antworten »

Jap die Formel ist mir Bekannt!!!.

Zitat:

Original von Wetal
ganz einfach. du hast vergessen das n in dem binomialkoeffizient zu erhöhen.

zu zeigen:

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

Kann ich diese Formel jetzt hier bei der Summe anwenden? Oder geht das bei Summen nicht???

30.10.2011, 16:52

Wetal

Auf diesen Beitrag antworten »

natürlich kannst du die formel bei der summe anwenden. so hab ich die aufgabe für mich bewiesen.

30.10.2011, 16:56

Bumppo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum_{k=0}^{n+1} { n+1 \choose k} = 2^{n+1} \end{eqnarray*}$ [/quote]

Daraus folgt dann: $\begin{eqnarray*} \sum_{k=0}^{n+1} { n \choose k} + sum_{k=0}^{n+1} { n \choose k-1} = 2^{n+1} \end{eqnarray*}$ [/quote]

30.10.2011, 17:06

Wetal

Auf diesen Beitrag antworten »

jup. das ist dann

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

nun sollst du zeigen, dass da $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ rauskokmmt, indem du die induktionsvoraussetzung anwendest. noch 'n hinweis: indexverschiebung.

30.10.2011, 17:10

Bumppo

Auf diesen Beitrag antworten »

Zitat:

Original von Wetal
jup. das ist dann

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

nun sollst du zeigen, dass da $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ rauskokmmt, indem du die induktionsvoraussetzung anwendest. noch 'n hinweis: indexverschiebung.

du meinst: $\begin{eqnarray*} \sum_{k=0}^{n+1} { n+1 \choose k} = \sum_{k=0}^{n} { n \choose k} +\sum_{k=0}^{n} { n \choose k-1} \end{eqnarray*}$
Oder? Nun kann ich die IV anwenden, sprich:
$\begin{eqnarray*} \sum_{k=0}^{n+1} { n+1 \choose k} = 2^{n} +\sum_{k=0}^{n} { n \choose k-1} \end{eqnarray*}$

30.10.2011, 17:21

Wetal

Auf diesen Beitrag antworten »

nein, ich habe doch nur den ausdruck in der summe umgeschrieben. warum sollten die summen dann plötzlich 1 glied weniger haben? es stimmt zwar für die erste summe, aba nicht für die zweite.

30.10.2011, 17:24

Bumppo

Auf diesen Beitrag antworten »

Dachte eben wenn man es auf die Weise umschreibt, verringert sich das n über der summe

30.10.2011, 19:36

Bumppo

Auf diesen Beitrag antworten »

bin komplett durcheinander und versteh hier jetzt garnix mehr... kann mir jemand bitte die richtige gleichung posten, an der ich ansetzen kann?

30.10.2011, 20:29

Bumppo

Auf diesen Beitrag antworten »

Ok hat sich erledigt ne freundin hat mir die aufgabe erklärt dennoch vielen dank euch allen!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »