Zeige, dass folgender Beweis fehlerhaft ist:

Behauptung: Auf einer Party mit ´n ≥ 1´ Gästen haben alle denselben Namen.

Induktionsbasis: Wenn auf einer Party nur ein Gast ist, ist die Aussage wahr (weil es nur einen Namen gibt).

Induktionsschritt: Seien auf einer Party ´n + 1´ Gäste. Wir schicken einen raus. Dann sind auf dieser Party nur noch ´n´ Gäste. Nach Induktionsvoraussetzung haben all diese ´n´ Gäste den gleichen Namen. Nun holen wir den Gast der draußen steht wieder rein und schicken einen anderen Gast raus. Nun haben nach Induktionsvoraussetzung wieder alle den gleichen Namen. Also müssen alle ´n + 1´ Gäste den gleichen Namen haben. Daraus folgt, dass alle Gäste auf einer Party gleich heißen.

Solution

  • Durch das zweite Herausschicken betrachtet man wieder nur eine Person und nicht ´n + 1 = 2´ Personen. Somit wird die Anforderung an den Induktionsschritt nicht erfüllt und es kann auch keine Aussage über die Richtigkeit der Behauptung gemacht werden.

  • URL:
  • Language:
  • Subjects: math
  • Type: Proof
  • Duration: 20min
  • Credits: 3
  • Difficulty: 0.5
  • Tags: hpi induction
  • Note:
    HPI, Mathematik I - Diskrete Strukturen und Logik, Wintersemester 2012/2013
  • Created By: adius
  • Created At:
    2013-04-12 16:49:14 UTC
  • Last Modified:
    2014-07-21 04:18:53 UTC