Vollständige Induktion

28.01.2008, 00:32

andinho

Vollständige Induktion

hi@all...

muss eine induktions aufgabe lösen... leider blick ich bei diesem thema absolut nicht durch... ich habe also wirklich keine ahnung wie ich das lösen soll... ich weiß nur das ich mal n+1 einsetzen muss...

vielleicht kann einer von euch schritt für erklären wie so eine rechnung funktioniert und das beispiel vielleicht langsam mit mir durchgehen...

die aufgabe lautet folgendermaßen:

Zeigen Sie mit vollstandiger Induktion, dass für alle

$\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt $\begin{eqnarray*} n^{3}-n \end{eqnarray*}$ ist durch 6 teilbar

wieder mal vielen dank im voraus für euer bemühen... einem nicht so fitten menschen weiterzuhelfen...

lg,
andi

28.01.2008, 00:49

tigerbine

Auf diesen Beitrag antworten »

Trick: Binomische Formel

Zitat:

$\begin{eqnarray*} \forall~n \in \mathbb N:~n^{3}-n \end{eqnarray*}$

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

28.01.2008, 01:59

Michael1988

Auf diesen Beitrag antworten »

Ich führe Dir mal einen einfachen Beweis durch vollständige Induktion vor.
Es soll gezeigt werden, dass für alle natürliche Zahlen "n" gilt:
$\begin{eqnarray*} 1+2+3+...+n = 0,5*n*(n+1) \end{eqnarray*}$

Jetzt kommen immer zwei Arbeitsabschnitte:
1.) Induktionsanfang:
Du musst zeigen, dass für ein möglichst kleines "n", das Du dir aussuchen darfst, die Aussage gilt. [Das ist eigentlich immer leicht!]
Im Beispiel heißt das also: Der Induktionsanfang sei "1".
$\begin{eqnarray*} 1 = 0,5*1*(1+1) \end{eqnarray*}$
$\begin{eqnarray*} <=> 0 = 0 \end{eqnarray*}$
$\begin{eqnarray*} q.e.d. \end{eqnarray*}$
2.) Induktionsschritt:
Die Aussage gilt also in einem konkreten Fall, das hast Du im ersten Teil gezeigt. Jetzt geht es darum zu beweisen: "Wenn die Aussage für irgendeine Zahll gilt, dann gilt sie auch für die darauf folgende Zahl".
Mathematisch also: In der zu beweisenden Aussage wird die Variable, z.B. "n", mit "n+1" ersetzt und gezeigt, dass die Gleichung weiterhin gültig ist.
Hierbei setzt man dann irgendwann voraus, dass die zu beweisende Aussage für "n" bereits gilt.

Im Beispiel muss also jetzt gezeigt werden, dass Folgendes gilt:
$\begin{eqnarray*} (1) 1+2+3+...+n+[n+1] = 0,5*[n+1]*([n+1]+1) \end{eqnarray*}$
Dabei darfst Du voraus setzen, dass gilt:
$\begin{eqnarray*} (2) 1+2+3+...+n = 0,5*n*(n+1) \end{eqnarray*}$
Also ersetzt du den linken Teil von (1) bis auf "[n+1]" mit der rechten Seite von (2):
$\begin{eqnarray*} 0,5*n*(n+1)+[n+1] = 0,5*[n+1]*([n+1]+1) \end{eqnarray*}$
$\begin{eqnarray*} <=> 0,5*n+1 = 0,5*(n+2) \end{eqnarray*}$
$\begin{eqnarray*} <=> 0 = 0 \end{eqnarray*}$
$\begin{eqnarray*} q.e.d. \end{eqnarray*}$

Dadurch entsteht eine "Kettenreaktion": Da die Beispielaussage für n=1 gilt (Induktionsanfang), gilt sie mit dem Induktionsschritt auch für n=2. Und damit für n=3, damit für n=4, usw.
Beweis geführt!
Ich hoffe, ich konnte Dir helfen und du bekommst deine ursprüngliche Aufgabe jetzt hin smile

28.01.2008, 08:55

system-agent

Auf diesen Beitrag antworten »

@Michael

Du weisst schon, dass du auf die Art:
$\begin{eqnarray*} a=b\Leftrightarrow ...\Leftrightarrow 0=0 \end{eqnarray*}$
keine Gleichung beweisen kannst? (Denn aus einer falschen Aussage, zb $\begin{eqnarray*} a=b \end{eqnarray*}$ , kannst du alles folgern, also auch eine richtige Aussage zb $\begin{eqnarray*} 0=0 \end{eqnarray*}$ )

