Kurs:Vorkurs Mathematik (Osnabrück 2009)/Arbeitsblatt zu Fibonacci und Quadratsummen

Die folgende Aufgabe kann man online bearbeiten, sie ist eine Wiederholung zum Binomischen Lehrsatz und zugleich eine kleine Einführung in Wikiversity. Halten Sie sich bitte an die Anweisungen.

Man begründe die Einzelschritte in der Gleichungskette im Beweis zu Fakt *****.

Gehen Sie dabei folgendermaßen vor.

1. Legen Sie auf Ihrer Benutzerseite (oder Gruppenseite) eine Unterseite an, indem Sie dort die Zeile

   [[/Binomischer Lehrsatz/Vergleichskette/Einzelbegründungen]]

   schreiben (d.h. Bearbeiten, Schreiben, Abspeichern; das / vorne und die eckigen Klammern sind wichtig).
2. Es erscheint ein roter Link. Klicken Sie auf den roten Link und geben Sie dort

    {{:Binomischer Lehrsatz/Vergleichskette/Begründungsfenster}}

   ein.

3. Es erscheint der Beweis der Binomischen Formel. Wenn Sie auf eines der Gleichheitszeichen gehen, erscheint ein roter Link. Gehen Sie auf diesen roten Link und geben Sie dort die Begründung für dieses Gleichheitszeichen ein.

Fibonacci-Zahlen

Aufgabe

Kaninchen werden bekanntlich immer zur Monatsmitte geboren, die Tragzeit beträgt einen Monat und die Geschlechtsreife erreichen sie im Alter von zwei Monaten. Jeder Wurf besteht aus genau einem Paar, und alle leben ewig.

Wir starten im Monat ${}1$ mit einem Paar, das einen Monat alt ist. Es sei ${}f_{n}$ die Anzahl der Kaninchenpaare im ${}n$-ten Monat, also ${}f_{1}=1$, ${}f_{2}=1$. Beweise durch Induktion die Rekursionsformel

${}f_{n+2}=f_{n+1}+f_{n}\,.$

Diese Zahlfolge nennt man die Folge der Fibonacci-Zahlen. Wie viele der ${}f_{n}$ Paare sind im ${}n$-ten Monat reproduktionsfähig?

Aufgabe

Beweise durch Induktion die Binet-Formel für die Fibonacci-Zahlen. Diese besagt, dass

${}f_{n}={\frac {{\left({\frac {1+{\sqrt {5}}}{2}}\right)}^{n}-{\left({\frac {1-{\sqrt {5}}}{2}}\right)}^{n}}{\sqrt {5}}}\,$

gilt (${}n\geq 1$).

Aufgabe *

Beweise durch Induktion die Simpson-Formel oder Simpson-Identität für die Fibonacci-Zahlen ${}f_{n}$. Sie besagt (für $n\geq 2$)

${}f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\,.$

Aufgaben zu Quadratsummen

Aufgabe

Finde die kleinste natürliche Zahl, die sich auf mehrfache Weise als Summe von zwei Quadratzahlen darstellen lässt.

Aufgabe

Bestimme für jede natürliche Zahl ${}n\leq 30$, ob sie sich als eine Summe von drei Quadratzahlen darstellen lässt.

Aufgabe

Bestimme für jede natürliche Zahl ${}n\leq 10$, auf wie viele verschiedene Arten sie sich als Summe von vier Quadratzahlen darstellen lässt, d.h. man bestimme die Anzahl der ${}4$-Tupel

$(x_{1},x_{2},x_{3},x_{4})\in \mathbb {Z} ^{4}{\text{ mit }}x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=n.$

Aufgabe

Zu einer natürlichen Zahl ${}n$ bezeichne ${}r(n)$ die Anzahl der Möglichkeiten, sie als Summe von vier Quadratzahlen darzustellen, d.h. ${}r(n)$ ist die Anzahl der ${}4$-Tupel

$(x_{1},x_{2},x_{3},x_{4})\in \mathbb {Z} ^{4}{\text{ mit }}x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=n.$

Es sei ${}u$ eine ungerade positive Zahl. Beweise die Beziehung

$r(2u)=3r(u).$

Aufgabe *

Zeige, dass eine ganze Zahl ${}n$ genau dann die Differenz zweier Quadratzahlen ist, wenn der Exponent von ${}2$ in der Primfaktorzerlegung von ${}n$ gleich ${}0$ oder ${}\geq 2$ ist.

Aufgaben zu Relationen

Aufgabe

Skizziere ein Teilerdiagramm für die Zahlen ${}12,15,16,20$ sowie all ihrer positiven Teiler.

Aufgabe

Es sei ${}M$ eine Menge und ${}I$ die Menge der echten Teilmengen von ${}M$, also

$I={\left\{T\subseteq M\mid T\neq \emptyset {\text{ und }}T\neq M\right\}}.$

Diese Menge ist durch die Inklusion eine geordnete Menge. Bestimme die minimalen und die maximalen Elemente von ${}I$.

Aufgabe

Zeigen Sie, dass für Relationen die Konzepte Reflexivität, Symmetrie und Transitivität voneinander unabhängig sind.

Aufgabe *

Es sei ${}M$ eine Menge mit ${}n$ Elementen. Bestimme die Anzahl der Relationen auf ${}M$, die

1. reflexiv
2. symmetrisch
3. reflexiv und symmetrisch

sind.

Aufgabe

Es seien ${}A$ und ${}B$ Mengen. Es sei weiter

${}A\times B:={\left\{(x,y)\mid x\in A,\,y\in B\right\}}\,$

das kartesische Produkt von ${}A$ und ${}B$. Eine Relation von ${}A$ nach ${}B$ ist eine Teilmenge ${}R\subseteq A\times B$.

Ist ${}R$ eine Relation von ${}A$ nach ${}B$ und ${}S$ eine Relation von ${}B$ nach ${}C$, so ist die Komposition

${}S\circ R:={\left\{(x,z)\in A\times C\mid \exists y\in B{\text{ mit }}(x,y)\in R{\text{ und }}(y,z)\in S\right\}}\,$

Weisen Sie nach, dass die Komposition von Relationen assoziativ ist, also die Gleichheit

${}T\circ (S\circ R)=(T\circ S)\circ R\,$

gilt.

Aufgabe

Es seien ${}A$ und ${}B$ Mengen. Es sei weiter

$A\times B\colon \!=\{(x,y)\,\vert \,x\in A,\,y\in B\}$

das kartesische Produkt von ${}A$ und ${}B$.

Eine Relation von ${}A$ nach ${}B$ ist eine Teilmenge ${}R\subseteq A\times B$. Die Umkehrrelation ${}R^{-1}$ ist gegeben durch

$(y,x)\in R^{-1}\,\,\Leftrightarrow \,\,(x,y)\in R.$

Eine Abbildung von ${}A$ nach ${}B$ ist eine Relation ${}f$ von ${}A$ nach ${}B$ mit der Eigenschaft, dass für jedes Element ${}x\in A$ genau ein Element ${}y\in B$ mit ${}(a,b)\in f$ existiert. Zeigen Sie, dass die Umkehrrelation einer Abbildung ${}f$ genau dann eine Abbildung ist, wenn ${}f$ bijektiv ist.