vollständige Induktion

03.03.2012, 02:01

Walter Subject

vollständige Induktion

Meine Frage:
Hallo,
Ich soll für $\begin{eqnarray*} n\in N \end{eqnarray*}$ den Wert der Summe

$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix} \end{eqnarray*}$ angeben und mein Ergenbis z.B. durch Induktion begründen.

Meine Ideen:
Durch probieren mit n=0,1,2,3 kommt man auf die Summenwerte 1, 3, 9, 27

Also ist der vermutete Wert $\begin{eqnarray*} 3^{n} \end{eqnarray*}$

Die Induktionsvoraussetzung wäre dann:

$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}= 3^{n} \end{eqnarray*}$

Die Induktionsbehauptung wäre dann:

$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}+ 2^{n+1}\cdot \begin{pmatrix} n \\ n+1 \end{pmatrix}= 3^{n+1} \end{eqnarray*}$

Induktionsanfang:

Für n=0 gilt 1=1 also eine wahre Aussage.

Beim Induktionsschritt habe ich umgeformt, bleibe aber irgendwie stecken. Ich habe zunächst zu $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ den letzten Summand auf der linken Seite der Vorraussetzung addiert also:
$\begin{eqnarray*} 3^{n}+2^{n+1}\cdot \begin{pmatrix} n \\ n+1 \end{pmatrix} \end{eqnarray*}$
jetzt müsste ich mal fragen, ob $\begin{eqnarray*} \begin{pmatrix} n \\ n+1 \end{pmatrix}= - \frac{1}{n+1} \end{eqnarray*}$ ist? Sonst macht es keinen Sinn das alles hinzuschreiben was ich weitergerechnet habe.

03.03.2012, 02:22

NichtBekannt112

Auf diesen Beitrag antworten »

RE: vollständige Induktion
Nein, leider ist nicht $\begin{eqnarray*} \begin{pmatrix} n \\ n+1 \end{pmatrix}= - \frac{1}{n+1} \end{eqnarray*}$ , sondern $\begin{eqnarray*} \begin{pmatrix} n \\ n+1 \end{pmatrix}=0 \end{eqnarray*}$ .
Bei dir ist leider schon die Umstellung von n auf n+1 nicht ganz gelungen. Da sich in der Ausgangsbehauptung ein Muster erkennen lässt, kann man das vielleicht als Summe umschreiben? Augenzwinkern

Wenn ja, dann siehst du vielleicht auch den Fehler, den du im Induktionsschluss am Anfang gemacht hast.

Naja, ich wünsche noch eine angenehme Nacht smile

03.03.2012, 17:19

Walter Subject

Auf diesen Beitrag antworten »

RE: vollständige Induktion

Zitat:

Original von NichtBekannt112
Nein, leider ist nicht $\begin{eqnarray*} \begin{pmatrix} n \\ n+1 \end{pmatrix}= - \frac{1}{n+1} \end{eqnarray*}$ , sondern $\begin{eqnarray*} \begin{pmatrix} n \\ n+1 \end{pmatrix}=0 \end{eqnarray*}$ .

Hab mir schon gedacht, dass das falsch ist, weil die Defintion
$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix}=\frac{n!}{k!\left(n- k\right)! } \end{eqnarray*}$ ja nur für $\begin{eqnarray*} k\leq n \end{eqnarray*}$ gilt. Aber warum ist das dann 0 bzw wie rechnet man wenn $\begin{eqnarray*} k\geq n \end{eqnarray*}$ ?

Zitat:

Original von NichtBekannt112
Bei dir ist leider schon die Umstellung von n auf n+1 nicht ganz gelungen. Da sich in der Ausgangsbehauptung ein Muster erkennen lässt, kann man das vielleicht als Summe umschreiben? Augenzwinkern

Meinst du so: $\begin{eqnarray*} \sum\limits_{k=0}^n 2^{k}\cdot \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ oder soll ich $\begin{eqnarray*} \left(1+ 2 \right)^{n} \end{eqnarray*}$ anstatt $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ schreiben?

Zitat:

Original von NichtBekannt112
Wenn ja, dann siehst du vielleicht auch den Fehler, den du im Induktionsschluss am Anfang gemacht hast.

Falls ich ersteres falsch gemacht habe, kann es dann sein, dass die Behauptung
$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}+ 2^{n+1}\cdot \begin{pmatrix} n+1 \\ n+1 \end{pmatrix}= 3^{n+1} \end{eqnarray*}$ heißen muss bzw. $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}\cdot \begin{pmatrix} n+1 \\ k \end{pmatrix} =3^{n+1} \end{eqnarray*}$ ?

