Gegeben ist:
T(n) = 2*T(n-1)+2 mit T(0) = 0
Umwandlung in homogene Rekursionsgleichung:
T(n)-2*T(n-1) = 2
T(n-1)-2*T(n-2) = 2
Subtraktion der beiden Gleichungen liefert:
T(n)-3*T(n-1)+2*T(n-2) = 0
Charakteristische Gleichung:
x^ 2 - 3*x + 2 = 0
(x-2)*(x-1) = 0
Ansatz:
T(n) = a*2^n + b*1^n
T(n) = a*2^n + b
Bestimmung der ersten beiden Werte:
T(0) = 0 (gegeben)
T(1) = 2 (durch Rekursion)
LGS zum Bestimmen der Koeffizienten:
a+b = 0
2*a+b = 2
Lösung des LGS:
a = 2
b = -2
Rekursionsfreie Gleichung:
T(n) = 2*2^n - 2
(Ich hoffe, die Aufgabe wird nicht noch einmal geändert...)