Vollständige Induktion Verständnis Problem

Neue Frage »

26.04.2010, 21:31	Lentio	Auf diesen Beitrag antworten »
Vollständige Induktion Verständnis Problem Hallo, wir haben gerade kurz das Thema voll. Induktion angesprochen und irgendwie will das nicht in meinen Kopf. Wir haben eine Aufgabe bekommen, die wir lösen sollen und ich hab keinen Schimmer. Wäre nett wenn mir jemand helfen könnte oder mir vielleicht auch das Thema mit anderen Beispielaufgaben näher bringt. 1) $\begin{eqnarray} \sum\limits_{i=1}^n i\times 2^{i} = (n-1)2^{n+1} +2 \end{eqnarray}$ 2) Es gibt eine natürliche Zahl n0 € N, so dass gilt: $\begin{eqnarray} n^{2} \leq 2^{n} \end{eqnarray}$ für alle n>=n0 Danke EDIT von Calvin LaTeX korrigiert
26.04.2010, 21:41	Mulder	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Verständnis Problem Bleiben wir erstmal bei Aufgabe 1. Sauber aufgeschrieben: $\begin{eqnarray} \sum\limits_{i=1}^n i\cdot 2^i= (n-1)\cdot 2^{n+1}+2 \end{eqnarray}$ Soll das für alle natürlichen Zahlen gezeigt werden? Das wird üblicherweise mit angegeben. Ist dir das generelle Prinzip bei der vollständigen Induktion denn klar? Wenn nicht, solltest du dich dort erstmal einlesen. Ansonsten sind bei Wikipedia einige Beispiele zu sehen. Siehe hier. Versuch erstmal den Induktionsanfang, sprich zeige, dass die Formel für n=1 gilt. Setze also auf beiden Seiten n=1 und schau, ob sie identisch sind.
26.04.2010, 21:50	Lentio	Auf diesen Beitrag antworten »
danke für die schnelle Antwort. Hab vergessen zu schreiben $\begin{eqnarray} n\in \mathbb N \end{eqnarray}$ . Also der Induktionsanfang wäre dann: $\begin{eqnarray} \sum\limits_{k=1}^1 1\cdot 2^{1}= 0+2 \end{eqnarray}$ 2=2 wahr.
26.04.2010, 22:00	Mulder	Auf diesen Beitrag antworten »
Gut. Und hast du schon eine Idee, wie du nun weiter machen könntest?
26.04.2010, 22:18	Lentio	Auf diesen Beitrag antworten »
Nein, genau da scheiterts bei mir. jetzt müsste doch eigentlich der Induktionsschritt kommen. Aber wie der aussehen soll....?
26.04.2010, 22:25	Mulder	Auf diesen Beitrag antworten »
Zunächst mal kommt die Induktionsannahme. Dabei nehmen wir nun an, dass wir die Formel bereits für alle Zahlen bis n bewiesen haben. Wir setzen also voraus: Es gibt auf jeden Fall ein n, für das gilt: $\begin{eqnarray} \sum\limits_{i=1}^n i\cdot 2^i= (n-1)\cdot 2^{n+1}+2 \end{eqnarray}$ Für n=1 haben wir das ja schon bewiesen, als gibt es ein solches n ja auch auf jeden Fall. Das ist eben die Bedingung dafür, dass man die Induktionsannehme machen kann: Es zunächst für wenigstens eine Zahl zu zeigen. Und nun kommt in der Tat der Induktionsschritt. Wir untersuchen die Formel für den Fall n+1. Die Idee dahinter ist ganz einfach: Wenn es für n stimmt, und wir dann noch zeigen, dass es für n+1 auch stimmt, dann sind wir fertig. Warum? Für n=1 haben wir es schon bewiesen. Und dann zeigen wir, dass es, wenn es für n gilt, auch für n+1 gilt. Das können wir auf n=1 übertragen. Das heißt, es gilt dann auch für n+1=1+1=2. Das wiederum bedeutet, da wir es für n+1 schon bewiesen haben, dass es auch für n=2+1=3 gilt. Und so weiter und so fort... Ist das klar geworden? Eigentlich ist das Prinzip dahinter sehr simpel.
Anzeige

