Lösung einer Rekursion

Question

T(n)=2T(n-1)+2

T(0)=0 (vorgegeben)

T(1)=2

T(2)=6

T(3)=10

T(4)=22

T(5)=46

T(6)=94

Das habe ich bisher. Komme leider nicht auf die Lösung, was T(n) ist.

Danke für eure Hilfe

Comments

Die Werte für n>0 stimmen nicht!

Answer 1

n	0	1	2	3	4
T(n)	0	2	6	14	30

Deine Folge habe ich korrigiert.
Dann gilt: T(n)=2ⁿ-2. 

Comments

Habe mich leider verschieben. Ist nicht +3 sondern +2 :)

---

Dann sieht es so aus:

n	0	1	2	3
T(n)	0	2	6	14

Ab den 3. Glied ist deine Folge falsch.

Answer 2

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