I have this problem I need to write a paper on and I'm stuck. You have fifty 2x1 rectangles, which we call dominoes. With these dominoes you want to pave a 2x50 rectangle. How many different ways are there to cover the rectangle? I've tried starting with smaller rectangles to see if I see a pattern but so far no luck. I'm thinking it has something to do with combinations and/or permutations. So far I've found a 2x1 rectangle has 1 way, a 2x2 has 2 ways, a 2x3 has 3 ways, a 2x4 has 5 ways, a 2x5 has 8 ways, a 2x6 has 13 ways and a 2x7 has 21 ways. I'm new to this forum but I've heard wonderful things about it and any help I could get would be greatly appreciated.
Hint - I would try this using recursion