26.04.2010, 22:36	Lentio	Auf diesen Beitrag antworten »
Danke, vom Prinzip her, habe ichs verstanden. Bin ich dann mit einer einfachen Einsetzung von n+1 dann fertig: $\begin{eqnarray} n2^{n+2}+2 \end{eqnarray}$ ?
26.04.2010, 22:41	Mulder	Auf diesen Beitrag antworten »
Du musst zeigen, dass die Gleichheit für n+1 gilt. Das heißt, das musst du auf beiden Seiten auch einsetzen. Du verwendest dafür eben die Induktionsannahme. Die Summe auf der linken Seite teilst du auf, damit du damit rechnen kannst: $\begin{eqnarray} \sum\limits_{i=1}^{n+1} i\cdot 2^i = \sum\limits_{i=1}^n i \cdot 2^i + \sum\limits_{i=n+1}^{n+1} i\cdot 2^i \end{eqnarray}$
26.04.2010, 22:57	Lentio	Auf diesen Beitrag antworten »
So ungefähr? $\begin{eqnarray} \sum\limits_{i=1}^n i\cdot 2^{i} +(n+1)\cdot 2^{n+1} = ((n+1)-1)\cdot 2^{(n+1)+1}+2+(n+1)2^{n+1} \end{eqnarray}$
26.04.2010, 23:06	Mulder	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Verständnis Problem So ganz sehe ich gerade nicht, was du da machst. Wo kommt da das ((n+1)-1) her? Du musst doch nur 1 zu 1 das einsetzen, was du aus der Induktionsannahme kennst.
26.04.2010, 23:22	Lentio	Auf diesen Beitrag antworten »
Sorry, hatte mich nur an dem Bespiel von deinem Link nach wiki orientiert. Hab da wohl was missverstanden.Das Orangene hatte mich irritiert. muss dann auf der rechten Seite das stehen, was ich im 7. Beitrag gepostet habe?
26.04.2010, 23:34	Mulder	Auf diesen Beitrag antworten »
Ich helf dir mal, das nun ein bisschen aufzudröseln. Wir versuchen ja, die Gleichheit für n+1 zu zeigen. Dafür müssen wir die Summe $\begin{eqnarray} \sum\limits_{i=1}^{n+1} i\cdot 2^i \end{eqnarray}$ etwas aufteilen, denn so, wie es da steht, wissen wir über den Wert dieser Summe nichts. Also können wir darüber auch nichts sagen. Daher die Aufteilung $\begin{eqnarray} \sum\limits_{i=1}^{n+1} i\cdot 2^i = \sum\limits_{i=1}^n i \cdot 2^i + \sum\limits_{i=n+1}^{n+1} i\cdot 2^i \end{eqnarray}$ Denn jetzt wird die Summe viel angenehmer. Auf der rechten Seite stehen jetzt zwei Summen. Die linke Summe auf der rechten Seite ist genau die, die in der Induktionssannahme steht. Also kennen wir ihren Wert. Und die rechte Summe auf der rechten Seite besteht nur aus einem Glied, das ist also dann auch klar. In der Annahme stand: $\begin{eqnarray} \sum\limits_{i=1}^n i\cdot 2^i= (n-1)\cdot 2^{n+1}+2 \quad () \end{eqnarray}$ Das setzen wir jetzt genau so ein: $\begin{eqnarray} \sum\limits_{i=1}^n i \cdot 2^i + \sum\limits_{i=n+1}^{n+1} i\cdot 2^i = (n-1)\cdot 2^{n+1}+2 + \sum\limits_{i=n+1}^{n+1} i\cdot 2^i = \underbrace{(n-1)\cdot 2^{n+1}+2}_{\text{eingesetzt aus} \, ()} \, \, + \, \, (n+1) \cdot 2^{n+1} \end{eqnarray}$
27.04.2010, 17:58	Lentio	Auf diesen Beitrag antworten »
ah, der Groschen ist endlich gefallen. Danke für die Geduld. Jetzt stelle ich mich aber ziemlich dumm beim ausrechnen an: $\begin{eqnarray} = (n-1)2^{n+1} +2+ (n+1)2^{n+1} = n2^{n+1}-2^{n+1}+2+n2^{n+1} +2^{n+1} =n2^{n+1} +2+n2^{n+1} \end{eqnarray}$ wie kommt man weiter auf $\begin{eqnarray} = n2^{n + 2 } +2 \end{eqnarray}$ ?
27.04.2010, 18:03	Mulder	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Verständnis Problem Du musst nur noch ein bisschen zusammenfassen. Wie könnte man $\begin{eqnarray} n\cdot 2^{n+1} + n\cdot 2^{n+1} \end{eqnarray}$ denn noch schreiben?
27.04.2010, 18:36	Lentio	Auf diesen Beitrag antworten »
ich dachte man kann nur von der Form $\begin{eqnarray} <br /> = n2^{n + 1 } \cdot n2<br /> \end{eqnarray}$ zu $\begin{eqnarray} <br /> = n2^{n + 2} \end{eqnarray}$ zusammenfassen?
27.04.2010, 18:39	Mulder	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Verständnis Problem In der Grundschule könnte man vielleicht mal gelernt haben: a+a = 2a Analog: $\begin{eqnarray} n\cdot 2^{n+1} + n\cdot 2^{n+1} = 2\cdot n\cdot 2^{n+1} \end{eqnarray}$
27.04.2010, 18:46	Lentio	Auf diesen Beitrag antworten »
Peinlich, da hatte ich wohl einen Kurzschluss

Neue Frage »

Antworten »

Vollständige Induktion Verständnis Problem

Verwandte Themen