Fibonaccizahlen sind induktiv definiert. Überprüfen Sie die Abbildungen auf Injektivität, Surjektivität, Bijektivität.

Question

Aufgabe 3:

Die Fibonaccizahlen sind induktiv definiert als $F_{0}:=0, ~ F_{1}:=1$ und $F_{n+2}=F_{n}+F_{n+1}$ für $n \in \mathbb{N}_{0}$

Zeigen Sie für $n \in \mathbb{N}_{0}$ :

a) $\sum \limits_{k=0}^{n} F_{k}=F_{n+2}-1$

b) $\sum \limits_{k=0}^{n} F_{k}^{2}=F_{n} F_{n+1}$

Aufgabe 4

a) Überprüfen Sie folgende Abbildungen auf Injektivität, Surjektivität und Bijektivität:

(i) $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f(x)=x^{3}$

(ii) $f: \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f((x, y))=x+y$

(iii) $f: \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f((x, y))=2^{x}(2 y+1)-1$

b) Die Menge der ganzen Zahlen $\{\ldots,-2,-1,0,1,2, \ldots\}$ bezeichnen wir mit $\mathbb{Z}$.

(i) Gibt es eine Bijektion zwischen $\mathbb{N}$ und $\mathbb{Z}$ ? Falls ja, geben Sie eine solche Bijektion an.

(ii) Gibt es eine Bijektion zwischen $\mathbb{N}^{2}=\mathbb{N} \times \mathbb{N}$ und $\mathbb{Z} ?$ Falls ja, geben Sie eine solche Bijektion an.

Answer 1

Aufgabe 3 kannst du per vollst. Induktion zeigen.

Aufgabe 4 a) hast du doch konkrete Funktionen gegeben? Bei Injektivität und Surjektivität musst du dir vor allem Definitionsmenge und Bildmenge anschauen. Wo genau ist hier dein Problem?

b) Ja das sind alles abzählbare Mengen. Von N nach Z wählt man zum Beispiel die Abbildung, die die ungeraden natürlichen Zahlen auf die positiven ganzen Zahlen (und die 0) abbildet und die geraden natürlichen Zahlen auf die negativen ganzen Zahlen. Bei der 2. Abbildung schau dir mal Cantors Diagonalargument an.

Gruß

Comments

Aufagbe 4 ja die habe ich im nachhinein gesehen

Aber wie gesagt ich kann mit f(x,y) nicht viel anfangen.

Auch N null zu N null verstehe ich nicht.

Ich habe leider schon rinfachere induktionen nicht hinbekommen ich zweifle starkban mir das es mir bei einer schwerer gelingen wird.

---

Ich zeig mal was ich gemacht habe weiss nicht was ich mit F k machen soll.

Bitte Lösungen

Er braucht das bis morgen ;)

---

8ch glaub das ist blödsinn aber ein versuch ;) 

---

wo ist da die Induktion....mach doch erstmal den Induktionsanfang?

Den Induktionsschritt zeigst du (wie sonst auch) in dem du die Induktionsvoraussetzung verwendest. Ich zeig dir das beispielsweise einmal

IS: Wenn die Aussage für n gilt, also wenn $\sum_{k=0}^n F_k = F_{n+2} - 1$ gilt, dann gilt die Aussage auch für n+1, das heisst $\sum_{k=0}^{n+1} F_k = F_{n+3} - 1$ . 

$$\sum_{k=0}^{n+1} F_k =\left( \sum_{k=0}^n F_k \right) + F_{n+1} = F_{n+2} -1 + F_{n+1} = F_{n+1} + F_{n+2} - 1 = F_{n+3} -1$$

bei der letzten Gleichung wurde die Definition der fibonacci-Zahlen benutzt.

---

Ist das jetzt so richtig?

---

Ja, das ist ja das was ich aufgeschrieben habe.

Bei (3) steht da nach dem ersten Gleichheitszeichen ein "+1" am Ende oder im Index von F?

---

Ist der erste znd zweite schritt richtig?

---

Hatte das Bild vorher nicht gesehen, deswegen habe ich meinen Kommentar geändert siehe also dort,

bei (2) steht einfach nur $F_{n+3} -1$ und das ist unterstrichen....was willst du damit sagen?

---

mit n-> n+1 wollte ich den nächsten schritt zeigen

Und das andere umzu zeigen was nachzuweisrn ist.

---

Dann müsste da stehen

$$\sum_{k=0}^{n+1} F_k = F_{n+3} - 1$$

und nicht einfach nur $$F_{n+3} -1$$

das 1. ist eine Gleichung (und somit eine Behauptung)

das was du geschrieben hast, ist einfach nur ein Term.....

---

Also

Man schreibt am

Anfang

Ind. Anfang

Um dann ein wert einzusetzen und nachzuweisen das es für ein bestimmtes n gilt.

Ind. Behauptung

Da wird gezeigt was nachzuweisen ist

Ind. Beweis

Hier wird gerechnet oder nicht?

Bild wie ich es meinte

---

Ja und das war ja alles in Ordnung......ich versuchs noch mal

du hast bei (2) geschrieben (in dem Kasten)

$$n \to n+1$$

$$F_{n+3} - 1$$

Das macht doch so an sich keinen Sinn. So sieht es zum Beispiel vernünftigt aus

