Eis um exemplo para mostrar como é que os números de Fibonacci respondem a este problema.
Comece por reparar como é que este problema satisfaz as três condições da definição de Fibonacci:
F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2) quando n > 1
Neste caso, F(n) significa "o número de formas de construir paredes de altura 2 e comprimento n" em que as soluções encontradas até aqui são como já vimos:
Repare como se demonstra estas 3 condições aplicadas ao nosso problema:
F(0)=0
Não há nenhuma forma se não houver nenhum tijolo, logo F(0)=0. Isto significa que o número de maneiras de construir uma parede de altura 2 e comprimento zero é zero.
F(1)=1
Só há uma única maneira de construir uma parede com altura 2 e comprimento 1, que é pondo um tijolo em pé, logo F(1)=1.
F(n)=F(n-1)+F(n-2)
Neste caso tem que se demonstrar que isto acontece para qualquer n> 1. Considere o que acontece no final do lado esquerdo da parede...
...ou existe um só tijolo no fim
...ou então existe um tijolo ao seu lado – em qualquer dos casos terá de existir um outro tijolo no topo para se ficar com a altura 2.
Para além destes dois casos não existe mais nenhuma possibilidade de construir uma parede de altura maior que 1.
Veja com mais atenção estes dois casos:
Se se começar a construir uma parede com altura n e com um único tijolo em pé, então precisa-se de formar uma parede de comprimento n-1 para a completar. Quantas destas existem? A resposta é F(n-1) formas de construir, visto ser isso mesmo que F(n-1) significa.
A outra única maneira de construir uma parede que tenha comprimento n, é começar-se com dois tijolos colocados na horizontal um sobre o outro. Pode-se assim continuar com qualquer forma de parede com altura 2 e comprimento n-2 o que faz com que hajam F(n-2) destes.
Conclui-se assim que todas as maneiras para encontrar paredes de altura n estão contidos nestes dois casos que acabaram de ver:
Primeiro com um tijolo em pé e depois com qualquer forma de comprimento n-2
Ou então com 2 tijolos horizontais seguidos por qualquer forma de comprimento n-2
Isto quer dizer que o número de formas de comprimento n é a soma do número de formas de comprimento n-1 com o número de formas de comprimento n-2.
Em notação matemática, isto quer dizer o seguinte:
F(n)=F(n-1)+F(n-2) desde que n > 1
Concluindo, todas as condições foram verificadas, e chegou-se exactamente à definição dos números de Fibonacci.
Por vezes F(0)=0 não é aplicável, ou então não é de fácil detecção. Uma definição alternativa para os números de Fibonacci é usar a seguinte definição alternativa:
1)F(1)=1
2)F(2)=1
F(n)=F(n-1)+F(n-2) quando n > 2.
