Rekurrenzrelation mit Hilfe vollständiger Induktion zeigen

Question

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?

Answer 1

Wenn $n$ eine Zweierpotenz sein soll, dann kannst Du im Induktionsschritt schlecht von $n$ zu $n+1$ uebergehen. Von $n$ nach $2n$ waere dann angebracht.

Comments

OK, macht man das ganze mit $2n$ statt mit $n+1$ macht das ganze schon viel mehr Sinn, vielen Dank :)