Let be the number of ways to tile a board. The very first column can be covered in one of two ways - either by a vertical domino in which case the remaining board can be covered in ways or by a horizontal domino in which case the remaining board can be covered in ways. So, the recursion we get is and the initial conditions are , . Thus, is a Fibonacci number.

Lams' sequence

F(n+2) = number of binary sequences of length n that have no consecutive 0's.

Very interesting how frequently this sequence is published.

See the link below:

http://oeis.org/search?q=1%2C2%2C3%2C5%2C8&language=english&go=Search

Let be the number of ways to tile a board. The very first column can be covered in one of two ways - either by a vertical domino in which case the remaining board can be covered in ways or by a horizontal domino in which case the remaining board can be covered in ways. So, the recursion we get is and the initial conditions are , . Thus, is a Fibonacci number.