Recurrence relation problems

Question

For some math homework (that was already due but I really want to understand the content) I was asked the following question, How should I go about answering this? I'm new to recurrence relations and my heavens it's confusing.

In each of the following cases, find a (linear, constant-coefficient) recurrence relation for $u_n$ and give the values of $u_i$ for $0 \leq i \leq 3$.

($a$) Let $u_n$ be the number of words of length $n$ on the symbols $x, y $ and $z,$ in which each $z$ is followed immediately by an $x.$

($b$) Let $u_n$ be the number of ways to fill $n$ parking spaces with cars, buses and trucks, if each car uses one space, while each bus and each truck uses two spaces.

($c$) Let $u_n$ be the number of ways to tile a $2 \times n$ rectangle with dominoes. (A domino is a $1 \times 2$ rectangle.)

This is something I've put alot of time into trying to understand but I'm not getting anywhere, any help would be greatly appreciated.

Answer 1

I am also quite new to this topic, so I am not sure whether it is true, but here my ideas:

1. $u_n = 2u_{n-1} + u_{n-2}$, since we can form a word of length $n$ (not ending in $z$) by either taking a word of length $n-1$ and adding either $x$ or $y$ or by taking a word of length $n-2$ and adding $zx$.
2. $u_n = u_{n-1} + 2u_{n-2}$, since we can fill $n$ spaces by first filling $n-1$ spaces and then add a car or by filling $n-2$ spaces and then add a bus or a truck.
3. $u_n = u_{n-1} + u_{n-2}$ as we can tile length $n$ by either tiling length $n-1$ and adding one tile vertically or by tiling length $n-2$ and adding 2 tiles horizontally.