Patterns #6

Introduction to recursive sequences

Exercise

You are tiling walkways using 1 x 2 tiles (pictured below). When you use the tiles, you can lay them horizontally or vertically.

1 x 2 tile

We’re curious how many different ways we could tile certain walkways. For example, if we want to tile a 2 x 2 walkway, there are two ways to do it (pictured below).

Tiling 1
Tiling 2
  1. How many ways are there to tile a 2 x 3 walkway? Sketch them out.
    3 x 2 walkway


  2. How about a 2 x 4 walkway?
    4 x 2 walkway



  3. How about a 2 x 5 walkway?
    5 x 2 walkway





  4. Let’s define a sequence \(t_n\) where \(t_n\) tells us the number of ways to tile a 2 x $n$ walkway. Use the work above to fill in the table below for \(n=2,3,4,5\). Then look for a pattern in the numbers, and use it to complete the rest of table. What is the pattern?

      \(n\)       2     3     4     5     6     7     8     9     10  
      \(t_n\)                      






  5. Can you explain the pattern you see in the numbers by connecting the ways to tile a 2 x 6 walkway with the ways to tile the smaller walkways? Generalize this to 2 x \(n\).