Andrew wants to cross a 12-foot long bridge. He can either take a 1 foot step or a 2 foot step.Provide a recursive formula for this problem.

Question

Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step.

I have found it easy to think of the bridge as a 1x12 game board using 1x1 blocks and 1x2 blocks. With that, I started with a 1x1 board and found there to be one possibility to fill the board, a 1x1 block. For a 1x2 board there are two possibilities: two 1x1 blocks or one 1x2 block. For a 1x3 board there are 3 possibilities, a 1x4 there are 5 possibilities, for a 1x5 there are 8 possibilities, and so forth. I noticed that this looked like the Fibonacci Sequence, therefore the recursive formula would look like Fn=Fn-1+Fn-2 if F1=1 and F2=2. Then we can find that there will be 233 ways for Andrew to cross the bridge.

Although I understand that the reason behind the recursive formula slightly, our professor wants a proof for how we came to the conclusion and i was unsure how to go about it. Here is what I understand thus far:

Given the 1x1 board and the 1x2 board, we can see that a 1x3 board is like the 1x2 board but with an extra 1x1 block added to the end. The 1x4 board has similar patterns to the 1x3 board, but adds an extra 1x1 block to the end and it is similar to the 1x2 board but adds two 1x1 block and one 1x2 block to the ends.

How does that work into a proof?

Answer 1

You are right that this amounts to a Fibonacci sequence, and to see why, notice this:

Let's say that the number of ways to $P_n$

Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways

So, we have that:

$$P_n = P_{n-1}+P_{n-2}$$

and there is obviously your connection with the Fibonacci problem!

Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$

So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$

So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways

Answer 2

You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).

How I would explain it is that given a bridge of length $n\geq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.

Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.

All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.

You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.