Vollständige Induktion

25.11.2018, 10:48

Anne21

Vollständige Induktion

Hallo zusammen,

gerade sitze ich an einer Matheaufgabe und komme überhaupt nicht weiter. Vielleicht kann mir da jemand helfen:
Jemand behauptet, dass sich jede Quadratzahl $\begin{eqnarray*} n^{2} \end{eqnarray*}$ mit $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ als Summe der ersten n ungeraden natürlichen Zahlen darstellen lässt. Beweisen Sie dies durch vollständige Induktion. [Die n-te ungerade natürliche Zahl kann geschrieben werden als 2n-1]

Danke!

25.11.2018, 11:00

Leopold

Auf diesen Beitrag antworten »

Mach dir erst einmal die Behauptung klar.

Summe der ersten ungeraden Zahl:

$\begin{align*} 1 = 1 \end{align*}$

Summe der ersten beiden ungeraden Zahlen:

$\begin{align*} 1 + 3 = 4 \end{align*}$

Summe der ersten drei ungeraden Zahlen:

$\begin{align*} 1 + 3 + 5 = 9 \end{align*}$

Summe der ersten vier ungeraden Zahlen:

$\begin{align*} 1 + 3 + 5 + 7 = 16 \end{align*}$

und so weiter ...

Hast du die Aussage, die du beweisen sollst, verstanden?

25.11.2018, 11:11

Anne21

Auf diesen Beitrag antworten »

Ja, die Aussage habe ich verstanden.
Wie das formal aussehen soll, bin ich mir aber nicht sicher. Ich hätte es jetzt vielleicht so aufgeschrieben:
$\begin{eqnarray*} \sum\limits_{}^{} 2n- 1 = n^{2} \end{eqnarray*}$

Dann müsste ich die vollständige Induktion mit dem Induktionsanfang (n=1) beginnen. Wenn ich in die obige Gleichnung n=1 eingebe kommt dann 1=1 raus und somit korrekt.
Und dann kommt der Induktionsschritt (n+1). Bei dem Induktionsschritt komme ich nicht weiter.

Ist der Anfang denn korrekt?

25.11.2018, 11:18

Leopold

Auf diesen Beitrag antworten »

Das ist halb richtig, was in der Mathematik ganz falsch bedeutet. Um das Entscheidende hast du dich gedrückt, nämlich um den Index bei der Summation. Wenn du für die obere Grenze einen Term mit $\begin{align*} n \end{align*}$ verwendest, kannst du den Laufindex nicht ebenfalls $\begin{align*} n \end{align*}$ nennen.

$\begin{align*} n=1: \ \ 1 = 1^2 \end{align*}$

$\begin{align*} n=2: \ \ 1 + 3 = 2^2 \end{align*}$

$\begin{align*} n=3: \ \ 1 + 3 + 5 = 3^2 \end{align*}$

$\begin{align*} n=4: \ \ 1 + 3 + 5 + 7 = 4^2 \end{align*}$

Jetzt nenne den Laufindex $\begin{align*} k \end{align*}$ und versuche, die Summen links mit Hilfe des Summenzeichens zu schreiben:

$\begin{align*} \sum_{k= \ldots}^{\ldots} \left( \cdots \text{Term mit } k \cdots \right) \ \ = \ \ n^2 \end{align*}$

25.11.2018, 11:30

Anne21

Auf diesen Beitrag antworten »

Okay, ich bin da total unsicher. Vielleicht so:
$\begin{eqnarray*} \sum\limits_{k=1}^{n} 2k -1=n^{2} \end{eqnarray*}$

Oder ist das zu einfach gedacht? Big Laugh

25.11.2018, 11:35

Leopold

Auf diesen Beitrag antworten »

Auf jeden Fall ist es mißverständlich. Vermutlich meinst du

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

Ohne die Klammer ist es mißverständlich, weil man nicht weiß, ob die -1 zum Summenglied gehört oder außerhalb der Summe steht.

