vollständige induktion

07.02.2009, 17:52

easyone

Auf diesen Beitrag antworten »

vollständige induktion

Hallo
ich habe hier eine aufgabe zu vollständigen induktion.

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

nach induktionsanfang und induktionsschritt komm ich am ende auf

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

mein problem ist nun das ich nicht auf die form:

$\begin{eqnarray*} 2^{n+1}-n \end{eqnarray*}$ komme. entweder ich hab mich verrechnet oder ich krieg das mit den potenzgesetzen nicht so ganz hin

07.02.2009, 18:44

JustPassingBy

Auf diesen Beitrag antworten »

Hm, bist du sicher, dass du die Induktionsvorraussetzung richtig eingesetzt hast?

In jeden Summand steht nämlich noch ein n, d.h. bei n -> n+1 kommt nicht nur ein zusätzlicher Term hinzu, jeder Summand verändert sich.

Moment, ich rechne das gerade mal durch...

Edit:

Also ich habe mal die Induktion durchgeführt und anscheinend hast du die Induktionsvorraussetzung falsch eingesetzt.

Wenn du die Induktionsvorraussetzung richtig einsetzt, kommst du auf einen Term, der auf den ersten Blick nicht gleich das gewünschte Ergebnis ist.

Allerdings kannst du wieder per Induktion beweisen, dass der Term in der Tat gleich dem gewünschten Ergebnis ist.

Falls du immer noch Probleme hast, poste mal deinen Lösungsweg auf.

07.02.2009, 19:10

easyone

Auf diesen Beitrag antworten »

also ich hatte für

n --> n+1 :

(n-(n+1))2^n herausbekommen für den summanden.

ist es nicht so, dass ich für k n+1 einsetze und n lasse ich so stehen?

meine rechung sieht so aus:

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

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

=I.V $\begin{eqnarray*} 2^{n}-n-1 + (-1) 2^{n} \end{eqnarray*}$

07.02.2009, 19:34

JustPassingBy

Auf diesen Beitrag antworten »

Öhm, wie ich schon gesagt habe:
in jeden deiner Summanden steht ein n und deswegen kommt bei n->n+1 nicht nur ein extra Summand hinzu, alle vorherigen Summanden verändern sich.

07.02.2009, 19:42

easyone

Auf diesen Beitrag antworten »

meine rechung sieht so aus:

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

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

=I.V $\begin{eqnarray*} 2^{n}-n-1 + (-1) 2^{n} \end{eqnarray*}$

für die rechte seite hab ich ja auch n+1 eingesetzt aber im letzten schritt muss ich doch den rechten term so wie er in der aufgabenstellung steht also $\begin{eqnarray*} 2^{n}-n-1 \end{eqnarray*}$ mit dem summandem addieren.

07.02.2009, 20:06

AD

Auf diesen Beitrag antworten »

Ein Induktionsschritt sollte nicht den Eindruck erwecken, dass bereits die Induktionsbehauptung verwendet wird - das riecht nach Zirkelschluss. Kannst du deine Überlegungen mal in der Hinsicht überarbeiten, denn die machen genau diesen Eindruck (das geht schon in der ersten Zeile los).

Anzeige

07.02.2009, 20:41

easyone

Auf diesen Beitrag antworten »

hm ich verstehe nicht ganz wie ich an die aufgabe sonst herangehen soll. ich addiere doch praktisch einfach die induktionsvorraussetzung mit dem herausgezogenen summanden.

07.02.2009, 20:51

AD

Auf diesen Beitrag antworten »

Dann mal deutlicher, folgende zwei Möglichkeiten:

(A) Du formst die Induktionsbehauptung solange äquivalent um (unter Einsatz der Induktionsvoraussetzung), bis eine wahre Aussage dasteht.

(B) Du beweist die Induktionsbehauptung direkt durch klare mathematisch logische Folgerungen, natürlich ebenfalls unter Benutzung der Induktionsvoraussetzung.

Welche Strategie verfolgst du: (A), (B) oder noch was anderes? Ich kann's nicht erkennen, dazu erläuterst du zu wenig deine Umformungskette. unglücklich

unglücklich

07.02.2009, 21:03

easyone

Auf diesen Beitrag antworten »

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

der Induktionsanfang: n=1

$\begin{eqnarray*} 2^{0} \end{eqnarray*}$ =0

$\begin{eqnarray*} 2^{1}-1-1=0 \end{eqnarray*}$

damit ist der Induktionsanfang erfüllt.

Induktionsschritt: n---> n+1 sei für ein beliebiges n aus N

$\begin{eqnarray*} \sum_{k=1}^n~(n-k)2^{k-1}= 2^{n}-n-1 \end{eqnarray*}$ (I.V)

dann gilt auch:

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

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

