Blocks and Towers

Difficulty: 5 of 10

One of my favorite kinds of puzzles involved a branch of mathematics called combinatorics. Combinatorics is basically all about counting things. Sounds easy, right? Good. I recommend sustaining this delusion as long as possible. I should also add that there are many practical applications to combinatorics. For example, we've been using combinatorics in my statistical physics class to calculate probabilities, which are then used to explain the behavior of large systems.

Here is an interesting combinatorics problem which doesn't require any knowledge of combinatorics, but does require a lot of cleverness. This is probably the hardest puzzle I've posted so far. You have an infinite number of 1x1 blocks and 1x2 blocks. You want to put some of them together so they make a tower of 1x10. How many different ways are there to do this?

To better understand the problem, first try smaller towers. I'm going to abbreviate each possible way into a string of 1s and 2s, representing a 1x1 blocks and a 1x2 blocks respectively. For a 1x1 tower, there is only one way: a single 1. For a 1x2 tower, there are two ways: 11 and 2. For 1x3, there are three ways: 111, 12, and 21. For 1x4, there are five ways: 1111, 211, 121, 112, and 22. Pretty soon, you'll need more than just your fingers to count these.

Ok, so I lied. I'm not just interested in 1x10 towers. I'm interested in any 1xN sized tower. A general formula, if possible, would be best. You might find a hint somewhere in my post explaining mathematical induction. (Is this puzzle the real reason I bothered with induction? I won't say!)

See the solution (Need I say, spoiler alert?)