Hopping Rabbit Problem

Classical “Hopping rabbit” problem

A rabbit can jump one or two steps, how many ways to get to the top of n stairs?

def f(n):
    if n == 1 or n == 0:
        return 1
    return f(n-2) + f(n-1)

f(3) # 111, 12, 21

3

Mathematically, say take x of 2-jumps, (n-2x) of 1-jumps.

x can be 0, 1, … up to floor(n/2)

For each x, can have (n-2x+x choose x) ways

So in total, \( \sum_{x=1}^{\lfloor n/2 \rfloor} \binom{n-x}{x} \)

import math
def f2(n):
    N = n//2
    ans = 0
    for i in range(n//2+1):
        ans += math.comb(n-i, i)
    return ans
f2(3)
    

3

for i in range(10):
    if f(i) != f2(i):
        print(i, f(i), f2(i))
        break
    if i == 9:
        print(i, f(i), f2(i))

9 55 55