How to write a recursive expression?

Question

I'm doing a problem involving a recursive expression, and I'm not quite sure how to accurately show one on paper. I've done some research and looked at other questions but I'm still slightly confused.

The problem in particular is:

The sequence $D_n$ shows the number of ways to color a buildings floor (of $n \ge 1$ stories). Each floor may be yellow or blue, but no blue floors can be touching. Yellow has no restriction. Find a recursive expression for $D_n$ with appropriate initial conditions.

I know how I would solve the problem, but I want to able to write this problem correctly, What are the initial conditions? I have no clue what those are. Thanks for helping!

Edit:

I would solve this problem by looking at a building of height h, I know that this tower is equal to h-1 + the current floor... I don't know EXACTLY how to solve it as I haven't put in the thought into it yet. I understand what a recursive expression is, I just have no idea what one consists of (the format) is what I really need. It also asks for sufficient initial conditions, and I don't know what initial conditions are.

Answer 1

Suppose you have a tall building with $n$ floors. The top floor is either yellow or blue.

Suppose the top floor is yellow and imagine popping this floor off the building. How many buildings on $n-1$ floors could remain? Since the top floor being yellow placed no additional restrictions on the other floors (aside from the universal one that two blue floors cannot touch), there are $D_{n-1}$ ways to color the remaining floors.

Suppose the top floor is blue. In this case, I know for certain the floor beneath it is yellow. Pop these top two floors off and ask how many buildings on $n-2$ floors could remain. Again, these floors could be colored using any legal configuration, so there are $D_{n-2}$ ways to do this.

Taken together, we get the recursion $D_n = D_{n-1} + D_{n-2}$ for $n \geq 2$. Since the recursion goes back two steps, we need to compute the values of $D_0$ and $D_1$ directly (the recursion won't help us find these first two values). There are no buildings having zero floors and there are just two having one floor, so $D_0 = 0$ and $D_1 = 2$ are the initial conditions.

Answer 2

Let $Y_n$ denote the number of colorings under the extra condition that the upper floor has color yellow, and let $B_n$ denote the number of colorings under the extra condition that the upper floor has color blue.

Then for $n=1,2,\dots$ we have the following equalities:

• $Y_{n+1}=D_n$
• $B_{n+1}=Y_n$
• $D_n=Y_n+B_n$

Now observe that: $$D_{n+2}=Y_{n+2}+B_{n+2}=D_{n+1}+Y_{n+1}=D_{n+1}+D_n$$

The initial conditions are $D_1=2$ and $D_2=3$ which are not difficult to find.