| |
| Autor |
  Vollständige Induktion |
|
cassiopaia
Ehemals Aktiv 
Dabei seit: 15.10.2002
Mitteilungen: 469
 |  Themenstart: 2002-10-16
|
Folgendes:
Beweisen sie die folgenden Behauptungen mit vollständiger Induktion nach n.
a)Für jede ganze Zahl n ³1 mit n¹3 gilt n²£2n
b) Für die durch f1 = 1, f2=1,fn = fn-1+fn-2 definierten Fibonacci-Zahlen gilt, dass fn genau dann durch drei teilbar ist, wenn n durch vier teilbar ist.
Wer kann da helfen?
Danke im voraus
|
 Profil
|
Fabi
Senior 
Dabei seit: 03.03.2002
Mitteilungen: 4586
 | Beitrag No.1, eingetragen 2002-10-16
|
Hi!
a) Es ist 24 ³ 4², also ist die Aussage richtig für n=4.
Vorraussetzung: Sei die Annahme richtig für n.
Behauptung: Dann ist sie auch richtig für n+1.
Es ist also 2n ³ n²
Zu zeigen ist 2n+1 ³ (n+1)²
Es ist 2n+1 = 2n*2 > n²*2
Es ist aber 2n²> (n+1)² (da Ö2*n > n+1 für n ³ 4).
Also ist 2n+1 = 2n*2 > n²*2 > (n+1)² und damit 2n+1 ³ (n+1)².
qed.
b)
f4 = 3, also ist die Aussage richtig für n = 4.
Nun ist zu zeigen, dass sie, wenn sie für n gilt, auch für n+4 gilt:
fn+4 = fn+3+fn+2 = fn+2 + fn+1+fn+1+fn = 3fn+1 + 2fn.
fn ist nach Vorrausetzung durch drei teilbar, 3fn+1 wegen dem Vorfaktor 3 natürlich auch. Also ist auch ihre Summe durch 3 teilbar. Da ihre Summe gleich fn+4 ist, ist fn+4 durch 3 teilbar.
Jetzt das Problem mit dem "genau, dann" in der Behauptung:
Zu zeigen ist, dass, wenn fn (n > 3)durch 3 teilbar ist, n durch 4 teilbar ist.
Nun ist fn = 3fn-3+2fn-4
Also ist 2fn-4 = fn-3fn-3, und da sowohl fn als auch 3fn-3 durch 3 teilbar ist, muss auch fn-4 durch 3 teilbar sein.
Damit dann auch fn-8, ...
Sei n = 4a+b, wobei a,b beliebige Zahlen, b £ 5.
Wenn f4a+b durch 3 teilbar ist, muss auch fb durch 3 teilbar sein. Da aber von den ersten 4 Funktionswerten nur einer durch 3 teilbar ist, nämlich f4, muss b = 4 sein. Damit ist n durch 4 teilbar.
qed
Gruß
Fabi
|
Profil
|
cassiopaia
Ehemals Aktiv
Dabei seit: 15.10.2002
Mitteilungen: 469
| Beitrag No.2, vom Themenstarter, eingetragen 2002-10-16
|
Erstmal Danke für deine Antwort.
Hätte da aber eine Frage: Warum beginnst du die Induktion bei n=4 in beiden Fällen und nicht bei n=1?
Und kannst du mir folgende Zeile erklären: fn+4 = fn+3+fn+2 = fn+2 + fn+1+fn+1+fn = 3fn+1 + 2fn.
Vor allen Dingen die Zwischenschritte bis hin zum Endresultat.
Z.B Wie kommst du von fn+4 auf fn+3+fn+2 usw.
Vielen Dank im voraus
|
Profil
|
Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4586
| Beitrag No.3, eingetragen 2002-10-16
|
Hi!
Mit 4 beginne ich bei der ersten, weil das die erste Zahl ist, für die für alle größeren Zahlen die Behauptung stimmen sollen. Fange ich bei n = 1 an, gelingt der Induktionsschritt nicht, weil n ungleich 3 ist.
Bei der zweiten interessieren nur n, die durch 4 teilbar sind. Da ist das erste n =4. Únd induzieren tue ich dann eben nicht auf n+1, sondern auf n+4.
Bei den Umformungen habe ich nur fn = fn-1+fn-2 für alle n verwendet.
Gruß
Fabi
|
Profil
|
cassiopaia
Ehemals Aktiv
Dabei seit: 15.10.2002
Mitteilungen: 469
| Beitrag No.4, vom Themenstarter, eingetragen 2002-10-16
|
Ok soweit bin ich jetzt da durch gestiegen nur eins macht mir noch Probleme:
Es geht um folgende Zeilen:
Sei n = 4a+b, wobei a,b beliebige Zahlen, b £ 5.
Wenn f4a+b durch 3 teilbar ist, muss auch fb durch 3 teilbar sein. Da aber von den ersten 4 Funktionswerten nur einer durch 3 teilbar ist, nämlich f4, muss b = 4 sein. Damit ist n durch 4 teilbar.
1.Wie kommst du auf n = 4a +b und warum b£5?
Kann ich für n eine beliebige Gleichungsform wählen? Oder ist das von vornherein festgelegt?
MFG Cassio
|
Profil
|
Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4586
| Beitrag No.5, eingetragen 2002-10-16
|
Hi!
Ich sage einfach: jedes n hat eine Summendarstellung c+b so, dass c durch 4 teilbar ist (deshalb schreibe ich c = 4a, weil es, wenn c durch 4 teilbar ist, eine natürliche Zahl a gibt mit 4a = c).
b könnte ich beliebig wählen (uups, Fehler: b < 5), wenn aber b > 4, dann ziehe ich sozusagen den Faktor 4 ins a rüber und habe dann 4(a+1)+b-4, aber da a, b eh beliebig sind, kann ich das auch als 4a+b schreiben.
Gruß
Fabi
|
Profil
|
cassiopaia
Ehemals Aktiv
Dabei seit: 15.10.2002
Mitteilungen: 469
| Beitrag No.6, vom Themenstarter, eingetragen 2002-10-16
|
Okay soweit alles klar. Aber irgendwie sehe ich den Bezug nicht bei dir wenn n durch 4 teilbar ist, das genau dann fn durch 3 teilbar ist.
1.Du hast die 3 Teilbarkeit von 2fn-4 = fn - 3fn-3 bewiesen.
Dann gehst du über und beweißt für ein beliebiges n das es durch 4 teilbar ist.
Bei diesem Beweis benutzt du die 3 Teilbarkeit von f4a+b und fb wobei b=4 sein muss damit dass gilt.
Dann sagst du n wäre durch 4 teilbar. Also müsste dann laut Aufgabe fn durch drei teilbar sein.
Woran erkenne ich das dann aber jetzt? Kannst du das vielleicht noch mal verdeutlichen indem du z.B. Zahlen einsetzt?
Wäre toll!
MFG Cassio
|
Profil
|
Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4586
| Beitrag No.7, eingetragen 2002-10-17
|
Hi!
Da das eine "genau dann, wenn"-Behauptung ist, muss ich zwei Richtungen beweisen:
1. Aus n durch 4 teilbar muss fn durch 3 teilbar folgen. Das beweise ich bei b) in den ersten 6 Zeilen per Induktion.
Beispiele: f8 = 21, f12 = 144, beid es durch 3 teilbar, weil 8 und 12 durch 3 teilbar sind.
2. Aus fn durch 3 teilbar muss n durch 4 teilbar folgen. Das beweise ich sozusagen durch "Rückwärts-Induktion": Aus fn durch 3 teilbar folgt fn-4 durch 3 teilbar etc. Also ist fn-4a bei natürlichem a immer durch 3 teilbar. Jetzt kann ich a sowählen, dass n-4a = 1,2,3 oder 4. Da aber fn-4a durch 3 teilbar sein muss, kommt nur f$ in Frage. Ein beliebiges durch 3 teilbares fn hat also ein n, das druch 4 teilbar ist (n = 4+4+4+4+...)
Gruß
Fabi
|
Profil
|
| Das Thema wurde von einem Senior oder Moderator abgehakt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
