Übungen zu Grundlagen der Informatik Kapitel 7 Aufgabe 2 Es werden für n aus N_0 genau Z (n) = 2^n - 1 viele Züge ausgeführt. Beweis durch vollständige Induktion: Die Behauptung ist für n = 0,1,2 und 3 richtig, wie man sich leicht versichern kann. Sei nun die Behauptung für n aus N richtig. Dann gilt: Das Problem für n+1-viele Steine besteht nach dem rekursiven Algorithmus nach Abschnitt 7.7 aus - der Lösung für n Steine: Z(n) viele Züge - einem einzelnen Zug - der Lösung für n Steine: Z(n) viele Züge Somit erhalten wir: Z (n+1) = Z (n) + 1 + Z (n) = 2 * Z(n) + 1 = 2 * ( 2^n -1) +1 = 2^(n+1) -1 Damit gilt die Behauptung auch für n+1 un damit für alle n aus N.