vollständige Induktion, 3. Schritt

15.09.2008, 13:12

Dorika

Auf diesen Beitrag antworten »

vollständige Induktion, 3. Schritt

Hallo,

ich hab ein kleines Problem bei der vollst. Ind.
Und zwar hab ich
$\begin{eqnarray*} A(n)=\sum_{k=1}^n~k =\frac{n(n+1)}{2} \end{eqnarray*}$

Der erste Schritt ist ja, dass ich gucke, ob $\begin{eqnarray*} A(1) \end{eqnarray*}$ passt.
$\begin{eqnarray*} \sum_{k=1}^1~k = \frac{1\cdot2}{2}=1 \end{eqnarray*}$
Somit ist A(1) schonmal richtig.

Annahme: A(n) ist richtig.
$\begin{eqnarray*} A(n)=\sum_{k=1}^n~k = \frac{n(n+1)}{2} \end{eqnarray*}$

Schluss von A(n) auf A(n+1)
$\begin{eqnarray*} A(n+1)=\sum_{k=1}^{n+1}~k =\sum_{k=1}^n~k+(n+1) \end{eqnarray*}$

Woher kommt denn jetzt das $\begin{eqnarray*} (n+1) \end{eqnarray*}$ ?

$\begin{eqnarray*} \frac{n(n+1)}{2}+(n+1) \end{eqnarray*}$
dann HN, zusammenfassen und man kommt auf
$\begin{eqnarray*} \frac{n²+3n+2}{2} \end{eqnarray*}$

Formt man nun die rechte Seite um, ergibt sich:
$\begin{eqnarray*} \frac{(n+1)\cdot(n+2)}{2}=\frac{n²+3n+2}{2} \end{eqnarray*}$

Danke, lg

15.09.2008, 13:20

Jacques

Auf diesen Beitrag antworten »

Hallo,

Also die Frage ist, wie man von

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

auf die Zerlegung

$\begin{eqnarray*} (n + 1)(n + 2) \end{eqnarray*}$

kommt?

Beispielsweise durch Linearfaktorzerlegung:

Der quadratische Term

$\begin{eqnarray*} x^2 + px + q \end{eqnarray*}$

kann zerlegt werden in

$\begin{eqnarray*} (x - x_1)(x - x_2) \end{eqnarray*}$

wenn x1 und x2 die Lösungen sind von

$\begin{eqnarray*} x^2 + px + q = 0 \end{eqnarray*}$

Und dass -1 und -2 die Gleichung

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

lösen, kann man wiederum über den Satz des Vieta feststellen.

Wobei:

Eigentlich ist das Unsinn. Du musst doch nur zeigen, dass die beiden Terme identisch sind. Und das kannst Du genauso gut machen, indem Du vom Ergebnis ausgehst und einfach die Klammern auflöst. (hast Du ja getan)

// edit: Sorry, ich hatte die Frage vollkommen falsch verstanden!

Also dass

$\begin{eqnarray*} \sum_{k = 1}^{n + 1} k = \left (\sum_{k = 1}^n k\right) + (n + 1) \end{eqnarray*}$

gilt, ergibt sich direkt aus der Definition der Summe:

Statt bis zu n+1 zu addieren, kann man auch erst bis n addieren -- und dann noch den (n+1)-ten Summanden hinzufügen. Und dieser Summand ist hier gerade n+1.

15.09.2008, 13:35

Dorika

Auf diesen Beitrag antworten »

Prima, danke.
Klingt logisch, wenn man mal die Kurve gefunden hat...
Möchte nun eine Induktion zu folgeneder Summe machen:
$\begin{eqnarray*} \sum_{k=0}^n~q^{k}= \frac{1-q^{n+1}}{1-q} \end{eqnarray*}$

passt das k als Exponent oder hab ich falsch abgeschrieben?

Setzte ich nun auf der linken Seite n=1, dann erhalte ich $\begin{eqnarray*} q \end{eqnarray*}$
Mach ich das nun auf der rechten Seite, erhalte ich $\begin{eqnarray*} \frac{1-q²}{1-q} \end{eqnarray*}$

15.09.2008, 13:41

Huggy

Auf diesen Beitrag antworten »

Die Reihe muss mit k = 0 anfangen.

15.09.2008, 13:44

Dorika

Auf diesen Beitrag antworten »

ups, danke, das hab ich wohl beim latex vergessen zu ändern...
Sonst soweit ok? Wie sieht es denn mit A(1) aus?

15.09.2008, 13:46

Huggy

Auf diesen Beitrag antworten »

Wende mal auf 1 - q^2 die dritte binomische Formel an.

Anzeige

15.09.2008, 13:46

Jacques

Auf diesen Beitrag antworten »

Hm, wenn Du jetzt doch mit k = 1 beginnst, ist es wohl kein LaTeX-Problem. Augenzwinkern

Augenzwinkern

Also die Summe, die da steht, hat die folgende Formel:

$\begin{eqnarray*} \frac{q - q^{n + 1}}{1 - q} \end{eqnarray*}$

Oder Du musst eben bei k = 0 beginnen.

// Also eins von beidem musst Du korrigieren: Den Startindex oder die Formel.