03.03.2012, 20:07

NichtBekannt112

Auf diesen Beitrag antworten »

RE: vollständige Induktion

Zitat:

Original von Walter Subject
Aber warum ist das dann 0 bzw wie rechnet man wenn $\begin{eqnarray*} k> n \end{eqnarray*}$ ?

Ich vermute, das wurde logisch hergeleitet. Wenn ich zum Beispiel 5 aus 4 ziehen möchte, habe ich dafür 0 Möglichkeiten, also wäre 4 über 5 = 0.
Eine bessere Begründung kann ich dir leider nicht liefern, aber dass n über k für k>n wirklich 0 ergibt, sagt auch Wikipedia : http://de.wikipedia.org/wiki/Binomialkoe...t#Eigenschaften (und diverse Nachschlagwerke) smile

Zitat:

Original von Walter Subject
Meinst du so: $\begin{eqnarray*} \sum\limits_{k=0}^n 2^{k}\cdot \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

Ja so meinte ich das. Nun fällt die Umformulierung

Zitat:

Original von Walter Subject
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}\cdot \begin{pmatrix} n+1 \\ k \end{pmatrix} =3^{n+1} \end{eqnarray*}$

auch deutlich leichter.

Mir stellt sich noch die Frage, ob du den binomischen Satz kennst und/oder ihn benutzen darfst. Denn das was du zeigen sollst, ist genau eine Anwendung dieses Satzes.
Falls du das nicht benutzen willst, wäre $\begin{eqnarray*} \binom {n+1} k = \binom n k + \binom n {k-1} \end{eqnarray*}$ für deinen Induktionsschluss möglicherweise eine nützliche Umformung.
Dir noch gutes Gelingen smile

04.03.2012, 01:44

Walter Subject

Auf diesen Beitrag antworten »

Vielen Dank für deine Hilfe Wink

04.03.2012, 02:26

NichtBekannt112

Auf diesen Beitrag antworten »

Sehr gerne Freude

04.03.2012, 04:25

Walter Subject

Auf diesen Beitrag antworten »

Sorry aber kannst mir vielleicht nochmal auf die Sprünge helfen. Also ich hab jetzt umgeformt bis $\begin{eqnarray*} 3^{n}+ 2^{k}\cdot \begin{pmatrix} n+ 1 \\ k \end{pmatrix}= 3^{n}+ 2^{k}\cdot \begin{pmatrix} n \\ k \end{pmatrix}+ 2^{k}\cdot \begin{pmatrix} n \\ k- 1 \end{pmatrix} = 3^{n}+ 3^{n}+ 2^{k}\cdot \begin{pmatrix} n \\ k- 1 \end{pmatrix}= 2\cdot 3^{n} + 2^{k} \cdot \begin{pmatrix} n \\ k- 1 \end{pmatrix} \end{eqnarray*}$
Ich hoffe mal das stimmt halbwegs. Wenn ich jetzt noch irgendwie $\begin{eqnarray*} 2^{k}\cdot \begin{pmatrix} n \\ k- 1 \end{pmatrix} \end{eqnarray*}$ in $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ umwandeln kann, dann hätte ich es ja, aber es klappt nicht. Und mit dem Binominalsatz komm ich auch nicht weiter...

04.03.2012, 06:30

Dopap

Auf diesen Beitrag antworten »

RE: vollständige Induktion

Zitat:

Original von Walter Subject

Die Induktionsvoraussetzung wäre dann:

$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}= 3^{n} \end{eqnarray*}$

Die Induktionsbehauptung wäre dann:

$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}+ 2^{n+1}\cdot \begin{pmatrix} n \\ n+1 \end{pmatrix}= 3^{n+1} \end{eqnarray*}$

sorry, wenn ich mich kurz einmische.
1.) die Binomialkoeff. kann man in Latex als

code:
1:	\binom {n}{k}

schreiben.

2.) Die Induktionsbehauptung gefällt mir nicht.
Meiner Meinung nach müsste in jedem Binomkoeffizient oben n+1 stehen. Das würde auch das "Problem" $\begin{eqnarray*} \binom {n}{n+1} \end{eqnarray*}$ bereinigen.

04.03.2012, 10:29

NichtBekannt112

Auf diesen Beitrag antworten »

Zitat:

Original von Walter Subject
Sorry aber kannst mir vielleicht nochmal auf die Sprünge helfen. [...] Wenn ich jetzt noch irgendwie $\begin{eqnarray*} 2^{k}\cdot \begin{pmatrix} n \\ k- 1 \end{pmatrix} \end{eqnarray*}$ in $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ umwandeln kann, dann hätte ich es ja, aber es klappt nicht.

