Induktion < Sonstiges < Schule < Mathe < Vorhilfe
|
Hallo!
Ich versuche mich an noch einem anderen induktiven Beweis. Diesmal soll gezeigt werden, dass
[mm] (x^3 [/mm] - x) mod 6 = 0
Im Prinzip sollte es doch darauf hinauslaufen, dass man zeigt, dass
(x + [mm] 1)^3 [/mm] - (x + 1) = [mm] a(x^3 [/mm] - x) mit a [mm] \in \IN, [/mm] oder?
Krieg ich aber wieder mal nicht gebacken :-(
Gruß und Danke,
Martin
|
|
| |
|
Hiho,
> Im Prinzip sollte es doch darauf hinauslaufen, dass man
> zeigt, dass
>
> (x + [mm]1)^3[/mm] - (x + 1) = [mm]a(x^3[/mm] - x) mit a [mm]\in \IN,[/mm] oder?
Nein, wie kommst du darauf?
Diesmal ist es eigentlich noch viel einfacher… es gilt: [mm] $(x+1)^3 [/mm] - (x+1) = x(x+1)(x+2)$
Nun zeige // überlege: x(x+1)(x+2) ist durch 2 und durch 3 teilbar… damit ist es auch durch 6 teilbar und damit ist $x(x+1)(x+2) = [mm] (x+1)^3 [/mm] - (x+1) [mm] \text{ mod } [/mm] 6 = 0$
Gruß,
Gono
|
|
|
| |
|
Hallo Gonozal,
dein Beweis ist aber kein Beweis per V.I., da er nicht auf die Induktionsveraussetzung zurückgreift.
Ohne VI geht's noch einfacher:
[mm] x^3-x=x(x^2-1)=x(x+1)(x-1), [/mm] und von den 3 aufeinanderfolgenden Zahlen ist mindestens eine gerade und mindestens eine eine Dreierzahl, somit ist das Produkt durch 2 und 3, also auch durch 6 teilbar.
Mit VI sollte das so aussehen:
x=1:
[mm] 1^3-1 [/mm] = 0 = 0 mod 6 (man kann sogar mit x=0 anfangen)
[mm] x\mapsto [/mm] x+1:
[mm] (x+1)^3-(x+1)= x^3+3x^2+3x+1-x-1=(x^3-x)+3(x^2+x)=(x^3-x)+3x(x+1)
[/mm]
Nach IV ist der 1. Summand (=1. Klammer) 0 mod 6.
3x(x+1) ist durch 3 und auch durch 2 teilbar, da x und x+1 zwei aufeinanderfolgende Zahlen sind, von denen eine gerade sein muss. Somit ist 3x(x+1) auch durch 6 teilbar, also ebenfalls 0 mod 6. Damit ist der gesamte Ausdruck 0 mod 6.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:48 Di 12.12.2017 | | Autor: | Gonozal_IX |
Hiho,
> dein Beweis ist aber kein Beweis per V.I.,
Das sehe ich anders…
> da er nicht auf die Induktionsveraussetzung zurückgreift.
Das muss er formal auch gar nicht.
Zu zeigen ist laut vollständiger Induktion für eine Aussage A(n), dass die Implikation $A(n) [mm] \Rightarrow [/mm] A(n+1)$ wahr ist.
Ist $A(n+1)$ als wahr gezeigt, so ist $A(n) [mm] \Rightarrow [/mm] A(n+1)$ wahr und damit gezeigt.
Damit gilt nach dem Prinzip der vollst. Induktion $A(n), [mm] n\in\IN$ [/mm] als gezeigt.
Gruß,
Gono
|
|
|
| |
|
> Hiho,
>
> > dein Beweis ist aber kein Beweis per V.I.,
> Das sehe ich anders…
>
> > da er nicht auf die Induktionsveraussetzung zurückgreift.
> Das muss er formal auch gar nicht.
Das sehe ich wieder anders.
Wenn ich mal genau so argumentieren wollte, könnte ich sagen: Jeder Beweis für alle natürliche Zahlen ist ein Beweis per V.I., denn wenn die Aussage für alle n [mm] \in \IN [/mm] gilt, gilt auch [mm]A(n) \Rightarrow A(n+1)[/mm]. Außerdem ist jeder direkte Beweis auch dann ein indirekter, denn aus A [mm] \Rightarrow [/mm] B folgt [mm] \neg [/mm] B [mm] \Rightarrow \neg [/mm] A.
Für mich ist die V.I. ein BeweisVERFAHREN, genau so wie der indirekte Beweis.
> Zu zeigen ist laut vollständiger Induktion für eine
> Aussage A(n), dass die Implikation [mm]A(n) \Rightarrow A(n+1)[/mm]
> wahr ist.
>
> Ist [mm]A(n+1)[/mm] als wahr gezeigt, so ist [mm]A(n) \Rightarrow A(n+1)[/mm]
> wahr und damit gezeigt.
Wozu dann n+1 statt n?
Wenn ich beweise, dass [mm] (a+1)^2 [/mm] = [mm] a^2+2a+1 [/mm] ist, ist es ein direkter Beweis, wenn ich aber [mm] (a+1+1)^2=(a+2)^2=a^2+4a+4=a^2+2a+1+2a+2+1=(a+1)^2+2(a+1)+1 [/mm] schreibe, ist es V.I.?
Oder wenn ich schreibe: "von n und n+1 ist eine der beiden Zahlen gerade" ist es eine normale Aussage, bei "von n+1 und n+2 ist eine der beiden Zahlen gerade" ist es V. I.?
>
> Damit gilt nach dem Prinzip der vollst. Induktion [mm]A(n), n\in\IN[/mm]
> als gezeigt.
>
> Gruß,
> Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Di 12.12.2017 | | Autor: | Gonozal_IX |
Hiho,
> Wenn ich mal genau so argumentieren wollte, könnte ich
> sagen: Jeder Beweis für alle natürliche Zahlen ist ein
> Beweis per V.I., denn wenn die Aussage für alle n [mm]\in \IN[/mm]
> gilt, gilt auch [mm]A(n) \Rightarrow A(n+1)[/mm].
Korrekt.
> Außerdem ist jeder direkte Beweis auch dann ein indirekter, denn aus A
> [mm]\Rightarrow[/mm] B folgt [mm]\neg[/mm] B [mm]\Rightarrow \neg[/mm] A.
Nein, aber eigentlich ist das der Sinn hinter einem indirekten Beweis… man zeigt [mm] $\neg [/mm] B [mm] \Rightarrow \neg [/mm] A$ und folgert daraus eben, dass dann auch $A [mm] \Rightarrow [/mm] B$ gilt.
Das trifft das Problem gerade aber nicht… sondern eher folgendes:
Für einen indirekten Beweis ist zu zeigen: [mm] $\neg [/mm] A [mm] \Rightarrow \neg [/mm] B$.
Ist [mm] $\neg [/mm] B$ nun eine Tautologie, würdest du diesen indirekten Beweis dann als "korrekt" ablehnen, weil du [mm] $\neg [/mm] A$ gar nicht benötigst?
> Für mich ist die V.I. ein BeweisVERFAHREN, genau so wie
> der indirekte Beweis.
Da stimme ich zu.
> Wozu dann n+1 statt n?
Das ist tatsächlich die Frage bei dieser Aufgabe…
Mal ein anderes Beispiel: Die Definition der Stetigkeit in [mm] $x_0$ [/mm] mit [mm] $\varepsilon$-$\delta$-Kriterium, [/mm] die da bekanntermaßen lautet:
[mm] $\forall\varepsilon>0\;\exists\delta>0\;\;|x-x_0| [/mm] < [mm] \delta \Rightarrow [/mm] |f(x) - [mm] f(x_0)| [/mm] < [mm] \varepsilon$
[/mm]
Nun möchte man das für die Funktion $f [mm] \equiv [/mm] 0$ zeigen.
Da gilt bekanntermaßen: $|f(x) - [mm] f(x_0)| [/mm] = 0 < [mm] \varepsilon$ [/mm] und das ganz ohne die "Voraussetzung" [mm] $|x-x_0| [/mm] < [mm] \delta$ [/mm] benutzt zu haben.
Ist die Implikation deswegen nicht gezeigt und die Funktion deswegen nicht stetig? Natürlich ist sie das trotzdem 
Und genau darauf wollte ich hinau: Rein formal ist bei der VI zu zeigen, dass "$A(n) [mm] \Rightarrow [/mm] A(n+1)$" gilt.
Zeigt man nun, dass A(n+1) allgemeingültig ist, so erfüllt das rein formal die Anforderungen der VI, sofern man einen Induktionsanfang findet.
Gruß,
Gono.
|
|
|
| |
|
> Zeigt man nun, dass A(n+1) allgemeingültig ist, so
> erfüllt das rein formal die Anforderungen der VI, sofern
> man einen Induktionsanfang findet.
Woazu braucht man dann einen Induktionsanfang, wenn man zeigt, dass A(n+1) gilt, ohne das aus "A(n) gilt" zu folgern?
Man muss dann nur fordern, dass es auch für n=0 gilt, und damit gilt es für alle Zahlen ab 1.
Wie kann etwas, das für alle n+1 gilt, ohne dass man es aus der Gültigkeit von A(n) gefolgert hat, nicht für alle n>1 gelten? Muss es doch dann automatisch. Und wozu benutze ich dann n+1 und nicht n im Beweis? Und wenn ich das dann tue: Was hat das noch mit V.I. zu tun?
Nochmal als Beispiel: Quadriert man eine gerade Zahl a, so ist das Ergebnis ebenfalls gerade.
Beweis ohne VI:
a gerade [mm] \Rightarrow [/mm] a=2n [mm] \Rightarrow a^2=4n^2=2(2n^2) [/mm] gerade.
Beweis mit VI nach Deiner Auffassung:
a gerade [mm] \Rightarrow [/mm] a=2(n+1) [mm] \Rightarrow a^2=4(n+1)^2=2(2(n+1)^2) [/mm] gerade.
Die Voraussetzung wurde nicht gebraucht, trotzdem ist es richtig. Ja. Aber was hat dieser Beweis im Entferntesten mit VI zu tun? Man braucht weder den Induktionsanfang, noch den Induktionsschritt n [mm] \mapsto [/mm] n+1.
Natürlich kann man sagen: Na, dann wurde das alles nicht gebraucht, so wie man bei deinem Stetigkeitsbeweis eben das [mm] \delta [/mm] nicht braucht. Aber dann kann ich auch sagen, dass mein obiges Beispiel ein Stetigkeitsbeweis ist, bei dem ich gerade mal die Stetigkeit, das [mm] \delta [/mm] und das [mm] \varepsilon [/mm] nicht brauchte.
Ein VI-Beweis ist ein solcher, bei dem in irgendeiner Weise benutzt wird, dass die Aussage vom Vorgänger auf den Nachfolger übertragen wird.
Wenn ich zeigen will, dass [mm] 7^n [/mm] - 1 teilbar durch 6 ist, kann ich eine "Polynomdivision" [mm] (7^n [/mm] - 1):(7 - 1) = [mm] 7^{n-1}+7^{n-2}+... [/mm] durchführen, und das ist kein Beweis durch VI.
Sage ich aber: Stimmt für n=1, soll für n stimmen, also [mm] 7^n [/mm] - 1 = 6k, damit gilt dann
[mm] 7^{n+1}-1= 7^{n+1}-7+6 [/mm] = [mm] 7(7^n-1)+6 [/mm] =(IV)k*6+6=(k+1)*6,
dann ist es ein Beweis mit VI!
|
|
|
| |
|
Hallo,
> Hallo!
> Ich versuche mich an noch einem anderen induktiven Beweis.
> Diesmal soll gezeigt werden, dass
>
> [mm](x^3[/mm] - x) mod 6 = 0
>
> Im Prinzip sollte es doch darauf hinauslaufen, dass man
> zeigt, dass
>
> (x + [mm]1)^3[/mm] - (x + 1) = [mm]a(x^3[/mm] - x) mit a [mm]\in \IN,[/mm] oder?
>
> Krieg ich aber wieder mal nicht gebacken :-(
Gonozal_IX hat dir die einfachste Möglichkeit aufgezeigt, den Sachverhalt zu beweisen. Nur ist das eben kein induktiver Beweis (den man hier nur machen sollte, wenn es ausdrücklich verlangt ist).
Mit vollst. Induktion fängst du wie immer mit dem Induktionsanfang an. Wähle dafür etwa x=1 und gehe damit in den Term ein, die Teilbarkeit durch 6 dürfte ja nicht allzu schwer zu erkennen sein...
Jetzt machst du im Prinzip das, was du vorgehabt hast, nämlich anstelle von x (x+1) zu setzen:
[mm] (x+1)^3-(x+1)
[/mm]
(was das mit deiner Gleichung werden soll, habe ich nicht verstanden, ich kann darin keinerlei Sinn erkennen).
Den obigen Term multiplizierst du jetzt aus. Die entstehenden Summanden sortierst du ein wenig um, so dass die Induktionsvoraussetzung vorkommt, also der Term [mm] (x^3-x). [/mm] Von diesem nimmst du die Teilbarkeit durch 6 an. Das was übrig bleibt, ist ebenfalls ein Term, für den man jetzt mit einer ähnlichen Logik wie der im Beweis von Gonozal_IX noch begründen muss, weshalb er für natürliche n durch 6 teilbar ist (das ist aber ziemlich offensichtlich nach einer kleinen Faktorisierung).
Meine Antwort habe ich verfasst ausschließlich für den Fall, dass du in einer Aufgabe tatsächlich aufgefordert bist, das per Induktion zu zeigen. Die Sinnhaftigkeit einer solchen Aufgabe darf allerdings angezweifelt werden.
Bei deinen ganzen Fragestellungen der letzten Zeit gibt es öfter Missverständnisse. Vielleicht wäre es gut, wenn du jeweils die Original-Aufgabe mit abtippen könntest?
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Di 12.12.2017 | | Autor: | sancho1980 |
Die Aufgabenstellung lautet:
"Zeigen Sie mithilfe vollständiger Induktion, dass
[mm] n^3 [/mm] - n durch 6 teilbar für alle n [mm] \in \IN
[/mm]
ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:49 Di 12.12.2017 | | Autor: | Gonozal_IX |
Hallo Diophant,
bitte meine Mitteilung zu HJKweseleit beachten 
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:13 Di 12.12.2017 | | Autor: | Diophant |
Hallo,
> bitte meine Mitteilung zu HJKweseleit beachten
in der Tat, die vollständige Induktion bekommt man bei dir 'serienmäßig mitgeliefert'.
Das ist aber schon etwas spitzfindig, und wenn man das für eine Übungs- bzw. Hausaufgabe verwenden möchte, sollte man es auch überzeugend begründen können...
Gruß, Diophant
|
|
|
|
