Given a $1xn$ grid, determine how many different distinct tilings are possible using only $1x1$ and/or $1x2$ tiles. Let z be the function giving the total number of distinct tiling for a given $1xn$ grid. For any given tiling of a $1xn$ grid where $n > 1$, it must end in a $1x1$ or a $1x2$ tile. For a $1x n$ grid, the number of tilings wherein the last tile is a $1x1$ tile is equal to $z(n-1)$. For a $1xn$ grid, the number of tilings wherein the last tile is a $1x2$ tile is equal to $z(n-2)$. Since each tiling must end in a 1x1 or 1x2 tile, $z(n) = z(n-1) + z(n-2)$. This follows the Fibonacci sequence.
Special case: $n=1$ results in 1 possible tiling.
When attempting to determine the various possible combination in which a 1x1 and 1x2 tile can fit within a box of length 1xn, we see that looking at the combinations for a 1x5 box can help us determine a manner to calculate greater tile values. When laying out the 8 combinations that results in 5 “ lines” ending with a 1x1 and 3 that end in a 1x2. Grouping up said lines and separating out the ending lines we see that all lines ending with a 1x1 tile gives the 5 various combinations 1x1 and 1x2 can fit within a 1x4 space, this is also seen when looking at the final 3 lines giving us the 3 various combinations that fit within a 1x3 box. Using this information it can be determined that each subsequent increase in box size would follow suit in taking the two previous combinations and adding a row ending with a 1x1 or 1x2. This can be written as F(n) =F(n-1)+F(n-2).
Proof:
For boxes 1xn in length filled in with differing combinations of 1x1 boxes and 1x2 boxes, the fibonacci sequence shows up with a 1x1 box having 1 combination, a 1x2 with 2 combinations, 1x3 with 3, 1x4 with 5, 1x5 with 8 an so on. This happens because the fibonacci sequence is Fn=F(n-1)+F(n-2) and this appears in the boxes as Fn-1 being the 1x1 tile remainder for odd n and Fn-2 being the 1x2 tile distributed through even n creating the fibonacci sequence in the tiles.
In the class activity we were given directions to determine the number of tilings for a 1xn grid using 1x1 and 1x2 tiles. When using the tiles to fill in the grid the possible combinations of the arrangement of the tiles continues in a pattern that is found in the Fibonacci Sequence. The Fibonacci Sequence is a recursive formula that calls upon itself and goes back 1 and 2 elements and adds them together to get the current element: Fn = F(n-1) + F(n-2). This formula works for all values n > 1.
Let $T_n$ be the number of tilings of the $1 \times n$ rectangle.
Consider a $1 \times n$ tiling, where $n \geq 3$. The rightmost tile is either a $1 \times 1$ tile or a $1 \times 2$ tile. So, $T_n$ is equal to the sum of i) the number of $1 \times n$ tilings ending in a $1 \times 1$ tile and ii) the number of $1 \times n$ tilings ending in a $1 \times 2$ tile.
If the rightmost tile is a $1 \times 1$ tile, removing it leaves a $1 \times (n - 1)$ tile. In fact, removing the rightmost tile gives a one-to-one correspondence between i) $1 \times n$ tilings ending with a $1 \times 1$ tile and ii) $1 \times (n - 1)$ tilings. Therefore, the number of such $1 \times n$ tilings is $T_{n-1}$.
Similarly, removing the rightmost tile gives a one-to-one correspondence between i) $1 \times n$ tilings ending in a $1 \times 2$ tile and ii) $1 \times (n - 2)$ tilings, so the number of such $1 \times n$ tilings is $T_{n-2}$.
We conclude that $T_n = T_{n-1} + T_{n-2}$ for all $n \geq 3$. Note that $T_1 = 1$, since the only tiling of a $1 \times 1$ rectangle is to use a single $1 \times 1$ tile, and $T_2 = 2$ since the $1 \times 2$ rectangle can be tiled either with a $1 \times 2$ tile or with two $1 \times 1$ tiles. By induction, $T_n$ is equal to the $n$th Fibonacci number.
For any given 1xn grid, the number of unique combinations using only 1x1 and 1x2 tiles to fill the space is equal to the nth value of the Fibonacci Sequence, given that the output when n = 1 is 1. The unique solutions for any given n can be split into two categories: those ending in a 1x1 or a 1x2 tile. Those ending in 1x1 tiles represent the solutions to n-1, with the addition of a 1x1 tile. Those ending in 1x2 tiles represent the solutions to n-2, with the addition of a 1x2 tile. Thus the number of solutions to any n are equal to the total number of solutions to n-1 and n-2.
In order to find the number of unique tile combinations in a 1xn grid, we first can take the combinations of the 1x(n-1) grid and add an additional 1x1 tile to each combination. Then we can take all the combinations of the 1x(n-2) grid and add an additional 1x2 tile to each combination. All the combinations in the previous two grid sizes appear in the grid we are currently dealing with. f(n) = f(n-1) + f(n-2). If we assume that the first two values in the sequence are 1 and 2, every value after will be the sum of the previous two terms.