Exemplo 11. Imagine that um prédio de quatro andares deva ser pintado usando-se uma cor para cada andar. Sabendo que as cores utilizadas podem ser ...

O exemplo apresenta um problema de contagem que envolve a sequência de Fibonacci. Para resolver o problema, podemos utilizar a sequência de Fibonacci para contar o número de maneiras possíveis de pintar o prédio. Como o primeiro andar pode ser pintado de verde ou amarelo, temos 2 possibilidades. Para o segundo andar, se o primeiro andar foi pintado de verde, só podemos pintar o segundo andar de amarelo, e se o primeiro andar foi pintado de amarelo, podemos pintar o segundo andar de verde ou amarelo, ou seja, temos 2 possibilidades. Para o terceiro andar, se o segundo andar foi pintado de verde, podemos pintar o terceiro andar de verde ou amarelo, e se o segundo andar foi pintado de amarelo, só podemos pintar o terceiro andar de verde, ou seja, temos 2 possibilidades. Para o quarto andar, se o terceiro andar foi pintado de verde, podemos pintar o quarto andar de verde ou amarelo, e se o terceiro andar foi pintado de amarelo, só podemos pintar o quarto andar de verde, ou seja, temos 2 possibilidades. Assim, o número total de maneiras possíveis de pintar o prédio de 4 andares é 2 x 2 x 2 x 2 = 16. Para um prédio de n andares, podemos utilizar a fórmula de Fibonacci para calcular o número de maneiras possíveis de pintar o prédio. Seja F(n+1) o número de maneiras possíveis de pintar um prédio de n+1 andares, temos: F(n+1) = F(n) + F(n-1) sendo F(1) = 2 e F(2) = 3.