Hier bei induktives Einsetzen kann ich nicht weiterarbeiten, kann jemand bitte Weiterhilfen?

Für n ≥ 2 sei 

$f(n)=2f(n/2)+3n\log n$

vorgegeben. Zeigen Sie durch induktives Einsetzen unter Nutzung der Anfangswertbedingung f(1) = 3, dass 

$f∈O(n(\log n)^2)$

Answer 1

[PWolff]

Wo ist der Summand 3 n log(n) geblieben?

-----

Induktionsvoraussetzung: für k < n (oder auch k <= n/2; n >= 2) gelte:

f(k) <= c k (log(k))^2

-----

Aus dem Term für f(n) klammerst du

c n (log(n))^2

aus und wählst c so, dass der Faktor für genügend große n kleiner als 1 (oder gleich 1) ist.

Woher ich das weiß: Hobby – Hobby, Studium, gebe Nachhilfe