Riddler Classic
A frog needs to jump across 20 lily pads. He starts on the shore (Number 0) and ends precisely on the last lily pad (Number 20). He can jump one or two lily pads at a time. How many different ways can he reach his destination?
What if he can jump one, two or three at a time? Or four? Five? Six? Etc.
Solution
Let \(J_n\) be the number of jumps required by the frog to reach the \(n^{th}\) lily pad. It is easy to see that \(J_n = J_{n-1} + J_{n-2}\) and \(J_1 = 1\) and \(J_2 = 2\).