Problem ist, dass du die Summen vor den Termen vergessen hast, so kann ich dir nicht helfen. Wenn ich die Grenzen der Summen nicht kenne (die hier eine entscheidende Rolle spielen), dann kann ich dir leider nicht sagen, wie es geht unglücklich

Auch weiß ich nicht ganz, wie du auf $\begin{eqnarray*} 3^{n}+ 2^{k}\cdot \begin{pmatrix} n+ 1 \\ k \end{pmatrix} \end{eqnarray*}$ umgeformt hast, denn eigentlich ist $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}\cdot \begin{pmatrix} n+ 1 \\ k \end{pmatrix} \end{eqnarray*}$ der Startterm, ich sehe ohne Grenzen die Umformung leider nicht.

Zitat:

Und mit dem Binominalsatz komm ich auch nicht weiter...

Der binomische Satz / Binomialsatz lautet
$\begin{eqnarray*} \left(a+b\right) ^{n} = \sum\limits_{k=0}^n \binom n k a^{k} b^{n-k} \end{eqnarray*}$
also ist dein Problem genau eine Anwendung dieses Satzes (für a=2, b=1). Deswegen hatte ich gefragt, ob du ihn kennst/benutzen darfst, weil du damit schon fertig wärst. (Ich nehme aber an, du sollst das explizit durch Induktion zeigen Augenzwinkern

).

Also - wenn es dir nichts ausmacht - würde ich dich bitten, deine Gedanken mit den Summen noch einmal hier zu formulieren. Würde mich freuen smile

04.03.2012, 10:46

Walter Subject

Auf diesen Beitrag antworten »

Ich hab mich ja korrigiert. Allerdings dürfte das hier falsch sein:
$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix}+ 2^{n+1}\cdot \begin{pmatrix} n+1 \\ n+1 \end{pmatrix}= 3^{n+1} \end{eqnarray*}$
Aber die Summenformel ist richtig:
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}\cdot \begin{pmatrix} n+1 \\ k \end{pmatrix} =3^{n+1} \end{eqnarray*}$ ?
Soweit war ich aber auch schon. In meinem letzten Beitrag rechne ich ja mit der richtigen Summe. Der letzte Summand, den ich zu $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ addiere ist auf jeden Fall $\begin{eqnarray*} 2^{k}\cdot \begin{pmatrix} n+1 \\ k \end{pmatrix} \end{eqnarray*}$ wobei $\begin{eqnarray*} k= n+1 \end{eqnarray*}$ ist. Ich kann jetzt natürlich anstelle der Rekursionsformel anzuwenden, was ich ja als letztes probiert hab gleich $\begin{eqnarray*} k= n+1 \end{eqnarray*}$ setzen. Aber das hab ich schon probiert. Dann hab ich $\begin{eqnarray*} 3^{n} +2^{n+1}\cdot \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray*}$ . Weil $\begin{eqnarray*} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix}=1 \end{eqnarray*}$ ist, bekomme ich $\begin{eqnarray*} 3^{n} +2^{n+1} \end{eqnarray*}$ . So dann hab ich halt nicht mehr weitergewusst, weil die unterschiedlichen Basen stören und ich nicht, weiß wie ich das weiterumformen kann, dass es irgendwie hilft. Wenn $\begin{eqnarray*} 2^{n+1}=3 \end{eqnarray*}$ ist, dann wär das easy...
Also ich glaub mit der Rekursionsformel wird das eher was.

04.03.2012, 22:38

NichtBekannt112

Auf diesen Beitrag antworten »

Zitat:

Original von Walter Subject
Aber die Summenformel ist richtig:
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}\cdot \begin{pmatrix} n+1 \\ k \end{pmatrix} =3^{n+1} \end{eqnarray*}$ ?

Fassen wir mal zusammen, was wir bisher getan haben. Wir haben die Summenformel und eingebaut und sind jetzt bei
$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} 2^{k}*\binom {n+1} k =\sum\limits_{k=0}^{n} 2^{k}*\binom {n+1} k + 2^{n+1}=\sum\limits_{k=0}^{n} 2^{k}*\left(\binom n k+\binom n {k-1}\right)+2^{n+1}= \end{eqnarray*}$
$\begin{eqnarray*} =\sum\limits_{k=0}^{n} 2^{k}*\binom n k +\sum\limits_{k=0}^{n} 2^{k}*\binom n {k-1} +2^{n+1}=^{I.V} 3^n+\sum\limits_{k=0}^{n} 2^{k}*\binom n {k-1} +2^{n+1} \end{eqnarray*}$
gelandet. Jetzt ist der weg zu $\begin{eqnarray*} 3^{n+1} \end{eqnarray*}$ doch nicht mehr weit (Spoiler : Eine Indexverschiebung wäre vielleicht der Schlüssel zur Lösung^^).

