Pintar um prédio

Um prédio vai ser pintado usando-se uma cor para cada andar. Sabendo que as cores utilizadas são verde e amarelo e que andares consecutivos não poderão ser pintados de amarelo, de quantas maneiras é possível fazer a pintura deste prédio? E se o prédio tiver $n$ andares?

Proposta de resolução

Para um prédio de 4 andares, temos 8 maneiras, que estão listadas na tabela (V — verde, A — amarelo). Repara que apenas a cor amarela tem restrições: poderá não estar presente ou ter até dois andares amarelos.

Situação	1.º andar	2.º andar	3.º andar	4.º andar
1	V	V	V	V
2	V	V	A	V
3	V	A	V	V
4	A	V	V	V
5	A	V	A	V
6	V	V	V	A
7	V	A	V	A
8	A	V	V	A

E se o prédio tiver $n$ andares? Vejamos as várias situações para 1, 2, 3, 4, 5 andares e formulemos uma conjetura. Se o prédio tiver:

• 1 andar → 2 possibilidades (verde ou amarelo);
• 2 andares → 3 possibilidades — basta acrescentar um andar a cada uma das situações anteriores: esse andar poderá ser pintado de verde, não havendo restrições, logo há 2 possibilidades, ou amarelo, mas aqui esta opção só é permitida se o andar anterior for verde, o que nos dá mais uma possibilidade: $2 + 1$;
• 3 andares → 5 possibilidades — seguindo o raciocínio anterior, serão os 3 anteriores (casos em que o 3.º andar é pintado de verde) + 2 (casos em que o 3.º andar é amarelo, o que se aplica às anteriores em que o 2.º andar era verde);
• 4 andares → 8 possibilidades (tabela acima);
• 5 andares — para o 5.º andar: na cor verde temos as 8 situações anteriores; na cor amarela, temos 5 possibilidades — todas as anteriores em que o 4.º andar é verde. Assim, há $8 + 5 = 13$ maneiras de pintar o prédio;
• o próximo andar poderá ter $13 + 8 = 21$.

N.º de andares	1	2	3	4	5	6	7	…
N.º de possibilidades	2	3	5	8	13	21	34	…

A solução lembra a sequência de Fibonacci! Espantoso! Seja $(u_n)$ a sucessão que dá o número de maneiras de pintar o prédio com $n$ andares. Tem-se

$$\begin{cases} u_1 = 2 \\ u_2 = 3 \\ u_{n+2} = u_n + u_{n+1}, \quad n \in \mathbb{N} \end{cases}$$

Recorda que na sucessão (ou sequência) de Fibonacci cada elemento é obtido somando os dois anteriores a ele, sendo os dois primeiros 1 e 1, ou seja, 1, 1, 2, 3, 5, 8, 13, 21, 34, …