Und ob das jetzt stimmt, überprüfst du so: Nimm ein $\begin{align*} n \end{align*}$ , zum Beispiel $\begin{align*} n=3 \end{align*}$ . Dann steht da:

$\begin{align*} \sum_{k=1}^3 (2k-1) = 3^2 \end{align*}$

Und jetzt setze nacheinander in das Summenglied $\begin{align*} 2k-1 \end{align*}$ die Werte $\begin{align*} k=1, k=2, k=3 \end{align*}$ ein und addiere die so entstehenden Zahlen. Wenn das herauskommt, was du willst, hast du die Summe richtig aufgestellt, ansonsten mußt du noch einmal beginnen.

25.11.2018, 11:40

Anne21

Auf diesen Beitrag antworten »

oh ja, die Klammern sollten da wirklich hin!

Wenn ich das einsetzte kommt bei mir 9=9 raus. Also stimmt das schon mal!

Jetzt muss doch noch der Induktionsschritt mit n+1 folgen, oder?

25.11.2018, 12:10

Leopold

Auf diesen Beitrag antworten »

Vorne anfangen.

1. Induktionsanfang (Verankerung)

2. Induktionsschritt
a) Induktionsannahme, b) Induktionsbehauptung, c) Induktion

25.11.2018, 12:26

Anne21

Auf diesen Beitrag antworten »

Okay, also Induktionsanfang wäre ja n=1:

$\begin{eqnarray*} \sum\limits_{k=1}^{n= 1} (2\cdot 1-1) = 1^{2} \end{eqnarray*}$

und das passt schon mal.

Dann der Induktionsschritt (n+1(->Induktionsbehauptung) unter der Voraussetzung der Richtigkeit der Aussage für n (->Induktionsannahme))

Aber wie bekomme das jetzt richtig hingeschrieben?

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

So passt das ja gerade vor dem Gleich nicht.

25.11.2018, 12:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Ohne die Klammer ist es mißverständlich, weil man nicht weiß, ob die -1 zum Summenglied gehört oder außerhalb der Summe steht.

Streng nach Konvention weiß man es: Es gehört nicht dazu, d.h., es ist

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

Das wollen wir hier ja nicht, daher sind die Klammern bei $\begin{eqnarray*} \sum_{k=1}^{n} (2k-1) \end{eqnarray*}$ zwingend erforderlich.

25.11.2018, 13:59

Anne21

Auf diesen Beitrag antworten »

aber wie geht es denn jetzt weiter? Ich komme einfach nicht voran -.-

25.11.2018, 14:16

Leopold

Auf diesen Beitrag antworten »

2. a) Bei der Induktionsannahme schreibt man die Behauptung hin und nimmt sie für ein spezielles, aber nicht konkret benanntes $\begin{align*} n \end{align*}$ als gültig an:

$\begin{align*} \sum_{k=1}^n (2k-1) = n^2 \end{align*}$ für ein gewisses $\begin{align*} n \geq 1 \end{align*}$

2. b) Bei der Induktionsbehauptung ist in der Aussage $\begin{align*} n \end{align*}$ durch $\begin{align*} n+1 \end{align*}$ zu substituieren:

$\begin{align*} \sum_{k=1}^{n+1} (2k-1) = (n+1)^2 \end{align*}$ für den Nachfolger $\begin{align*} n+1 \end{align*}$ jenes $\begin{align*} n \end{align*}$ aus a).

2. c) Jetzt muß die Induktion durchgeführt werden. Dazu darfst du die Formel in a) als gültig ansehen und mußt die Formel in b) daraus folgern.

Bitte mache, solange du noch keine Fachfrau für vollständige Induktion bist, immer alle drei Schritte. Nimm dir die Zeit und schreibe 2.a) und 2.b) wirklich hin. Achte auch auf die Quantoren "für ein gewisses n" und "für den Nachfolger jenes n". Schreibe das hin. Gehe der bloßen Bequemlichkeit halber keine Abkürzungen! Sie führen direkt den Hang hinab in das dornenreiche Logik-Gestrüpp. Wenn du das Prinzip einmal verstanden hast, kann man das ein oder andere dann schneller erledigen.

