I am working on a problem case to try gaining more intuition behind recursion and mathematical formula's. I understand how to solve the case by using code and recursion. However, I find the mathematical formula less intuitive.
The case is: an object has to cover 11 feet to reach it's end destination. It can take moves of 1 feet or 2 feet. Find out in how many ways the object can cover 11 feet, f(11)?
The solution follows the "Fibonacci-method" to generate the answer (providing the answer on the number of ways the object can reach the 11th step). I can code this by using a recursive function that returns the sum of the two previous states (n-1 and n-2).
So the solution states that this problem case follows the following function:
f(n+2) = f(n+1) + f(n)
So if we take f(3):
f(1+2) = f(1+1) + f(1) -> f(3) = f(2) + f(1)
But why should the answer of f(3) be the sum of the previous two states? Why does that make sense in this case where the object can take either 1 or 2 feet-moves?
We can't move by $3$ feets directly.
So we must have achieved that by a sequence of $1$ or $2$ feets that sum up to $3$.
Let's condition on the last move.
To use $2$ feet as our last move, we must have taken the $2$ feet move from $1$ feet location. To reach the $1$ feet location, there are $f(1)$ ways.
To use $1$ feet as our last move, we must have taken the $1$ feet move from $2$ feet location. To reach the $2$ feet location, there are $f(2)$ ways.
Hence $$f(3)=f(1)+f(2)$$