(Twitter)
Moin!
Der Induktionsanfang ist ja schon vorgegeben, für \( n = 0 \) hat A 0 Elemente und Damit gibt es nur eine Abbildung. Da auch \( m^0 = 1 \) gilt, stimmt das so weit.
Für den Induktonsschritt wissen wir also schon, dass die Aussage für ein beliebiges (aber festes) n gilt, also dass die Anzahl der Abbildungen einer n-elementigen Menge in die (m-elementige) Menge B genau \( m^n \) beträgt.
Betrachten wir nun eine Menge A mit (n+1) Elementen, dann müssen wir zeigen, dass es aus dieser Menge exakt \( m^{n+1} \) Abbildungen nach B gibt.
Nach Annahme ist A nciht leer, also isolieren wir ein Element \(a \in A \) und betrachten die Menge \( A' := A \backslash \{a\} \), also die Menge, die entsteht wenn wir das Element a aus A entfernen.
Aus dieser gibt es nach Induktionsvoraussetzung exakt \(m^n\) Abbildungen nach B. Jede von diesen kann nun fortgesetzt werden, indem man den Wert der Abbildung für a festlegt. Aber wieviele Möglichkeiten gibt es dafür? Und wie kombiniert man diese...?
Viel Erfolg!
Softwarearchitekt, Punkte: 115
1) Induktionsanfang: Beweise die Aussage für einen geeigneten Startwert (meistens n = 0 oder n = 1). Dies ist oft leicht und kann durch Einsetzen erledigt werden.
2) Induktionsschritt: Hier ist der trickreiche Teil: Man versucht, die Aussage für eine Zahl zu zeigen und dabei verwendet man die Annahme, dass sie für den Vorgänger gilt. Dabei ist es unerheblich, ob man von (n-1) auf n schließt oder die Aussage für (n+1) beweist, indem man sie für n annimmt.
Simples Beispiel: Zeige per Induktion über n, dass die Summe der ersten n ungeraden Zahlen exakt \( n^2 \) ist, oder in Formeln, zeige \( \sum_{k=1}^n 2k-1 = n^2 \)
Der Induktionsanfang (n = 1) ist einfaches Einsetzen. Im Induktionsschritt muss man diese Gleichung für den Wert (n+1) zeigen: \( \sum_{k=1}^{n+1} 2k-1 = (n+1)^2 \)
Man darf aber verwenden, dass die Sache für n schon gilt, also rechnet man einfach nach, indem man den letzten Summanden abspaltet:
\( \sum_{k=1}^{n+1} 2k-1 = \sum_{k=1}^{n} (2k-1) + 2n + 1 = n^2 + 2n + 1 = (n+1)^2 \)
Alles klar? ─ dr_lars 29.05.2019 um 10:42
Vielen vielen Dank für deine super tolle Antwort! Ich glaube. dass ich verstanden habe, aber ich muss noch etwas üben. Kannst du mir vlt. Tipps geben, wie ich mit ähnlichen Aufgaben umgehen sollte?
Herzichen Dank nochmal und Gruß
Eva ─ evatsigkana 28.05.2019 um 17:10