Teorema 11. Teorema de Zeckendorf. Todo número inteiro positivo pode ser escrito de modo único como soma de termos da sequência de Fibonacci, de ín...

Teorema 11. Teorema de Zeckendorf. Todo número inteiro positivo pode ser escrito de modo único como soma de termos da sequência de Fibonacci, de índices não consecutivos e maiores que 1. Demonstração. Iniciamos mostrando a existência da representação, usando indução em n. Temos que 1 = F2, 2 = F3, 3 = F4, 4 = 3 + 1 = F4 +F2, 5 = F5, 6 = F5 + F2 e, com isso, o resultado vale para todo n 6 6. Supõe que o resultado vale até um certo k. Se k+1 é um termo da sequência de Fibonacci, então está provado. Caso contrário, existe j tal que Fj < k+ 1 < Fj+1. Logo a = k+ 1−Fj é menor que Fj−1. De fato, se a > Fj−1, então k + 1 = a + Fj > Fj−1 + Fj = Fj+1, o que dá uma contradição. Assim, por hipótese de indução, segue que a é soma de termos não consecutivos da sequência de Fibonacci, onde o maior deles é menor que Fj−1. Portanto k + 1 pode ser escrito como soma de termos não consecutivos da sequência de Fibonacci. Agora provaremos a unicidade da representação. Supõe que a representação é única até um certo k e que k+1 = Fa0 +Fa1 + · · ·+Far = Fb0 +Fb1 + · · ·+Fbs , com ai + 1 < ai+1 e bj + 1 < bj+1. Então Far 6 Fa0 + Fa1 + · · · + Far = Fb0 + Fb1 + · · · + Fbs 6 Fbs + Fbs−2 + · · · + Ft = Fbs+1 − 1, onde t = 2 se bs é par e t = 3 se bs é ímpar. Logo Far < Fbs+1 e assim ar < bs + 1, ou seja, ar 6 bs. De maneira análoga podemos mostrar que bs 6 ar e, portanto ar = bs. Usando a hipótese de indução concluímos que r − 1 = s − 1 e que ai = bj , para i, j ∈ {0, 1 . . . , r − 1}. Portanto está provada a unicidade.

O teorema de Zeckendorf afirma que todo número inteiro positivo pode ser escrito como soma de termos da sequência de Fibonacci, de índices consecutivos e maiores que 1.
A demonstração do teorema de Zeckendorf é feita por indução.
A unicidade da representação é provada por contradição.
O teorema de Zeckendorf é um exemplo de problema de contagem.