A(n) bedeutet: "die Aussage für n ist wahr"

Induktionsschritt:$$A(n) \Longrightarrow A(n+1)$$

zu zeigen: $\sum_{k=0}^{n+1} F_k = F_{k+3} - 1$

---

Ind. Schritt werde ich dann ab jetzt schreiben

Alles klar und dann noch zu zeigen ;)

---

Ja probier doch mal die b), dann sehen wir ob du es verstanden hast.

---

H9ffentlich ;)

Wird denn da was anderes m8t verlangt?

Oder a7f selben niveou?

---

Ist nicht wirklich schwieriger.

---

Wolte fragen ob es bishierher korrekt ist?

---

....1. wo kommt die + 1 bei (1) her?2. Hasst du überhaupt nicht verstanden was ich dir in den letzten 5 Posts geschrieben habe bei (2) steht wieder nur ein Term unter zu zeigen und keine Gleichung.
3. Wo kommt aufeinmal "-1" her, und das Quadrat? Was sind deine Gedanken hinter diesen Formulierungen....du hast vor allem die Aufgabenstellung nicht richtig mitgenommen...

---

Das erste hatte übersehen

(2) habe ich verbessert denke ich ;)

(3) ich habe ja aus aufgabe a gelernt das F_k = F_n+2  -1 ist.

Deswegen diese umformung.

Jetzt siweit richtig?

---

(1) ja

(2) ja (endlich ^^)

(3) Nein....du hast aus (a) gelernt, dass für die SUMME gilt

$$\sum_{k=0}^{n} F_k = F_{n+2} - 1$$

außerdem geht deine Summe im IS bis n+1, außerdem ist vor allem

$$(F_{n+2} - 1)^2 = \left( \sum_{k=0}^{n} F_k \right)^2 \neq \sum_{k=0}^{n} F_k^2$$

Du brauchst (a) für diese Aufgabe überhaupt nicht.

---

Darf ich hier sowas machen? Ausmultipliezieren und zwar F_k ?und dann summe mit fk?

---

Wie bitte? Ich weiß nicht was du meinst.

---

8ch hab es für mich selbst svhon beantwortet das geht nicht ;)

Bild schick mal was ich meien^^ man darf nur zahlen die zahlen die im mal stehen raus ziehen^^

---

8ch hab mal das versucht

---

....wie kommst du auf

$$F_k^2 = F_n F_{n+1} - F_{n+1}$$ ??

---

Ich habe summe f² k + fn+1 gemacht deswegen.

Ist das falsch?

---

Nein, mensch...gewöhn dir doch mal eine saubere Arbeitsweise an

Schreib immer die Summenzeichen wenn du sie brauchst...

Ich glaube schon, dass du fast auf dem richtigen Weg bist aber du erschwerst einem echt die Arbeit.

Schreib mir mal bitte was deiner Meinung nach

$$\sum_{k=0}^{n+1} F_k^2 = \sum_{k=0}^n F_k^2 + \_?\_$$

an Stelle des Fragezeichens stehen müsste?

---

Fn +1 habe ich geschrieben gehabt war das falsch?

---

Natürlich...wie sieht denn die Summe aus???Jedes Glied hat die Form $F_k^2$, demnach müsste an Stelle des Fragezeichens$F_{n+1}^2$ stehen und nicht $F_{n+1}$

---

Ah ja klar sry das hätte ich gewuusst meine kinzentration war wohl nicht ganz da^^

---

Ich hab das gemacht aber irgendwie...

---

Joa das geht doch so weit in Ordnung, du hast nur irgendwie eine andere Vorgehensweise, du zeigst die Gleichung in dem du auf die Induktionsvoraussetzung zurückschließt (ist aber nicht weniger verkehrt). Meistens sieht man eher, dass man die IV verwendet um die Aussage für n+1 zu zeigen:

$$\sum_{k=0}^n F_k^2 + F_{n+1}^2 = F_n F_{n+1} + F_{n+1}^2 = F_{n+1} (F_n + F_{n+1} ) = F_{n+1} F_{n+2}$$

siehst du den Unterschied in der Vorgehensweise? (Wie gesagt, deine Lösung ist nicht weniger falsch).

Gruß

---

Hä ist meine lösung jetzt richtig?

Und was meinst du mit IV?

Deins konnte ich nicht sehen es ladet langsam ich sehe nurirgendwelche zeichen ausser text^^

---

Ah ja jetzt sehe ich sie.

Muss man die linke seite nicht gleich mit n+1 machrn?dachte es muss sein^^

Du wirst vielleicht lachen

Aber ich habe das heute im schlaf also im traum gelöst^^

Ich kinnte einfach nicht aufhoeren

Ich danke dir

Ich hab zum ersten mal es alleine (mit hilfe a7ch von dir es hinbekimmrn.)

---

Ne muss man nicht. Schön, dass es bei dir geklappt hat :).

Weißt du viele dieser induktiven Beweise kann man dadurch beginnen, dass man das n+1-te Glied aus der Summe zieht, dann die Summe die nur noch bis n geht durch deine Induktionsvoraussetzung (das meine ich mit IV) ersetzt und dann ein wenig rumrechnest. Das führt zwar nicht immer zum Ziel, ist aber meist (vor allem bei den Standardaufgaben) sehr lehrreich.