Um nun 2.c) durchzuführen, beginne mit der linken Seite:

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

und forme sie nach gültigen Regeln so um, bis du die rechte Seite $\begin{align*} (n+1)^2 \end{align*}$ erhältst. Unterwegs mußt du irgendwo 2.a) einbauen. Dein Ziel muß daher sein, so umzuformen, daß die linke Seite von 2.a) entsteht.

25.11.2018, 14:41

Anne21

Auf diesen Beitrag antworten »

okay, also ich komme jetzt auf diesen Lösungsweg:

$\begin{eqnarray*} <=> \sum\limits_{k=1}^{n} (2k-1)+(2(n+1)-1)<br /> \end{eqnarray*}$

und $\begin{eqnarray*} \sum\limits_{k=1}^{n} (2k-1) \end{eqnarray*}$ ist die Induktionsvoraussetzung

$\begin{eqnarray*} <=> n^{2} + 2n+2-1<br /> \end{eqnarray*}$

$\begin{eqnarray*} <=> n^{2} + 2n+1 = (n+1)^{2} <br /> \end{eqnarray*}$

25.11.2018, 14:49

Leopold

Auf diesen Beitrag antworten »

Das ist ja gut gemeint, im Aufschrieb aber eine Katastrophe. Doppelpfeile $\begin{align*} \Leftrightarrow \end{align*}$ sind logische Verknüpfungen und stehen für die Äquivalenz von Aussagen. Du schreibst nun Terme und verbindest sie mit Doppelpfeilen. Das ist so, als würde jemand $\begin{align*} 3 \ \Leftrightarrow \ 2 \end{align*}$ schreiben. Was für einen Sinn soll das ergeben?
Für die Umformung von Termen steht in der Mathematik das Gleichheitszeichen. Und sonst nichts. Das war noch nie anders. Und es wird nie anders sein.
Hast du dagegen Gleichungen, die du Äquivalenzumformungen unterwirfst, dann bilden diese Gleichungen Aussagen. Und diese Aussagen werden durch Doppelpfeile zueinander in Beziehung gesetzt.

25.11.2018, 15:03

Anne21

Auf diesen Beitrag antworten »

okay, dann notiere ich das mit Gleichheitszeichen!

Danke für die Hilfe!

25.11.2018, 15:17

Leopold

Auf diesen Beitrag antworten »

Ein gut gemeinter Rat: Sei sorgfältiger mit deiner Sprache. In der Sprache drückt sich Denken aus. Wenn jemand oberflächlich redet, dann besteht immer der Verdacht, daß er auch oberflächlich denkt. Ein Beispiel: Du sagt

Zitat:

Original von Anne21
und $\begin{eqnarray*} \sum\limits_{k=1}^{n} (2k-1) \end{eqnarray*}$ ist die Induktionsvoraussetzung

Jetzt bin ich einmal ganz streng und sage: Das ist falsch. Richtig ist

$\begin{align*} \sum \limits_{k=1}^{n} (2k-1) = n^2 \end{align*}$ ist die Induktionsvoraussetzung.

Denn eine solche ist ja eine Aussage. Und ein Term wie $\begin{align*} \sum \limits_{k=1}^{n} (2k-1) \end{align*}$ ist nun einmal ein Term. Und Terme sind nie Aussagen.

Besser wäre gewesen, du hättest so formuliert:

Und auf $\begin{align*} \sum \limits_{k=1}^{n} (2k-1) \end{align*}$ kann jetzt die Induktionsannahme angewandt werden.

Und schon paßt alles.

Nix für ungut! Augenzwinkern

(Heute sind wir aber arg streng ...)

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen