A probability problem by Darel Gunawan

Let $f\left( n \right)$ be the number of ways to cover a $n\times 2$ rectangle, for $n\ge 1$ , with $1\times 2$ rectangles. Clearly, $f\left( 1 \right) =1$ and $f\left( 2 \right) =2$ .

Now, consider a $n\times 2$ rectangle, for $n\ge 3$ . Firstly, draw an $1\times 2$ on an end, as follows:

Consider the $(n-1)\times 2$ rectangle of the right side; the number of ways to cover it is given by $f\left( n-1 \right)$ .

Secondly, draw an $2\times 1$ rectangle on an end, as follows:

The space below (or above) only can be covered by another $2\times 1$ . Consider the $(n-2)\times 2$ rectangle of the right side; the number of ways to cover it is given by $f\left( n-2 \right)$ .

If you place a $2\times 1$ rectangle on another position of the $n\times 2$ , the left end of the $n\times 2$ rectangle can be covered in one of the two ways that we have studied, so another possible configuration will have been included in $f\left( n-2 \right)$ or $f\left( n-1 \right)$ , therefore, the number of ways to cover a $n\times 2$ rectangle is recursively given by the following expression:

$f\left( n \right) = f\left( n-1 \right)+ f\left( n-2 \right)$

We see that this is how Fibonacci sequence is defined (but $f\left( n \right)$ would be ${ f }_{ n+1 }$ ). Hence, we are looking for $f\left( 10 \right)$ , which is ${ f }_{ 11 }=89$ .