Zitat:

Original von Walter Subject
Also ich glaub mit der Rekursionsformel wird das eher was.

(Falls du mit Rekursionsformel deinen aller ersten Ansatz meinst: ) Das ist deine Entscheidung, ich fand das persönlich mit der Summe einfacher (und bei der Summer sind wir jetzt auch fast fertig), aber es bleibt dir überlassen, wie du es machen möchtest Augenzwinkern

05.03.2012, 20:47

Walter Subject

Auf diesen Beitrag antworten »

Zitat:

Original von NichtBekannt112

Zitat:

Du hast natürlich recht. Ich wollte einfach den letzten Summanden meiner ürsprunglichen Behauptung zu $\begin{eqnarray*} 3^{n} \end{eqnarray*}$ addieren. Dabei habe ich nicht bedacht, dass $\begin{eqnarray*} 3^{n}= \begin{pmatrix} n \\ 0 \end{pmatrix}+ 2\cdot \begin{pmatrix} n \\ 1 \end{pmatrix}+ 2^{2} \cdot \begin{pmatrix} n \\ 2 \end{pmatrix}+...+ 2^{n}\cdot \begin{pmatrix} n \\ n \end{pmatrix} \end{eqnarray*}$ ist. Es muss ja in jedem Summand $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k \end{pmatrix} \end{eqnarray*}$ stehen und nicht $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ . Von daher war das dann Quark.

Zitat:

Original von NichtBekannt112

Zitat:

Und mit dem Binominalsatz komm ich auch nicht weiter...

Ja also eventuell $\begin{eqnarray*} \left(\sum\limits_{k=0}^n \binom n k a^{k} b^{n-k} \right)\cdot \left(1+ 2\right) = 3\cdot 3^{n}= 3^{n+1} \end{eqnarray*}$ ?!

05.03.2012, 20:49

Walter Subject

Auf diesen Beitrag antworten »

Zitat:

Original von Walter Subject
Wenn $\begin{eqnarray*} 2^{n+1}=3 \end{eqnarray*}$ ist, dann wär das easy...

Quatsch, ist natürlich falsch.

05.03.2012, 20:54

Walter Subject

Auf diesen Beitrag antworten »

Zitat:

Original von Walter Subject

Ja also eventuell $\begin{eqnarray*} \left(\sum\limits_{k=0}^n \binom n k a^{k} b^{n-k} \right)\cdot \left(1+ 2\right) = 3\cdot 3^{n}= 3^{n+1} \end{eqnarray*}$ ?!

Weiß jetzt bloss nicht ob das trivial ist oder ob ich die Implikation iwie verdreht habe...?!?

06.03.2012, 00:59

NichtBekannt112

Auf diesen Beitrag antworten »

Also der binomische Satz lautet
$\begin{eqnarray*} \left(a+b\right) ^{n} = \sum\limits_{k=0}^n \binom n k a^{k} b^{n-k} \end{eqnarray*}$
Setze a=2, b=1 und du erhältst
$\begin{eqnarray*} \left(3\right) ^{n} = \sum\limits_{k=0}^n \binom n k 2^{k} 1^{n-k} \end{eqnarray*}$
also
$\begin{eqnarray*} \sum\limits_{k=0}^n 2^k \binom n k = 3^n \end{eqnarray*}$ ,
, genau das, was du zeigen sollst. (So meinte ich das mit "Anwendung des Binomischen Satzes").
Aber ich nehme an, die Aufgabe lautet "Zeigen sie durch Induktion, dass" - somit dürftest du das nicht anwenden. Und der Binomische Satz hilft dir auch nicht beim Induktionsschluss.

Zitat:

Original von NichtBekannt112
Fassen wir mal zusammen, was wir bisher getan haben. Wir haben die Summenformel und eingebaut und sind jetzt bei
[latex]\sum\limits_{k=0}^{n+1} 2^{k}*\binom {n+1} k = [...] =^{I.V} 3^n+\sum\limits_{k=0}^{n} 2^{k}*\binom n {k-1} +2^{n+1}[/latex
Anmerkung : Siehe mein Beitrag weiter oben

Hast du diese Schritte alle nachvollziehen können? Weil ich möchte keine Berechnung hinklatschen, von denen du dann nicht alles verstanden hast, das soll ja nicht Sinn und Zweck hier sein smile

Neue Frage »

Antworten »

vollständige Induktion

Verwandte Themen