WisFaq!

Bewijs mbv inductie

T(n)= 1 (als n=1)
= T(n-1)+2^n (anders dan 1)

is gelijk aan T'(n)=2^(n+1) - 1

basis stap n=2

T(1)= 1 T(2)= (2-1)+2^2 = 4 = 5

T'(2)= 2^3 - 1 = 7

hoe gaat het verder? Ik loop nu een beetje vast.

Peter
14-9-2003

Antwoord

Hallo Peter,

De opgave klopt niet helemaal, want T(2)=T(1)+2² = 1+4=5
En T'(2)=2³-1=7 zoals je zelf schreef...

Het klopt wel als je T(n)=1 als n=0 stelt
en nog steeds T(n)=T(n-1)+2^n als n0
Dus T(0)=1
T(1)=3 T(2)=3+2²=7 enzovoort.

Dan het bewijs:
Stel dat het werkt voor T(n)=T'(n), er is te bewijzen dat T(n+1)=T'(n+1)

T(n+1)=T(n)+2^(n+1) (per definitie van T(n+1))
= T'(n)+2^(n+1) (inductiehypothese T(n)=T'(n))
= 2^(n+1) - 1 + 2^(n+1) (per definitie van T'(n))
= 2*2^(n+1) - 1
= 2^(n+2) - 1
= T'(n+1) (per definitie van T'(n+1))

En daarmee is de gelijkheid van T en T' bewezen!

Groeten,
Christophe.

Christophe
14-9-2003