Problem 6 · The kangaroo's jumps
A Fibonacci-style recurrence: $f(n) = f(n-1) + f(n-3)$.
Integer answer, at most 4 digitsA kangaroo moves along a straight line making forward jumps of one metre or three metres. If it wants to move exactly 10 metres, in how many different ways can it do so? (The same combination of jumps in a different order counts as a different way; e.g. the sequences $\{3,3,3,1\}$ and $\{1,3,3,3\}$ are different.)
Copa Cangur · SCM
Medium
Closed answer
Reasoned solution
Key idea: let $f(n)$ be the number of ways to advance $n$ metres. The last jump is $1$ or $3$ metres: $f(n) = f(n-1) + f(n-3)$.
With $f(0) = f(1) = f(2) = 1$ (ones only):
$$f(3)=2,\ f(4)=3,\ f(5)=4,\ f(6)=6,\ f(7)=9,\ f(8)=13,\ f(9)=19,\ f(10)=28.$$
Answer: 28