WisFaq!

Recursie

T(n) = 2*T(n-1) +3
T(1) = 4

hoe ga ik te werk om bovenstaande recurrente betrekking te verwerken tot een normale expressie ?

san jay
10-5-2004

Antwoord

1) Uitschrijven om een idee te krijgen
T(4)=2·T(3)+ 3 = 4·T(2) +3 +3 +3 = 8·T(1) + 3 +3 +3 +3 +3 +3 +3 ®
2) Idee: T(n)=2^n-1·T(1)+ (2^n-1-1)·3= 2^n-1·(T(1)+3) - 3
3) Bewijs dit nu met volledige inductie.

Met vriendelijke groet

JaDeX

jadex
10-5-2004