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

Bitte ein Bit

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
...

knivil

@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.