Verschillende manieren om een trap op te lopen

Als ik een trap op loop dan doe ik dat met stappen van een of twee treden tegelijk. Hoeveel verschillende manieren zijn er dan om een trap van n treden op te lopen?

Frank
Student universiteit - woensdag 19 maart 2003

Antwoord

Stel het aantal verschillende manieren is a(n).
Je ziet snel dat geldt: a(1) = 1 en a(2) = 2.
En ook dat a(3) = a(1) + a(2), immers je eindigt met een stap van 2 óf 1 trede.

Algemeen: a(n) = a(n-2) + a(n-1).

Dit is de recursieformulie die hoort bij de rij van Fibonacci (F(n)), maar nu met andere startwaarden.
Je ziet waarschijnlijk snel dat dus geldt: a(n) = F(n+1).

Zie Leonardo's Leaps

woensdag 19 maart 2003

©2001-2024 WisFaq