Autor |
Beitrag |
Miriam (Mmemim)
| Veröffentlicht am Dienstag, den 11. Dezember, 2001 - 17:15: |
|
Hi Ihr! Habe zwei Aufgaben für Euch! Ich hoffe, ihr könnt sie diesmal lösen. Wäre echt wichtig! Ich brauch doch die Punkte, sonst werde ich nicht zur Klausur zugelassen. Vielen Dank!!! 1. Beweisen Sie, dass die Summe zweier Quadrate x^2+y^2 , x,yeZ niemals kongruent 3 modulo 4 sein kann. 2. Für Fibonacci-Zahlen Fn zeige man Fn=1/wurzel5((1 + wurzel5/2)^n – (1 – wurzel5/2)^n). Liebe Grüße Miriam |
H.R.Moser,megamath
| Veröffentlicht am Mittwoch, den 12. Dezember, 2001 - 06:52: |
|
Hi Miriam, Zur Lösung Deiner zweiten Aufgabe müssen wir umfangreiche Vorbereitungen treffen und die Bezeichnungen klarstellen. 1.Fibonaccizahlen. Die Fibonaccizahlen, die im folgenden auftreten, seien wie folgt bezeichnet und numeriert: F1 = 1, F2 = 1, F3 = 2 , F4 = 3 , F5 = 5 , F6 = 8 , F7 = 13, F8 = 21,….Fn,…….. DasRekursionsgesetz wird als bekannte vorausgesetzt. 2 Reminiszenzen an den goldenen Schnitt. Es treten bei den Berechnungen von Teilungen nach dem goldenen Schnitt die beiden folgenden Terme auf: r = ½ * [wurzel(5) –1] t = ½ * [wurzel(5) +1] Zwischen r und t bestehen die einfachen Relationen t - r = 1 t + r = wurzel(5)................................................................(°) t * r = 1 t erfüllt die quadratische Gleichung in z: z ^ 2 – z – 1 = 0 (die andere Lösung ist z = - r) Daher gilt : t ^ 2 = t+1 °°°°°°°°°°°° r erfüllt die quadratische Gleichung in u: u ^ 2 + u –1= 0 (die andere Lösung ist u = - t) Daher gilt: r^2 = 1 – u °°°°°°°°°°°° 3 :Ein (t,r) –Kalkül mit überraschenden Ergebnissen (Linearisierung der Potenzen) Wir bilden Potenzen von t und r mit positiven ganzen Exponenten r ^1 = r r ^2 = 1 – r , daraus r ^3 = r*r^2 = r*(1-r) = r – r^2 = 2 * r –1 = F2 * r – F1........ ....(!) r ^4 = r*r^3 = r*(2*r-1) = 2*r^2 – r = 2 – 3* r = F3 –F4*r... ....(!) r^5 = r*r^4 = r*(2 – 3*r)=2*r – 3*r^2 = 5*r - 3 = F5*r – F4...(!) r^6 = r*r^5 = r* (5*r-3) =5*r^2 – 3*r = 5 – 8*r = F5 – F6*r...(!) ........................................................................................................ Allgemein gilt Für gerade n: r ^ n = F(n-1) – Fn * r ...........................................(I) °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Für ungerade n: r^n = Fn * r – F(n-1) ........................................(II) °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Bei den Potenzen von t hat man keine Vorzeichenprobleme Es gilt ( Herleitung analog ): t ^ 2 = t + 1 = F2 *t + F1 t ^ 3 = 2 * t + 1 = F3 *t + F2 t ^ 4 = 3 * t + 2 = F4 *t + F3 t ^ 5 = 5 * t + 3 = F5* t + F4 t ^ 6 = 8 * t + 5 = F6* t + F5 ......................................................................................... allgemein gilt für alle n = 2,3,4.................................... t ^ n = Fn * t + F(n-1)...................................................................(III) °°°°°°°°°°°°°°°°°°°°°° 4. Beweis der Behauptung Wir formulieren und beweisen den Satz a) für gerade n , b) für ungerade n a) n gerade ; sei an = 1/wurzel(5) * [ t ^ n – r ^ n ] °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Behauptung: an = Fn: das Folgeglied an stimmt mit der n-ten Fibonacc i- Zahl überein. Beweis. Nach der Formeln (I) und (III)gilt t ^ n - r ^ n = Fn * t +F(n-1) – F(n-1) +Fn * r = (t+r)*Fn = wurzel(5)*F(n), letzteres nach (°),somit an = Fn,wzbw °°°°°°°°°°°°°° b) n ungerade; sei bn = 1 / wurzel(5) * [ t ^ n + r ^n ] °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Behauptung: bn = Fn: das Folgeglied bn stimmt mit der n-ten Fibonacci - Zahl überein. Beweis. Nach der Formeln (I) und (II)gilt t ^ n + r ^ n = Fn * t +F(n-1) + Fn * r - F(n-1) = (t+r)*Fn = wurzel(5)*F(n), letzteres nach (°),somit bn = Fn,wzbw °°°°°°°°°°°°°°° Damit ist der Beweis erfolgreich überstanden ! Mit freundlichen Grüßen H.R.Moser,megamath. |
Lars Brünjes (Lbrunjes)
| Veröffentlicht am Mittwoch, den 12. Dezember, 2001 - 09:51: |
|
Hallo, Miriam! Die Lösung für Deine erste Aufgabe ist viel kürzer :-) Wir rechnen modulo 4! Zuerst überlegen wir uns, daß eine Quadratzahl stets kongruent 0 oder 1 modulo 4 ist:
| n mod 4 | n2 mod 4 | 0 | 0 | 1 | 1 | 2 | 4º0 | 3 | 9º1 | Damit folgt jetzt die Behauptung ganz leicht, denn wenn jede Quadratzahl kongruent 0 oder 1 modulo 4 ist, ist die Summe von zwei Quadratzahlen kongruent 0+0, 0+1, 1+0 oder 1+1 modulo 4, d.h. kongruent 0,1 oder 2 modulo 4 - und niemals kongruent 3 modulo 4! ---- Man kann die Aufgabe mit den Fibonacci-Zahlen übrigens auch ein wenig weniger "trickreich" lösen, als megamath das getan hat, wenn man die gute alte Lineare Algebra bemüht. Dazu bezeichne f:R2->R2 die R-lineare Abbildung mit f(a,b):=(b,a+b), d.h. die Abbildung, die bezüglich der Standardbasis des R2 durch die Matrix dargestellt wird. Es ist f(1,1)=(1,2) f(1,2)=(2,3) f(2,3)=(3,5) f(3,5)=(5,8) f(5,8)=(8,13), d.h. f1(1,1)=(1,2) f2(1,1)=(2,3) f3(1,1)=(3,5) f4(1,1)=(5,8) f5(1,1)=(8,13) und allgemein fn(1,1)=(Fn+1,Fn+2) (in megamaths Numerierung der Fibonacci-Zahlen). (Die Exponenten sollen Hintereinanderausführen von f bedeuten!) - die letzte Behauptung ist klar bzw. folgt durch eine triviale Induktion! So weit, so gut! Wenn wir also eine leichte Formel hätten, um die n-fache Hintereinanderausführung von f zu berechnen, könnten wir die Fibonacci-Zahlen leicht berechnen. Und von welchen linearen Abbildungen kann man die Potenzen leicht berechnen? Nun, auf jeden Fall von Diagonalmatrizen, denn ist A die Matrix so ist An einfach die Matrix Wir müssen unsere f also "nur" diagonalisieren, d.h. also zunächst einmal, wir müssen die Eigenwerte von f berechnen. Fangen wir mit dem charakteristischen Polynom von f an: c(T)=(T-0)(T-1)-1*1=T2-T-1=(T-[½(1+wurzel 5)])(T-[½(1-wurzel 5)]). Die beiden Eigenwerte von f sind also a:=-[½(1+wurzel 5) und b:=-[½(1-wurzel 5). Um f auf Diagonalgestalt zu bringen, müssen wir jetzt nur noch eine Basis des R2 aus Eigenvektoren finden, d.h. wir müssen zu a und b je einen Eigenvektor bestimmen: Sei v=(x,y) Eigenvektor zum Eigenwert a, dann folgt: a*v=f(v)Þ(ax,ay)=(y,x+y)Þy=ax (und x+y=ay). Setzen wir also zum Beispiel x:=1, so folgt y=a, und wir haben unseren Eigenvektor v gefunden, wir können v:=(1,a) setzen. Genauso bestimmen wir einen Eigenvektor w zum Eigenwert b, d.h. wir können setzen w:=(1,b). Bezeichne T die Basiswechselmatrix von der Basis {v,w} zur Standardbasis: Wir brauchen noch T-1, die Basiswechselmatrix in der anderen Richtung. Es ergibt sich: T-1=
-b/wurzel 5 | 1/wurzel 5 | a/wurzel 5 | -1/wurzel 5 | Jetzt sind wir fertig, müssen nur noch alles zusammenbauen! Oben haben wir gesehen, daß Fn die erste Komponente von fn-1(1,1) ist. Berechen wir die! Zunächst rechnen wir den Vektor (1,1) mit T-1 in die Basis aus Eigenvektoren um und erhalten den Vektor ((1-b)/wurzel 5,(a-1)/wurzel 5)=(a/wurzel 5,-b/wurzel 5). Jetzt müssen wir (n-1)-mal f anwenden, was ja jetzt ganz leicht ist, da f bezüglich dieser Basis Diagonalgestalt hat: Wir müssen nur die erste Komponente mit an-1, die zweite mit bn-1 multiplizieren, d.h. wir erhalten (an-1*a/wurzel 5,bn-1*(-b)/wurzel 5)=(an/wurzel 5,-bn/wurzel 5). Jetzt müssen wir mit T in die Standardbasis zurückrechnen und die erste Komponente ablesen, d.h. die Summe obiger Komponenten berechnen; wir erhalten: an/wurzel 5-bn/wurzel 5=(an-bn)/wurzel 5, und das sollte - zumindest, wenn wir dieselbe Numerierung für die Fibonacci-Zahlen benutzt haben, wir Ihr, die geforderte Lösung sein! Vielleicht erscheint all dies ein wenig kompliziert, aber es ist alles nur "Routine"-Lineare-Algebra - die einzige "Idee" ist, die lineare Abbildung f zu betrachten - der Rest ist dann nur eine nette Übung über Eigenwerte und Eigenvektoren :-) Ich hoffe, die Ausführungen helfen Dir ein wenig! Viel Erfolg bei Deiner Klausur!!!! |
H.R.Moser,megamath
| Veröffentlicht am Donnerstag, den 13. Dezember, 2001 - 08:15: |
|
Hi Mirim, Hi Lars, Im Namen aller, die etwas von linearer Algebra verstehen, danke ich Dir, Lars, für die von Dir präsentierte Lösung ; sie hat mir auch deshalb so gut gefallen, da - wie Du sagst- darin die gute alte Lineare Algebra zum Zuge kommt. Wie viel in diesem Fachgebiet steckt , möchte ich mit einer weiteren, besonders eleganten Beweismethode zur selben Frage zeigen. Ich hättet sie schon in meiner letzten Arbeit verwenden können, war mir aber nicht sicher, ob Miriam Kenntnisse auf diesem Gebiet hat. Wir stellen eine typische Aufgabe aus dem Anfängerunterricht, die so lautet: Im Vektorraum R^N aller reellen Zahlenfolgen {a(0),a(1),a(2),a(3),...}wird durch die zwei ersten Glieder a(0),a(1 ) aus R und die Rekursionsformel a(n+2) = a(n+1) + a(n) für n> =0 eine Zahlenfolge definiert. a) Beweise, dass die Menge aller Folgen, welche das Rekursionsgesetz erfüllen, einen Untervektorraum U von R^N bilden b) Bestimme die Dimension von U und ermittle eine Basis von U. c) Ermittle für a(0) = a(1) =1 eine geschlossene Formel für a(n). N.B.© ist gerade die zweite Aufgabe von Miriam ! Zur Lösung °°°°°°°°°°°° Zu a) Man zeigt leicht, dass die Kriterien für einen Unterraum erfüllt sind. Zu b) Ebenso leicht finden wir die Basis e1 ={1, 0,...........} e2 = {0,1,..........} fehlende Glieder werden der Reihe nach gemäss der Rekursionsvorschrift berechnet. Dass e1, e2 den Unterraum U erzeugen, wird durch vollständige Induktion nachgewiesen. Die Dimension ist somit 2. Zu c) Hauptteil Lars wird entschuldigen, wenn nun ein Trick angewendet wird, der darin besteht, als Basis von U nicht die oben erwähnte zu benützen, sondern dass nun geometrische Folgen zum Einsatz kommen. Zunächst ist abzuklären, wie eine solche Folge auszusehen hat. In der g-Folge {1,q,q^2,q^3,q^4,..........}muss wegen der Rekursion gelten: q^(n+2) = q^(n+1) + q^n ; da q ungleich null ist ,heben wir q ^ n weg; es bleibt die quadratische Gleichung in q übrig, die wir von meiner ersten Arbeit her kennen, nämlich: q ^ 2 - q – 1 = 0 mit den Lösungen q1 = t , q2 = - r (Die Bezeichnungen sind dieselben wie in der erwähnten Arbeit.) Die mit q1,q2 gebildeten geometrischen Folgen sind linear unabhängig und bilden somit eine Basis u , v , nämlich u = {1, t, t^2, t^3,.................}; v = {1, -r , r^2, - r^3,....} Folgerung : die Fibonacci-Folge Fn muss sich aus den Folgen u und v linear kombinieren lassen, d.h. es gilt Fn = f * u +g *v mit Konstanten f und g, für welche wir zwei Gleichungen anschreiben können, wenn wir die ersten beiden Komponenten der Folgen berücksichtigen. Diese Gleichungen lauten: f + g = 1 f * t – g * r = 1 Wir finden als Lösungen dieses Gleichungssystems: f = 1 / wurzel (5) * t = 1 / wurzel(5) * ½ [wurzel(5)+1] g = 1 / wurzel (5) * r = 1 / wurzel(5) * ½ [wurzel(5) -1] Daraus ergibt sich die Darstellung für die n-te Fibonacci-Zahl Fn = f * t ^ n + g* (-1) ^ n * r ^ n ,wie zuvor °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Mit freundlichen Grüßen H.R.Moser,megamath |
Lars Brünjes (Lbrunjes)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 10:00: |
|
Hallo, Miriam und megamath! Deine zweite Lösung, megamath, gefällt mir auch sehr gut!!! - Und ich habe wirklich rein gar nichts gegen Tricks, im Gegenteil - ich denke nur, daß man als Anfänger nicht den Eindruck bekommen sollte, daß man mathematische Aufgaben nur mit "Tricks" lösen kann - oft genügt es, einfach systematisch und nach "Routine" vorzugehen. Viele Grüße - Lars |
Miriam (Mmemim)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 16:51: |
|
Hallo Ihr beiden!!! Da ihr so schön die beiden anderen Aufgaben gelöst habt, würde ich Euch gern noch was fragen: Es ist nämlich noch eine dritte Aufgabe hinzu gekommen, die folgendermaßen lautet: Modifizieren Sie den Beweis des Euklid, um zu zeigen, dass unendlich viele Primzahlen p kongruent 3 mod 4 erfüllen. Beweis von Euklid: Es gibt unendlich viele Primzahlen. Beweis: Angenommen, es gäbe nur die Primzahlen p1=2, p2=3, p3=5,....,pn Definiere N=p1*p2*…*pn+1 ist durch keines der p1,p2,p3,...,pn teilbar! => N ist selbst Primzahl oder N besitzt Primteiler ungleich p1,p2,...,pn => Neue Primzahlen! Wie würde man das Lösen! Wäre ein Ansatz, wenn man sich erst übrlegen würde, welche Primzahlen kongruent 3 modulo 4 wären? Z.B. 3,7,11,19 usw. Aber wie verfahre ich dann weiter? Dann noch eine Frage zur 2 Aufgabe! Kann ich sie auch über Induktion lösen. Der Induktionsanfang würde ja stimmen, aber beim Schluß hab ich Probleme. Aber eigentlich müsste das doch gehen! Vielen Dank!! Lieber Gruß Miriam |
Miriam (Mmemim)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 16:52: |
|
Hallo Ihr beiden!!! Da ihr so schön die beiden anderen Aufgaben gelöst habt, würde ich Euch gern noch was fragen: Es ist nämlich noch eine dritte Aufgabe hinzu gekommen, die folgendermaßen lautet: Modifizieren Sie den Beweis des Euklid, um zu zeigen, dass unendlich viele Primzahlen p kongruent 3 mod 4 erfüllen. Beweis von Euklid: Es gibt unendlich viele Primzahlen. Beweis: Angenommen, es gäbe nur die Primzahlen p1=2, p2=3, p3=5,....,pn Definiere N=p1*p2*…*pn+1 ist durch keines der p1,p2,p3,...,pn teilbar! => N ist selbst Primzahl oder N besitzt Primteiler ungleich p1,p2,...,pn => Neue Primzahlen! Wie würde man das Lösen! Wäre ein Ansatz, wenn man sich erst übrlegen würde, welche Primzahlen kongruent 3 modulo 4 wären? Z.B. 3,7,11,19 usw. Aber wie verfahre ich dann weiter? Dann noch eine Frage zur 2 Aufgabe! Kann ich sie auch über Induktion lösen. Der Induktionsanfang würde ja stimmen, aber beim Schluß hab ich Probleme. Aber eigentlich müsste das doch gehen! Vielen Dank!! Lieber Gruß Miriam |
Miriam (Mmemim)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 16:52: |
|
Hallo Ihr beiden!!! Da ihr so schön die beiden anderen Aufgaben gelöst habt, würde ich Euch gern noch was fragen: Es ist nämlich noch eine dritte Aufgabe hinzu gekommen, die folgendermaßen lautet: Modifizieren Sie den Beweis des Euklid, um zu zeigen, dass unendlich viele Primzahlen p kongruent 3 mod 4 erfüllen. Beweis von Euklid: Es gibt unendlich viele Primzahlen. Beweis: Angenommen, es gäbe nur die Primzahlen p1=2, p2=3, p3=5,....,pn Definiere N=p1*p2*…*pn+1 ist durch keines der p1,p2,p3,...,pn teilbar! => N ist selbst Primzahl oder N besitzt Primteiler ungleich p1,p2,...,pn => Neue Primzahlen! Wie würde man das Lösen! Wäre ein Ansatz, wenn man sich erst übrlegen würde, welche Primzahlen kongruent 3 modulo 4 wären? Z.B. 3,7,11,19 usw. Aber wie verfahre ich dann weiter? Dann noch eine Frage zur 2 Aufgabe! Kann ich sie auch über Induktion lösen. Der Induktionsanfang würde ja stimmen, aber beim Schluß hab ich Probleme. Aber eigentlich müsste das doch gehen! Vielen Dank!! Lieber Gruß Miriam |
Miriam (Mmemim)
| Veröffentlicht am Freitag, den 14. Dezember, 2001 - 16:54: |
|
Hallo Ihr beiden!!! Da ihr so schön die beiden anderen Aufgaben gelöst habt, würde ich Euch gern noch was fragen: Es ist nämlich noch eine dritte Aufgabe hinzu gekommen, die folgendermaßen lautet: Modifizieren Sie den Beweis des Euklid, um zu zeigen, dass unendlich viele Primzahlen p kongruent 3 mod 4 erfüllen. Beweis von Euklid: Es gibt unendlich viele Primzahlen. Beweis: Angenommen, es gäbe nur die Primzahlen p1=2, p2=3, p3=5,....,pn Definiere N=p1*p2*…*pn+1 ist durch keines der p1,p2,p3,...,pn teilbar! => N ist selbst Primzahl oder N besitzt Primteiler ungleich p1,p2,...,pn => Neue Primzahlen! Wie würde man das Lösen! Wäre ein Ansatz, wenn man sich erst übrlegen würde, welche Primzahlen kongruent 3 modulo 4 wären? Z.B. 3,7,11,19 usw. Aber wie verfahre ich dann weiter? Dann noch eine Frage zur 2 Aufgabe! Kann ich sie auch über Induktion lösen. Der Induktionsanfang würde ja stimmen, aber beim Schluß hab ich Probleme. Aber eigentlich müsste das doch gehen! Vielen Dank!! Lieber Gruß Miriam |
H.R.Moser,megamath
| Veröffentlicht am Samstag, den 15. Dezember, 2001 - 11:20: |
|
Hi Miriam, Hier der versprochene Induktionsbeweis zur Fibonacci-Formel Vorbereitung Sei r = ½ * ( wurzel(5) - 1 ) t = ½ * ( wurzel(5) + 1 ) Weiter dient uns s = - r als nützlicher Term. Die folgenden Relationen haben wir bereits nachgewiesen: t + r = wurzel(5)...................................................................(0) r ^ 2 = 1 – r .......................................................................... (1) t ^ 2 = t +1............................................................................(2) Aus (1) folgt: s ^ 2 = s + 1...........................................................................(3) Die Behauptung lautet dann: Fn = F(n) = 1 / wurzel(5) * [ t ^ n - s ^ n ].............................(4) °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Beweis mit vollständiger Induktion Verankerung: F(1) = 1/ wurzel(5) * [t –s] = 1 / wurzel(5)* [t + r] = 1 nach (0) F(2) = 1/ wurzel(5) * [t ^ 2 – s^2] = 1 / wurzel(5)* [t - s] = 1 nach (2) und (3), somit: F(2) = 1/ wurzel(5) * [t –s] = 1 / wurzel(5)* [t + r] = 1 nach (0) Alles bestens ! Vererbung (Schluss von n-1 & n auf n+1) Induktionsvoraussetzung. die Formel gelte für n & n-1,d.h. es gelten die Beziehungen: F(n) = 1 / wurzel(5) * [ t ^ n - s ^ n ]..............................(5) F(n-1) = 1 / wurzel(5) * [ t ^(n-1) - s ^(n-1)]........................(6) Wir wollen zeigen, dass daraus folgt; F(n+1) = 1 / wurzel(5) * [ t ^(n+1) - s ^ (n+1) ].....................(7) Die letzte Beziehung sagt dann aus, dass die Formel auch für n + 1 gültig ist. Nachweis: nach dem Bildungsgesetz gilt: F(n +1) = F(n) + F(n-1) = 1 / wurzel(5) * [ t ^ n – t ^ (n-1) – {s ^ n – s ^ ( n -1)} ] = 1 / wurzel(5) * [ t ^ (n-1) * ( t + 1) – s ^ (n -1) * ( s +1 ) ] = 1 / wurzel(5) * [ t^(n-1) * t ^ 2 - s ^ (n –1 ) * s ^ 2 ].........(8) Zuletzt wurden die Gleichungen (2) und(3) gebraucht. Aus (8) folgt unmittelbar (7) ;damit ist der Induktionsbeweis erfolgreich beendet. Mit freundlichen Grüßen H.R.Moser,megamath. |
|