Fibonacci Numbers

Suppose you had to lay a walkway of combinations of 1x2 ft tiles. Being the observant individual that you are, you notice that these tiles display a pattern. If you have one tile, you may lay it in one way. If you have two tiles you may lay them two ways. If you have three tiles, you may lay them 3 ways, and if you have 4 tiles you may lay them 5 ways. Like so,
Notice that this actually elicits a pattern. We have that the 3 x 2 tiles equal the 1 x 2 tiles + 2 x 2 tiles. This continues throughout all values of tiles, and is not a coincidence.
This pattern gives us the Fibonacci numbers which are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
If we were asked to write a formula for the Fibonacci numbers it would be recursively defined, or in terms of previous terms of a sequence, by: