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.