Rijen met d-k beperking

Ik heb deze vraag vorige week ook al gesteld, maar deze is verwijderd omdat ik geen reactie zou gegeven hebben op de vraag om verduidelijking. Ik had dit echter niet gezien. Sorry hiervoor. Toch zouden jullie ons veel kunnen helpen door het volgende te bewijzen:

Laat a(n) het aantal 0-1 rijen van lengte n zijn met d-k beperking waarin d=2 en k=3. Toon aan dat voor n6 geldt:
a(n) = a(n-3) + a(n-4)

Verduidelijking :
* 0-1 rijen: rijen van 0'en en 1'en
bv. 001101000011101101111100
* een rij met d-k beperking: een rij met als eigenschap dat tussen 2 opeenvolgende 1'en tenminste d 0'en staan en er nergens meer dan k 0'en achter elkaar staan. Hier wil dit dus zeggen dat het aantal opeenvolgende 0'en varieert tussen 2(min) en 3(max).
* a(n) is dus het aantal mogelijke rijen die er kunnen zijn.

Veel dank
nick, stefaan en bart 5LaWic

Nick V
3de graad ASO - woensdag 4 mei 2005

Antwoord

Noem b(n) het aantal rijen dat voldoet aan de eigenschap EN met een 1 begint. Zulke rijen zijn dan van de vorm

100...
(gevolgd door weer een rij die met een 1 begint, maar lengte n-3 heeft)

OF

1000...
(gevolgd door weer een rij die met een 1 begint, maar lengte n-4 heeft)

Er volgt dus dat b(n)=b(n-3)+b(n-4).

Het probleem is nu dat jij het niet hebt over eventuele voorwaarden die aan een rij die met een 0 begint worden gesteld, waar er dus nog geen "eerste" 1 is opgetreden. Die bepaling is nodig vooraleer je uitspraken kan doen over a(n).

vrijdag 13 mei 2005

©2001-2024 WisFaq