Vollständige Induktion

23.04.2010, 19:43	Mike99	Auf diesen Beitrag antworten »
Vollständige Induktion Meine Frage: Hallo, folgende zwei Probleme: Finden Sie den Fehler in den folgenden Induktionsbeweisen: 1. Aufgabe Behauptung: Für alle gilt: Sind a und b zwei natürliche Zahlen, deren Maximum gleich n ist (max (a,b) = n), so ist a = b Beweis: Induktionsanfang: Für n=0 ist die Behauptung offenbar richtig. Induktionsschritt: die Behauptung sei für n-1 nachgewiesen. Wir betrachten zwei natürliche Zahlen a, b mit max (a,b) = n. Man betrachtet nun die Zahlen a'=a-1 und b'=b-1. Es gilt dann max (a',b') = n-1 und damit auch die Induktionsannahme a'= b'. Daraus folgt a=b. 2. Aufgabe Behauptung: Befinden sich Personen in einem Raum, so haben alle am selben Tag Geburtstag. Beweis: Induktionsanfang: Für n=1 ist die Behauptung offenbar richtig. Induktionsschritt: Die Behauptung sei für n-1 nachgewiesen. Wir schicken von den n Personen, die sich im Raum befinden, eine hinaus. Wieder haben die verbleibenden Personen am selben Tag Geburtstag. Dies muss derselbe Tag wie vorhin sein. Also haben alle an diesem Tag Geburtstag. Meine Ideen: Könnte mir vielleicht jemand einen Tipp für den Lösungsansatz geben? Vor allem bei der 2. Aufgabe ist offensichtlich, dass sie nicht stimmt, aber wie kann ich das effektiv belegen? Mein Lösungsansatz ist, dass man nicht davon ausgehen kann, n-1 sei schon bewiesen. Damit ist der Induktionsschritt von grund auf falsch, was für beide Aufgaben zutrifft. Zur Aufgabe 2 habe ich leider noch keinen Lösungsvorschlag ... Könnte mir jemand dabei helfen, eine besser ausformulierte Lösung zu erstellen? Danke im Voraus.
23.04.2010, 21:06	wisili	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Zu 1. Die Behauptung ist falsch. Der Beweis ist fehlerhaft: Wenn a, b natürliche Zahlen sind, kann man nicht schliessen, dass a-1 und b-1 auch natürliche Zahlen sind; die Anwendung der Induktionsvoraussetzung ist deshalb nicht zulässig. Zu 2. Die Behauptung ist falsch. Der Beweis ist fehlerhaft: Der Induktionsschluss von n-1 auf n wäre für n>2 zwar zulässig, aber nicht für n=2 (weil die Teilmengen mit n-1 Elementen dann leeren Durchschnitt haben).
23.04.2010, 21:09	Equester	Auf diesen Beitrag antworten »
Hmm...wisili, wäre es möglich davon auszugehen, dass es sich bei a-1 und b-1 um natürliche Zahlen handelt, wenn ich weitere Induktionsschritte haben?
23.04.2010, 21:16	wisili	Auf diesen Beitrag antworten »
Ja, ich finde, der Induktionsschluss von n-1 auf n wäre für n>1 zulässig. Edit: Nein, ich nehme diese Antwort zurück: Es geht ja nicht um n, sondern um a und b und eine davon kann immer 1 sein.
23.04.2010, 21:17	Equester	Auf diesen Beitrag antworten »
Yep, das wars schon^^ Danke!
23.04.2010, 21:27	wisili	Auf diesen Beitrag antworten »
@Equester: Musste mich korrigieren, oben. Sorry.
Anzeige

23.04.2010, 21:37	Equester	Auf diesen Beitrag antworten »
Ahh ok...trotzdem danke! Ist einleuchtend!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »