Paula would like to re-tile the hallway with those nice domino-shaped tiles she discovered while redoing the kitchen. The tiles are 1×2, and the hallway is just wide enough for one of these tiles to fit horizontally.

Paula knows she doesn’t have to tile the hallway all the way to the back of the house, since the carpet from the den can stretch across some portion of the hallway; she hasn’t decided exactly how long the tiling will be, though. To keep her options open, Paula labels the dimension of the hallway 2xn, where n is some positive integer.

How many ways are there for her to tile the 2xn hallway with the domino-shaped tiles?

The solution can be found here. Happy puzzling!

*Print-friendly versions of all Brain Play problems can be found here.*