🐇 Rabbit Staircase

A rabbit can hop either 1 or 2 steps at a time. How many distinct ways can it reach the top of a staircase with n steps?

Number of steps: 5

Choose a sequence below, or click “Show one way”.

Why does the recurrence work?

Last hop = 1 step

Before the last hop, the rabbit must be standing on step n−1.

W(4) = 5 ways

Last hop = 2 steps

Before the last hop, the rabbit must be standing on step n−2.

W(3) = 3 ways

So W(5) = 5 + 3 = 8.

8 sequences

Base cases: W(0)=1 and W(1)=1. Therefore the number of ways for n steps is F(n+1).