WisFaq!

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
19-3-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 [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibpuzzles.html#stairs]

jr
19-3-2003