Aufgabe:
Gegeben sei ein rekursiver Algorithmus und wir möchten die Laufzeit abschätzen. Der Algorithmus nimmt eine natürliche Zahl \( n \in \mathbb{N} \) entgegen und endet nach \( n \) Rekursionsschritten. Dabei besteht der gesamte Algorithmus aus zwei Teilalgorithmen: Algorithmus \( A \) und Algorithmus \( B \). Algorithmus \( A \) ruft drei mal sich selbst und zwei mal Algorithmus \( B \) auf und Algorithmus \( B \) ruft zwei mal Algorithmus \( A \) auf. Der gesamte Algorithmus startet mit dem Ausführen von Algorithmus \( A \).
Die \( n \) Rekursionsschritte sind dabei wie folgt zu verstehen: Ist \( n=0 \), so wird \( A \) einmal ausgeführt und der Algorithmus endet. Ist \( n=1 \), so wird \( A \) einmal ausgeführt, dann noch drei mal Algorithmus \( A \) und zwei mal Algorithmus \( B \) und dann endet der Algorithmus.
a) Sei \( x_{m} \) die Anzahl der Ausführungen von \( A \) und \( y_{m} \) die Anzahl der Ausführungen von \( B \) im \( m \)-ten Rekursionsschritt. Finden Sie eine Matrix \( M \) sodass für \( m \leq n \) gilt dass \( M^{m}\left(\begin{array}{l}1 \\ 0\end{array}\right)=\left(\begin{array}{l}x_{m} \\ y_{m}\end{array}\right) \).
b) Berechnen Sie die Eigenwerte und zugehörigen Eigenvektoren von \( M \) und bestimmen Sie die zugehörige Basiswechselmatrix zum Diagonalisieren.
c) Berechnen Sie die Anzahl der Rechenschritte (damit ist gemeint: Ausführungen von Algorithmus \( A \) oder \( B \) ) im \( m \)-ten Rekursionsschritt.
\( d^{*} \) ) Sei \( 1 \neq a \in \mathbb{R} \) und \( m \in \mathbb{N} \). Zeigen Sie mittels vollständiger Induktion nach \( m \), dass
\( \sum \limits_{n=0}^{m} a^{n}=\frac{1}{a-1}\left(a^{m+1}-1\right) .\)
Folgern Sie mit den Ergebnissen aus c) eine möglichst gekürzte Formel zur Anzahl der gesamten Rechenschritte des Algorithmus nach Eingabe einer natürlichen Zahl \( n \in \mathbb{N} \).
Hinweis: Betrachten Sie das Beispiel zur rekursiven Berechnung der Fibonacci Folge.
Problem/Ansatz:
Ich habe hier leider keinen Ansatz, wie ich die Aufgabe lösen muss. Ich wäre über eine Lösung mit Erklärung sehr dankbar
