Grössenordnung der rekursiven Funktion? T(0):=0 und T(n):=3*T(n-1) + 2, für n≠0.

Question

Vollständige Induktion mit zwei Variablen?

Ich möchte die Größenordnung einer rekursiven Funktion ermitteln. Durch Substitution konnte ich die Funktion in folgende allgemeine Form bringen:

Dies muss ich nun noch mit vollständiger Induktion beweisen. Wie stelle ich das an bei zwei Variablen ( n und k). Fühl mich grad ein bisschen vor den Kopf gestoßen, obwohl es ja nicht so schwer sein kann.

Übrigens, das genaue Verhalten der Funktion ist bestimmt wichtig um helfen zu können ;)

Ich hoffe auf aufschlussreiche Antworten, danke im Vorfeld!

LG

Mark

Comments

Mach das erstmal fertig, d.h. bis zum Ende, wo k=n ist.

Answer 1

Du vermutest also für n≥1

$$ T(n)= \sum_{k=1}^{n}{{ 3 }^{ n-k }*2} $$

Bew. durch vollst Ind. über n:

Für n=1    nach Def: T(1)= 3*0+2=2

nach Formel Summe von k=1 bis 1 also nur der Summand 3 ^1-1 * 2 = 2 passt.

Induktionsschritt:   Wenn die Formel für n gilt, dann

$$  T(n+1)= 3*T(n) + 2 = 3*\sum_{k=1}^{n}{{ 3 }^{ n-k }*2}+2 $$
$$=\sum_{k=1}^{n}{{ 3 }^{ n+1-k }*2}+2*3^0 $$
$$=\sum_{k=1}^{n+1}{{ 3 }^{ n+1-k }*2}$$

Dann hast du nach Ausklammern der 2 eine geo. Reihe, also

T(n) = 2 * ( 3^n - 1 ) / (3-1)   =  3^n - 1

Das kannst du an den Werten auch sofort ablesen

T(1) = 2 = 3-1

T(2)= 8 = 9-1

T(3) = 26 = 27 - 1   etc. und das dann mit Ind. beweisen.