Vertiefung - Berechnungsformeln
Zur Orientierung
Im letzten Abschnitt wurde die Anzahl von Zügen (das sind die Scheibenbewegungen) bestimmt, die man beim Umschichten eines $n$-Scheiben-Turm benötigt. Man erhält für $n = 1; 2; 3; 4; 5; \dots$ folgende Zuganzahlen:
$1; 3; 7; 15; 31; ...$
In diesem Abschnitt entwickeln wir Formeln zur Berechnung dieser Zuganzahlen.
Das Berechnungsverfahren analysieren
Aufgabe 1
Sicher ist dir auch schon aufgefallen, dass man die Folgenglieder schrittweise berechnen kann.
$a_1 = 1$
$a_2 = 2 \cdot a_1 + 1$
$a_3 = 2 \cdot a_2 + 1$
$a_4 = 2 \cdot a_3 + 1$
$a_5 = 2 \cdot a_4 + 1$
...
(a) Ergänze die nächste Berechnungsformel.
(b) Beschreibe die Berechnungen jetzt allgemein. Ergänze hierzu die Formel für $a_n$.
$a_1 = 1$
$a_n =$ ... (für $n = 2, 3, ...$)
(c) Kontrolliere die Formel im folgenden Applet.
Aufgabe 2
Die Folgenglieder kann man auch direkt berechnen.
$a_1 = 2^0-1$
$a_2 = 2^1-1$
$a_3 = 2^2-1$
...
(a) Ergänze die nächste Berechnungsformel.
(b) Beschreibe die Berechnungen jetzt allgemein. Ergänze hierzu die Formel für $a_n$.
$a_n =$ ... (für $n = 1, 2, 3, ...$)
(c) Kontrolliere die Formel im folgenden Applet.
Aufgabe 3 (etwas schwieriger)
Hier geht es um eine Herleitung der Formel aus Aufgabe 2.
(a) Wir wissen, dass folgender Zusammenhang besteht:
$a_1 = 1$
$a_n = 2 \cdot a_{n-1} + 1$ für $n = 2, 3, ...$
Begründe, dass sich hieraus ergibt:
$a_1 = 1$
$a_2 - a_1 = a_1 + 1$
$a_3 - a_2 = a_2 + 1$
$a_4 - a_3 = a_3 + 1$
...
(b) Erläutere die folgenden Umformungen.
$a_1 = 1 = 2^0$
$a_2 = 2 \cdot a_1 + 1 = 2\cdot(2^0) + 1 = 2^1 + 2^0$
$a_3 = 2 \cdot a_2 + 1 = 2\cdot(2^1 + 2^0) + 1 = 2^2 + 2^1 + 2^0$
$a_4 = 2 \cdot a_3 + 1 = 2\cdot(2^2 + 2^1 + 2^0) + 1 = 2^3 + 2^2 + 2^1 + 2^0$
...
Begründe, dass sich hieraus ergibt:
$a_1 = 2^0$
$a_2 - a_1 = 2^1$
$a_3 - a_2 = 2^2$
$a_4 - a_3 = 2^3$
...
(c) Begründe: Mit (a) und (b) erhält man:
$a_1 + 1 = 2^1$ bzw. $a_1 = 2^1 - 1$
$a_2 + 1 = 2^2$ bzw. $a_2 = 2^2 - 1$
$a_3 + 1 = 2^3$ bzw. $a_3 = 2^3 - 1$
...
