Zeigen Sie durch vollständige Induktion, dass \(T(n)\leq7n^2-6n\), falls \(n\) eine Zweierpotenz ist und \(T(n)\) durch folgende Rekurrenzrelation beschrieben wird:
$$T(n)\leq \begin{cases} 1 & \text{falls }n=1\\4*T(\lceil \frac{n}{2}\rceil)+6n & \text{falls} ~ n\ge 2 \end{cases}$$
Meine Lösung sieht bis jetzt folgendermaßen aus:
Für den Fall, dass \(n=1\) ist das ganze trivial.
Für alle weiteren Fälle der Induktion sieht das so aus:
\(T(n+1)\leq4*T(\lceil \frac{n+1}{2}\rceil)+6(n+1)\leq7(n+1)^2-6(n+1)\)
Irgendwie komme ich an dem Punkt aber nicht weiter. Habe ich hier schon einen Denkfehler drin (zum Beispiel das ich \(n+1\) verwende und dabei nicht berücksichtige, dass \(n\) eine Zweierpotenz ist)?
Kann mir jemand Denkanstöße liefern, damit ich mir die Lösung erarbeiten kann?
