Introduction:

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,

This pattern gives us the Fibonacci numbers which are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

\(F_n=F_{n-1}+F_{n-2}\)