Rekursion auflösen



  • Hallo, ich habe folgende Rekuriosn gegeben:

    \begin{eqnarray*} T(2^0) = 0 \\ T( 2^n) = T(2^{n-1})*2 +2^n, für n>1 \end{eqnarray}

    Wie geht man vor um das in eine normale nicht-rekursive Formel umzuformen?



  • Da das ganze irgendwie nicht so geklappt hat wie ich es wollte nochmal:

    T( 2^0) = 0
    T( 2^n) = T(2^ (n-1)) *2 + 2^n



  • Ich schreibe es mal um:
    T(0) = 0
    T(n) = T(n-1)*2 + 2^n, n >= 1

    Idee:
    Berechne die ersten paar Werte (wie unten) bis du eine Funktion vermutest und beweise diese anschliessend mittels vollständiger Induktion.

    T(0) = 0
    T(1) = T(0) * 2 + 2
    T(2) = (T(0) * 2 + 2) * 2 + 2 = 2*T(0) + 2*2 + 2
    T(3) = ... = 4*T(0) + 2*2*2 + 2*2 + 2
    ...



  • @softball: Deine Notation ist sehr seltsam. Einfach mal die ersten Folgeglieder ausrechnen und dann weiter mit Intuition. Ich gehe mal von a(0) = 0 und a(n) = 2*a(n-1) + 2^n aus:

    a0 = 0
    a1 = 2* a0 + 2^1
    a2 = 2* a1 + 2^2
    a3 = 2* a2 + 2^3
    = 2* (2* a1 + 2^2) + 2^3
    = 2*2* a1 + 22^2 + 2^3
    = 2*2* (2
    a0 + 2^1) + 2^3 + 2^3
    = 2*2*2* a0 + 2^3 + 2^3 + 2^3
    = 0 + 3 * 2^3

    wie man leicht sieht, ist a(n) = n * 2^n, was vielleicht noch durch Induktion bewiesen werden sollte.

    Eine Andere Moeglichkeit (und wohl die richtige) deine Gleichung zu interpretieren ist: T(1) = 0 ; 2^0 = 1 T(2z) = 2* T(z) + 2z ; wenn z = 2^(n-1) ist.

    Der Weg ist analog zu dem oberen, nur dass jetzt a(2^n) = n * 2^n herauskommt. Substituieren wir mit k = 2^n => n = log k. Daraus ergibt sich a(k) = k * log k.


Log in to reply