15.09.2008, 14:05

Dorika

Auf diesen Beitrag antworten »

Ok, ich habs korrigiert.
Mein Fehler lag bei A(1)=q, was ja falsch ist. Ich hatte nämlich das $\begin{eqnarray*} q^{0} \end{eqnarray*}$ , was ja 1 ist, nciht mit berücksichtigt....
Und danke auch für die Idde mit der bin. Formel.
Somit ergibt sich A(1)=1+q

Dann nehme ich in Schritt 2 jetzt an, dass A(n) richtig ist. Aber warum nehme ich das an? Um die Voraussetzungen für die Induktion zu schaffen?

Nehme ich die linke Seite, erhalte ich als Ergebnis
$\begin{eqnarray*} \frac{2-q^{n+1}+n-qn-q}{1-q} \end{eqnarray*}$
Bei der rechten Seite
$\begin{eqnarray*} \frac{1-q^{n+2}}{1-q} \end{eqnarray*}$
Hm, kann ich das erste Ergebnis noch vereinfachen oder ist mir ein Fehler unterlaufen?

Edit: Nicht 1, sondern 2.

15.09.2008, 14:07

Huggy

Auf diesen Beitrag antworten »

Überprüf noch mal deine linke Seite!!!

15.09.2008, 14:11

Jacques

Auf diesen Beitrag antworten »

Also wenn Du bei k = 0 anfängst, dann ist der Induktionsanfang sinnvollerweise auch A(0). Natürlich kannst Du auch A(0) separat beweisen und dann nochmal bei A(1) beginnen. Aber warum eigentlich? Augenzwinkern

Augenzwinkern

Zitat:

Original von Dorika

Dann nehme ich in Schritt 2 jetzt an, dass A(n) richtig ist. Aber warum nehme ich das an? Um die Voraussetzungen für die Induktion zu schaffen?

Das ist das Prinzip der vollständigen Induktion:

Wenn eine Eigenschaft E(x) für eine natürliche Zahl n gilt -- und gleichzeitig gilt, dass E(k) => E(k + 1) für eine beliebige (feste) natürliche Zahl k mit $\begin{eqnarray*} k \geq n \end{eqnarray*}$ , dann folgt daraus:

Jede natürliche Zahl ab einschließlich n hat die Eigenschaft.

15.09.2008, 14:27

Dorika

Auf diesen Beitrag antworten »

Habe den Beitrag oben editiert. Komme immer wieder auf das gleich Ergebnis.
$\begin{eqnarray*} \sum_{k=0}^{n+1}~q^{k} =\sum_{k=0}^n~q^{k}+(n+1) =\frac{1-q^{n+1}}{1-q} +(n+1)= \frac{2-q^{n+1}+n-qn-q}{1-q} \end{eqnarray*}$

15.09.2008, 14:31

Jacques

Auf diesen Beitrag antworten »

Moment, da hast Du was verwechselt:

Es gilt

$\begin{eqnarray*} \sum_{k = 0}^{n+1}q^k = \left( \sum_{k = 0}^{n} q^k \right) + q^{n +1} \end{eqnarray*}$

Denn der (n+1)-te Summand ist doch diesmal q^(n+1), nicht n+1 (das war bei der vorigen Summe so)

// Als Schema:

$\begin{eqnarray*} \sum_{k = 0}^{n+1}q^k = \underbrace{q^0 + q^1 + q^2 + \ldots + q^n}_{=\sum_{k=0}^n q^k} + q^{n+1} \end{eqnarray*}$

Also

$\begin{eqnarray*} \sum_{k = 0}^{n+1}q^k = \left( \sum_{k=0}^n q^k \right) + q^{n+1} \end{eqnarray*}$

15.09.2008, 14:32

Huggy

Auf diesen Beitrag antworten »

Da ist schon der Anfang falsch.

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

15.09.2008, 14:36

Jacques

Auf diesen Beitrag antworten »

@ Huggy:

Willst Du im Thread weitermachen oder soll ich? Denn Dorika braucht die Antworten kaum in doppelter Ausführung. Augenzwinkern

Augenzwinkern

15.09.2008, 14:37

Dorika

Auf diesen Beitrag antworten »

Ach,
dann ists natürlich klar, man erhält
$\begin{eqnarray*} \frac{1-q^{n-2}}{1-q} \end{eqnarray*}$ auch auf der linken Seite.
Prima, danke, den Fehler hätt ich nie gefunden.

Ich denke mal, damit hat sich die Sach erübrigt. Aber danke für die doppelte Hilfe Augenzwinkern

Augenzwinkern

15.09.2008, 14:40

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Jacques
@ Huggy:

Willst Du im Thread weitermachen oder soll ich? Denn Dorika braucht die Antworten kaum in doppelter Ausführung. Augenzwinkern

Augenzwinkern

Hat sich erledigt, da Dorika verstanden hat.
Manchmal postet man dummerweise fast gleichzeitig.

15.09.2008, 14:45

Jacques

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy

Manchmal postet man dummerweise fast gleichzeitig.

Klar, deswegen die Frage. War nicht als Vorwurf gemeint oder so. smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »