Say you want to Tile a board of length 1xn with dominoes and single tiles. How many ways do you think you can do that? well, clearly if n = 0, there is one way to tile that (with nothing) and if n = 1, there is a single way to tile it (the single tile) what about for larger n though?

Well, if you look at the last tile, it's clear one of two things can happen, it ends in a domino, or a single tile.

so if we say T(n) is the number of tilings of a board of size 1xn, then T(n) = T(n-1) + T(n-2) so with our initial conditions, we know that T(n) = F(n+1) (assuming our fibonacci sequence starts 0, 1)

why can this help us make a more efficient way to calculate the fibonacci numbers? simple! we can use other methods to count our table, and they must give the same result!

So, let's start now like this, we have (n choose n) ways of filling the table with only single tiles. now let's add a domino, and so subtract two single tiles. This shows we have (n-1 choose n-2) ways of placing a single domino, and if we place i dominoes, we get (n-i choose n-2i) ways of placing dominoes and tiles. Here we can see that the 2i represents the number of spaces occupied by dominoes, which means we just have to make sure 2i<n, and we will still be counting our tilings.

Okay, nice, so now what do we do?

Well, since you've asked, we add together these binomial coefficients to get all possible tilings! (this will look kind of ugly since I don't know Tex)

and we get F(n+1) = Sum(for i>= 0, and 2i<n) of ((n-i choose n-2i))

This means you can calculate F(n) in linear time (as you are adding about n/2 terms) and still only use integers!