I've been stuck with this problem:
With the help of recurrence equations, solve the following: There is a chart with dimensions $1 \times n$. We have dominos in two different colors which we should use to fill up the chart. In how many different ways can the chart be filled?
I'm hopeless with recurrence problems. I hope someone can explain how this particular problem should be solved.
If you have to use recurrence relations, note that a chart of length $n$ can be filled by filling the first $n-2$ squares then placing one more domino at the end.
You can do it without recurrence by noting that you have $\frac n2$ places to put dominoes and $2$ choices at each place.