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 :)