Tiling Rectangles
You have two puzzles. For a 1 by n rectangle, how many ways can you fill it with a mixture of 1 by 1 squares and 1 by 2 rectangles? For a 2 by n rectangle, how many ways can you fill it with 1 by 2 rectangles?
THE CHALLENGE
Why do these two puzzles give the same answers? What are the answers when the rectangles being filled are 10 long? How about when they are 20 long?
EXPLORATION
How are these two problems similar to each other and earlier puzzles? How do things change in the 1 by n puzzle if we use 1 by 1 and 1 by 3 pieces instead? How do things change in the 1 by n puzzle if we use 1 by 1, 1 by 2, and 1 by 3 pieces?
Notes
THE CHALLENGE
Seeing how to apply earlier results to part or all of a new puzzle is a powerful skill.
These two puzzles are exactly the same in nature. Vertical pieces in the 2 x n rectangle correspond to 1 by 1 pieces in the 1 x n rectangle, and horizontal pieces in the 2 x n rectangle correspond to 1 by 2 pieces in the 1 x n rectangle. So, there really is no difference between the two puzzles.
Also, the 1 x n rectangle puzzle is exactly like the steps puzzle in “Fibonacci – 2.” Going one step at a time is like putting in a 1 by 1 square, and going two steps at a time is like putting in a 1 by 2 rectangle. The two puzzles are the same, so the analysis and results are the same.
EXPLORATION
If we use 1 by 1 and 1 by 3 rectangles, a lot changes. Look at the first few values and consider how they are calculated. We get 1, 1, 2, 3, 4, 6, and 9 for the first few values. In general the next value is the sum of the current value and the one two steps before that. It is simple enough to calculate, but it is no longer the Fibonnaci sequence.
If we use 1 by 1, 1 by 2, and 1 by 3, things change even more dramatically. Now the first few values are given by 1, 2, 4, 7, 13, and 24. The next value in the sequence is the sum of the previous three values.
Sequences like this that define their next terms by a set formula involving previous terms are called recursive sequences. The Fibonacci Numbers are not the only recursive sequence, but they are probably the most famous.