Finding the number of ways of crossing a river

Question

There are $X$ stones in the river.The stones are placed in such a way that a person can jump from one stone to the next one, or skip one and jump to the one after that. Find the number of ways in which one can jump across the stones from one river bank to another.

Note: We are always standing at the farther stone from the bank

For example:

• If there is one stone, we can jump directly to the bank of the river i.e. only 1 way.
• If there are 2 stones, we can jump from 1st to 2nd and then 2nd to bank or we can jump from 1st to bank skipping one stone(as mentioned in the question).
• Similarly for 3 stones no. of ways are 3.
• Similarly for 5 stones no. of ways are 8.

Is there any general technique to calculate the number of ways of crossing the river with $X$ stones?

Answer 1

Given n stones, the only option one has for the first jump is to go to stone n-1 or n-2. From that point on the options are the same as for stone n-1 or n-2, hence for any n, the number of options equals the sum of the options of n-1 and n-2. This generalises to the Fibonacci sequence (Fibonacci+1 to be exact). Hence the generalised technique to calculate this for n stones is Jumps=Fibonacci(n+1)

Answer 2

Isn't this just the Fibonacci sequence: 1, 2, 3, 5, 8, 13, 21, ...

Explanation:

If you number the stones starting at the target bank: From $stone_{n}$ you can initially jump to either $stone_{n-1}$ or $stone_{n-2}$. This makes the number of ways from $stone_{n}$ to the target bank equal to $stone_{n-1} + stone_{n-2}$.