=I.V $\begin{eqnarray*} 2^{n}-n-1 + (-1) 2^{n} \end{eqnarray*}$

07.02.2009, 21:12

hummel

Auf diesen Beitrag antworten »

Zitat:

Original von easyone

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

Nein, denn in der Summe links müsste auch überall mit (n+1) summiert werden.

07.02.2009, 21:15

AD

Auf diesen Beitrag antworten »

Zitat:

Original von easyone
dann gilt auch:

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

Das ist zu beweisen - wobei du vergessen hast, um das n+1 auch Klammern zu setzen:

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

Es ist verwirrend und schlechter Stil, mitten in die Gleichungskette diese Behauptung mit einzubauen. Das solltest du deutlich abgetrennt kennzeichnen, dass das erst noch zu beweisen ist!

Ok, ignorieren wir diesen Teil zunächst, weiter geht's:

Zitat:

Original von easyone
= $\begin{eqnarray*} \sum_{k=1}^n~(n-k)2^{k-1} + (n-(n+1))2^{n} \end{eqnarray*}$

Vollkommen falsch, du hast die Anmerkung von JustPassingBy wiederholt nicht beachtet:

Zitat:

Original von JustPassingBy
und deswegen kommt bei n->n+1 nicht nur ein extra Summand hinzu, alle vorherigen Summanden verändern sich.

Tatsächlich geht es also erstmal so weiter, wenn du denn unbedingt den letzten Summanden abtrennen willst:

$\begin{eqnarray*} = \left[ \sum_{k=1}^n ~ (n+1-k)2^{k-1} \right] + (n+1-(n+1))2^n \end{eqnarray*}$

Ich würde an der Stelle eher eine Indexverschiebung $\begin{eqnarray*} k=j+1 \end{eqnarray*}$ empfehlen, damit kommt man direkter auf die Induktionsvoraussetzung:

$\begin{eqnarray*} = \sum_{j=0}^n ~ (n+1-(j+1))2^{(j+1)-1} = \sum_{j=0}^n ~ (n-j)2^{j}= \cdots \end{eqnarray*}$ .

07.02.2009, 21:44

easyone

Auf diesen Beitrag antworten »

ich hab es erst nochmal versucht mit dem summanden, der wird ja dann schliesslich zu 0
, so dass nur noch $\begin{eqnarray*} 2^{n}-n-1 \end{eqnarray*}$ stehen bleibt, wie komme ich von da auf die Induktionsvorraussetzung?

07.02.2009, 21:46

AD

Auf diesen Beitrag antworten »

Was wird zu Null? Du erklärst zu wenig, so wird das nichts. unglücklich

unglücklich

07.02.2009, 21:54

easyone

Auf diesen Beitrag antworten »

wenn ich den summanden ausrechne $\begin{eqnarray*} (n+1-n-1)^{2n} \end{eqnarray*}$ dann wird der term ja zu 0, so dass ich nur noch $\begin{eqnarray*} 2^{n}-n-1 \end{eqnarray*}$ stehen habe.

07.02.2009, 21:59

AD

Auf diesen Beitrag antworten »

Ok, du meinst also den abgetrennten Summanden, den für $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ .

Wenn du nur von "Summand" redest, kann das hier alles mögliche sein - also bitte nicht so maulfaul, mehr erklären. Es nervt total, immer wieder nachhaken zu müssen...

-----------------

Wenn dir meine Idee mit der Indexverschiebung nicht behagt, es geht etwas umständlicher auch so;

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

Jetzt kannst du die IV verwenden, musst dich aber eben noch um die andere Summe kümmern.

07.02.2009, 22:17

easyone

Auf diesen Beitrag antworten »

um nochmal auf den abgetrennten summanden $\begin{eqnarray*} (n+1-n-1)^{2n} \end{eqnarray*}$ zurückzukommen. den hast du jetzt in der rechnung gar nicht mehr verwendet oder ist es so , dass ich die n+1 nur für das n einsetzte? sorry aber blick momentan gar nicht mehr durch unglücklich

unglücklich

07.02.2009, 22:31

AD

Auf diesen Beitrag antworten »

Den Eindruck habe ich auch. Dass dieser letzte Summand gleich Null ist, hatten wir doch schon geklärt, oder? Und außerdem lautet der nicht $\begin{eqnarray*} (n+1-n-1)^{2n} \end{eqnarray*}$ , sondern $\begin{eqnarray*} (n+1-n-1)\cdot 2^n \end{eqnarray*}$ , ...

Vielleicht schläfst du erstmal drüber.

07.02.2009, 22:36

easyone

Auf diesen Beitrag antworten »

ja ich denke auch ich werd es morgen nochmal weiter versuchen. aber danke schonmal für die hilfe Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »