Respuesta :
Answer:
[tex]f(n) = 3f(n - 1) + 2f(n - 2)[/tex], if [tex]n \geq 2[/tex].
[tex]f(0) := 1[/tex], [tex]f(1) := 3[/tex]
Step-by-step explanation:
Let [tex]f(n)[/tex] be the number of different tiling of [tex]1 \times n[/tex] floor. We can divide all possible tiling of floor [tex]1 \times n[/tex] into five not overlapping groups by color of last cell in the row (Blue, Red, Green, Orange, White).
The number of tiling [tex]1\times n[/tex] floor such that last cell in row is Blue is exactly f(n - 1) because we can throw away last [tex]1\times 1[/tex] tile and cover the rest [tex]1\times (n - 1)[/tex] cells in f(n - 1) ways. Similarly for Red and Green.
The number of tiling [tex]1\times n[/tex] floor such that last cell in row is Orange is exactly f(n - 2) because we can throw away last [tex]1\times 2[/tex] tile and cover the rest [tex]1\times (n - 2)[/tex] cells in f(n - 2) ways. Similarly for White.
So we get recurrent relation:
[tex]f(n) = 3f(n - 1) + 2f(n - 2)[/tex], if [tex]n \geq 2[/tex].
Now we should define the initial conditions.
[tex]f(0) := 1[/tex] because there is only one empty tiling.
[tex]f(1) := 3[/tex] because we can place Blue, Red or Green tile.
This completely define our recurent sequence because the depth of reccurence is 2.
