Fibonacci Numbers and Linear Recurrences

Question

Today while doing this topic our professor gave an example with tiles.

The example: There are 2 kinds of tiles, A= 1 x 1 and B= 2 x 1. In how many ways can you arrange tiles in a line n units long?

There are two cases. Case 1: the last tile is 1 x 1 so the preceding tiles are an arrangement of n-1 units. Case 2: the last tile is 2 x 1 so the preceding arrangement is of n-2 tiles. Let's call the number of arrangements of type one $w_{n-1}$ and the number of arrangements of type two $w_{n-2}$. Then we have a recurrence relation $w_{n}$= $w_{n-1}$ + $w_{n-2}$.

I really have no idea what's going on here, if anybody could explain I would be grateful.

Answer 1

Suppose your tiles form a line of length $n$.

If the last tile is of form of $A$, then we are concatenating previous line of length $n-1$ with $A$. Hence, we just have to care about number of ways to form a line of length $n-1$ using those tiles, which is $w_{n-1}$.

If the last tile is of form of $B$, then we are concatenating previous line of length $n-2$ with $B$. Hence, we just have to care about number of ways to form a line of length $n-2$ using those tiles, which is $w_{n-2}$.

Hence $$w_n = w_{n-1} + w_{n-2}$$

Answer 2

Start with a small chain.

To make a line that is 1" long use a small tile.

To make a line that is 2" long either use 2 small tiles or one big tile.

To make a line that is 3" take a line that is 2" long and put a small tile on the end, or take a line that is 1" long and place a big tile on the end.

How many ways to make a chain that is $n$" long? Add a small tile to a chain that is $(n-1)$" or a long tile to a chain that is $(n-2)$"

$F_n = F_{n-1} + F_{n-2}$

Answer 3

In this problem we are trying to give an answer to the question "how many arrangements are there, for an array of size n?", and we do it in the form of recursion.

That means, we are saying something like "If we knew the answer to this question for a smaller number than n, then maybe we could represent our answer by that answer"

In this case, we indeed can.

ASSUME you know the number of arrangements for an array of size n-1 and the answer for an array of size n-2.

Now, look at an array of size n, for which you don't know the number of arrangements.

We now try to represent an answer for n by the (known) answer for n-1 and n-2

It is possible to do it by separating into two distinct cases.

1. The last tile is 1x1
2. The last tile is 2x1

How many arrangements for case 1? This is actually like asking what is the size of the array leftwithout the last tile. Answer: n-1, meaning f(n-1) arrangements.

Same for for case 2, f(n-2) arrangements.

These are two distinct cases, so we sum the number of options each of them yields:

F(n)=f(n-1)+f(n-2)