In the book of Difference equations by Peterson, at page 73 - 74, it is given that
Example 3.22. (a tiling problem) In how many ways can the floor of a hallway that is three units wide and n units long be tiled with tiles, each of which is two units by one unit? We assume that n is even so that the tiling can be done without breaking any tiles.
However, I'm having trouble understanding the construction of $y_n$ and $_n$.
First of all, what does exactly $z_n$ denote as a number ? Secondly, should we have $$y_{n+2} = 3 * y_n ...$$ and $$z_{n+2} = 2* z(n) ...$$
I would appreciate if someone help me to go through the argument that the author provides.
To answer your two questions:
(1) $z(n)$ is the number of ways to tile a $3 \times n$ rectangle with two tiles already placed next to the short edge in the two configurations shown:
(2) Not quite. There are three ways to start tiling a rectangle (shown in Figure 3.4 in your question). So indeed, we will add three things together - namely, the number of ways to continue the tiling for each of these three ways to start. So
$y(n + 2) = (\text{number of ways to finish configuration 1}) + (\text{number of ways to finish configuration 2}) + (\text{number of ways to finish configuration 3}).$
Now configuration 1 is a rectangle two units shorter than the original (which is of length $n + 2$ in the original argument), and we already have a symbol for this, namely $y(n)$.
Configuration 2 and 3 are mirror images, so they will have the same number of ways to finish them. We don't have a symbol for that, so the author introduces the symbol $z(n + 2)$.
So we have:
$y(n + 2) = y(n) + z(n + 2) + z(n + 2) = y(n) + 2z(n + 2).$
Now, to calculate $z(n+2)$, we see there are 2 ways to start this new tiling (Figure 3.5 in your question). (We only look at one of the mirror images, since the numbers will be the same.) So now we will add two things:
$z(n + 2) = (\text{number of ways to finish configuration 1}) + (\text{number of ways to finish configuration 2}).$
(Here these configurations have nothing to do with the configurations we used in the equations for $y(n + 2)$.)
In first the configuration, we have a rectangle that is 2 units shorter than the original, which means the number of ways to finish that is $y(n)$. In the second configuration, we have a version of the $z$-type tiling that is two units shorter. So we can write:
$z(n + 2) = y(n) + z(n).$
We can then go ahead and solve these recurrence equations and get a final value for $y(n)$ in terms of $n$. The $z(n)$ was introduced as a helper function to make it easier to write down equations, but it will not appear in the final result (or, we can eliminate it from the final result).