Rekursive Darstellung einer Folge

Ein Knobelproblem mit einer Folge bearbeiten

Wir betrachten das Kartenhausproblem.

Zur Bearbeitung des Problems benutzen wir eine Folge. Die Folge $a_1; a_2; a_3; ...$ beschreibt die Anzahl der Karten, die man für das Kartenhaus mit der Nummer $1; 2; 3; ...$ benötigt.

Aufgabe 1

Ergänze die Formel für $a_n$.

$a_1 = 3$
$a_2 = a_1 + 2\cdot 3$
$a_3 = a_2 + 3\cdot 3$
$a_4 = a_3 + 4\cdot 3$
...
$a_n = ...$ für $n = 2; 3; 4; ...$

Aufgabe 2

(a) Rekursive Darstellungen führen zu zurücklaufenden Berechnungen. Erkläre das Vorgehen bei der Ausführung einer Berechnung an folgendem Beispiel.

rekursiver Abstieg	rekursiver Aufstieg
$a_4 = a_3 + 4\cdot 3$ $\downarrow$	$a_4 = 18 + 12 = 30$
$a_3 = a_2 + 3\cdot 3$ $\downarrow$	$a_3 = 9 + 9 = 18$ $\uparrow$
$a_2 = a_1 + 2\cdot 3$ $\downarrow$	$a_2 = 3 + 6 = 9$ $\uparrow$
$a_1 = 3$	$a_1 = 3$ $\uparrow$

(b) Begründe, warum eine rekursive Berechnung eines Folgenglieds recht aufwendig ist.

Aufgabe 3

Welche rekursive Darstellung kann man zur Berechnung der oben beschriebenen Folge nutzen? Begründe kurz.

Variante 1:

$a_1 = 3$
$a_n = a_{n-1} + n \cdot 3$ für $n = 2; 3; 4; ...$

Variante 2:

$a_1 = 3$
$a_{n+1} = a_n + (n+1) \cdot 3$ für $n = 1; 2; 3; ...$

Variante 3:

$a_{n+1} = a_n + (n+1) \cdot 3$ für $n = 1; 2; 3; ...$

Aufgabe 4

(a) Es ist recht schwierig, eine explizite Formel für $a_n$ zu bestimmen. Wir verraten sie hier:

$a_n = \displaystyle{\frac{(n+1) \cdot n}{2}} \cdot 3$ für $n = 1; 2; 3; 4; ...$

Überprüfe, ob die Formel stimmt. Berechne hierzu zur Kontrolle mindestens 3 Folgenglieder.

(b) Mache dir an Beispiel "Kartenhaus" nochmal klar, dass es manchmel recht leicht ist, eine rekursive Darstellung einer Folge zu bestimmen. Die Berechnung der Folgenglieder ist dagegen aufwendig.