Explizite Folgenbeschreibung

Eine alternative Beschreibung der Zahlenfolge entwickeln

Wir betrachten weiterhin die minimalen Anzahlen von Bewegungen $a_1; a_2; a_3; a_4; a_5; ...$ zum Umschichten eines $n$-Scheiben-Turmes. Man erhält diese Zahlenfolge:

$1; 3; 7; 15; 31; ...$

Aufgabe 1

Überprüfe zunächst die Formeln für $a_1$, $a_2$ und $a_3$ in der folgenden Auflistung. Ergänze anschließend die allgemeine Formel für $a_n$.

$a_1 = 2^1 - 1$
$a_2 = 2^2 - 1$
$a_3 = 2^3 - 1$
...
$a_n = ...$ (für $n = 1, 2, ...$)

Aufgabe 2

(a) Die Mönche von Benares benötigen zum Transport von 1 Scheibe 1 Minute. Wie lange brauchen sie, um einen 64-Scheiben-Turm umzuschichten? Benutze die in Aufgabe 1 entwickelte Formel zur Berechnung der Dauer des Umschichtvorgangs. Gib das Ergebnis in Minuten und auch in Jahren an.

(b) Vergleiche die in (a) bestimmte Zeit mit dem Alter des Universums, das ca. 13.8 Milliarden Jahre beträgt. Wann ist demnach der Weltuntergang zu befürchten?

Aufgabe 3 (etwas schwieriger)

Hier geht es um eine Herleitung der Formel aus Aufgabe 1.

(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$
...