Du musst also von einer Seite der zu zeigenden Gleichung anfangen und dann durch irgendwelche Umformungen die rechte Seite erhalten, das heisst
$\begin{eqnarray*} a=...=\text{irgendwas dazwischen}=...=b \end{eqnarray*}$ , dann hast du die Gleichheit gezeigt !

Um das in deinem Beweis im Induktionsschritt anzuwenden:
Die Annahme ist, dass die Gleichheit
$\begin{eqnarray*} 1+2+...+n=\frac{n(n+1)}{2} \end{eqnarray*}$
für $\begin{eqnarray*} n\geq1 \end{eqnarray*}$ gilt.

Nun kommt der Schritt:
$\begin{eqnarray*} 1+2+...+n+(n+1)=\frac{n(n+1)}{2}+(n+1) \end{eqnarray*}$ (nach der Annahme)
Dann gilt weiterhin:
$\begin{eqnarray*} \frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$
Letzteres ist nun die Aussage für $\begin{eqnarray*} n+1 \end{eqnarray*}$ und damit ist der Induktionsschritt gezeigt

@andinho
Hat es nun mit der vorgeführten Rechnung und tigerbines Tipp geklappt?

28.01.2008, 19:18

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von system-agent
@Michael

Du weisst schon, dass du auf die Art:
$\begin{eqnarray*} a=b\Leftrightarrow ...\Leftrightarrow 0=0 \end{eqnarray*}$
keine Gleichung beweisen kannst? (Denn aus einer falschen Aussage, zb $\begin{eqnarray*} a=b \end{eqnarray*}$ , kannst du alles folgern, also auch eine richtige Aussage zb $\begin{eqnarray*} 0=0 \end{eqnarray*}$ )

Warum kann er nicht? Natürlich kann er das und das ist auch richtig. Kritisch wird es tatsächlich dann, wenn man folgert und nicht äquivalent umformt.

$\begin{eqnarray*} a=b\Leftrightarrow\ldots\Leftrightarrow 0=0 \end{eqnarray*}$

ist aber eine Äquivalenzumformung und damit mathematisch durchaus korrekt (ob es 'schön' ist, steht auf einem anderen Blatt).
Schwierig wird es, wie du richtig sagst, dann, wenn das Ganze so aussieht:

$\begin{eqnarray*} a=b\Rightarrow\ldots\Rightarrow 0=0 \end{eqnarray*}$ .

Damit hätte er $\begin{eqnarray*} a=b \end{eqnarray*}$ tatsächlich nicht bewiesen. Aber so hat er es nicht gemacht, sondern - wie oben - nur mit Äquivalenzumformungen, und dann ist nichts am Beweis auszusetzen.

28.01.2008, 19:26

Leopold

Auf diesen Beitrag antworten »

@ MSS

Das Problem bei dieser Beweisführung ist nur, daß ein nicht unbeträchtlicher Teil der Probanden nach meiner Erfahrung gewohnheitsmäßig $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ schreibt, obwohl vielleicht nur $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ gilt.

28.01.2008, 19:30

Duedi

Auf diesen Beitrag antworten »

Warum mit Induktion, wenns auch viel einfacher geht:
Wenn n-1 nicht durch 3 teilbar ist, n auch nicht, dann ist n+1 todsicher durch 3 teilbar (jede dritte Zahl ist durch 3 teilbar).
EDIT: Beziehe mich hier auf den Trick von Tigerbine

28.01.2008, 19:37

Dual Space

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
@Duedi:

Zitat:

Original von andinho
Zeigen Sie mit vollständiger Induktion, dass für alle ...

28.01.2008, 23:30

Mathespezialschüler

Auf diesen Beitrag antworten »

@Leopold
Das ist mir durchaus bewusst. Und ob Michael sich der Äquivalenz genau bewusst war, d.h. sich das wirklich überlegt hat, dem bin ich mir nicht einmal sicher.
Aber es ging mir auch nicht darum, diese Art von Beweisen zu beschönigen, eben weil sie dieses Problem mit sich bringen, welches du ansprichst, sondern darum, system-agents falsche Aussage zu entlarven, da sie ja zumindest bei diesem konkreten Fall völlig Fehl am Platz war und ich mir auch da nicht sicher bin, ob system-agent sich dem selbst klar ist, ob dies also wirklich nur eine "Leseschwäche" oder ähnliches war.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen