In how many ways can one tile a $2 \times n$ rectangle with $2 \times 1$ dominoes?
We place the rectangle horizontally. Let $u_{n}$ be the number of ways to tile the rectangle. We observe that $u_{1}=1$ and $u_{2}=2$. Consider an integer $n \geq 2$. If the rightmost domino is placed horizontally, the last two columns are occupied by two horizontal dominos, and the rest of the rectangle can be tiled in $u_{n-2}$ ways. If the rightmost domino is placed vertically, the last column is occupied by a vertical domino, and the rest of the rectangle can be tiled in $u_{n-1}$ ways. We thus obtain the recurrence relation $u_{n}=u_{n-1}+u_{n-2}$. We recognize the Fibonacci sequence, so the number of ways to tile a $2 \times n$ rectangle is $F_{n+1}$.