Not being together arrangement exercise

Question

I have these 2 exercises, i tried to solve them but i'm now sure about my answer. I'm not really good at this mathematics area, so i'd appreciate any help

Exercise 1.- "Rex is going to paint a six-floor building and he has 2 colors, green and blue. How many ways can the building be painted, if each floor is painted in a single color and there can't be consecutive floors painted blue?" Note: He can't paint all the building Green.

My ideas

I solved it in a "manual" way. Let's see, if Rex just paint one floor blue, he can paint the building of 6 ways,that are:

1. B,G,G,G,G,G
2. G,B,G,G,G,G
3. G,G,B,G,G,G
4. G,G,G,B,G,G
5. G,G,G,G,B,G
6. G,G,G,G,G,B

if he paint 2 floors blue, he can do it of 10 ways :

1. B,G,B,G,G,G
2. B,G,G,B,G,G
3. B,G,G,G,B,G
4. B,G,G,G,G,B
5. G,B,G,B,G,G
6. G,B,G,G,B,G
7. G,B,G,G,G,B
8. G,G,B,G,B,G
9. G,G,B,G,G,B
10. G,G,G,B,G,B

and if he paint 3 floors, he can do it of 4 ways.

1. B,G,B,G,B,G
2. B,G,B,G,G,B
3. B,G,G,B,G,B
4. G,B,G,B,G,B

in total he got 6 + 10 + 4 = 20 ways

But i don't really want that, i'd like to do it in a "formula way", with a Binomial coefficient, or by a permutation/combination. i got:

painting 1 floor blue he has:

$\frac{6!}{1!5!}$ = 6

Painting 2 floors blue he has (The total ways to paint two floors minus the ways to paint consecutive floors:

$\frac{6!}{2!4!}$ - $\frac{5!}{1!4!}$ = $15-5$ = $10$

Next to that i don't really know how. I would appreciate for any help, thanks.

Answer 1

Let's paint the building floor by floor, and keep track of two numbers: options where the top-most painted floor (floor $n$) is green $g(n)$, and those where it is blue $b(n)$.

Clearly $g(1)=1$ and $b(1)=1$ (ignoring, for now, the restriction on an all-green building).

If we have painted up to floor $k$, how many options are there for floor $k\!+\!1$? To paint the new floor blue, we need the previous floor green, so $b(k\!+\!1)=g(k)$. But we don't have that restriction on green floors, so $g(k\!+\!1) = g(k)+b(k)$.

So we can quickly paint up the building:

\begin{array}{|c|c|} \hline \text{floor }n & g(n) & b(n) \\ \hline 1 & 1 & 1 \\ \hline 2 & 2 & 1 \\ \hline 3 & 3 & 2 \\ \hline 4 & 5 & 3 \\ \hline 5 & 8 & 5 \\ \hline 6 & 13 & 8 \\ \hline \end{array}

-then add these two and subtract the all-green option to get the answer of $13+8-1 = 20$

On the way to the answer, most people with an interest in mathematics will recognize the Fibonacci sequence, and it's clear that $g(k\!+\!1) = g(k)+g(k\!-\!1)$ (since $b(k)=g(k\!-\!1)$) which explains this occurrence.