Teoremas de Zeckendorf
Flavio Henrique de Oliveira
Ali Messaoudi
Instituto de Biociências, Letras e Ciências Exatas - IBILCE/UNESP
São José do Rio Preto, SP
E-mail: [email protected], [email protected]
RESUMO
Sequência de Fibonacci é uma sucessão de números que aparece em muitos fenômenos da natureza. O italiano Leonardo Fibonacci definiu-a por volta do século XII. Usualmente, a sequência
de Fibonacci começa com 0 e 1 e os números seguintes são definidos recursivamente como a soma
dos dois números anteriores. Portato, os primeiros termos da sequência de Fibonacci são
0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 146, . . .
Ao transformar esses números em quadrados e dispô-los de maneira geométrica é possı́vel
traçar uma espiral perfeita, cuja existência é observada em várias situações. Por exemplo, na
concha do caramujo, na cauda do camaleão e nas presas de marfim de um elefante (caso não
parassem de crescer). As sementes do girassol também preenchem o miolo dispostas em dois
conjuntos de espirais. Geralmente, 21 no sentido horário e 34 no anti-horário.
Denotando os elementos da sequência de Fibonacci por
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 , a
√
1+ 5
sequência (Fn /Fn−1 )n≥2 converge para o número φ = 2 , chamado número de ouro, ou ainda,
proporção áurea. Tal proporção aparece frequentemente nas artes, pois representa ideologicamente a beleza divina, já que é considerada agradável aos olhos. O valor φ é de aproximadamente
1,618. Encontramos o número de ouro e a sequência de Fibonacci em obras de arte, tais como
Monalisa e o Homem Vitruviano de Leonardo da Vinci, e em obras literárias tais como o poema
épico Ilı́ada de Homero, Os Lusı́adas, de Camões, e Eneida, de Virgı́lio. A razão áurea ainda
aparece em construções, tais como as pirâmides do Egito, pois cada bloco das pirâmides é 1,618
vezes maior que o bloco do nı́vel imediatamente acima e, em algumas, as câmaras internas têm
comprimento 1,618 vezes maior que sua largura. Além disso, a largura e altura do Partenon
estão na proporção áurea, o que mostra que os gregos já conheciam o número de ouro.
Não é difı́cil provar que qualquer número inteiro maior do que zero é escrito como soma de
elementos da sequência de Fibonacci. Além disso, se colocarmos a restrição de que dois elementos consecutivos da sequência de Fibonacci não estejam na soma, teremos a unicidade dessa
representação.
Apresenta-se neste trabalho um estudo relacionado às generalizações da sequência de Fibonacci, que são as sequências de K-bonacci e os vetores de K-bonacci. Pretendemos demonsrar
que todo número inteiro maior do que zero é escrito como soma de elementos da sequência de
K-Bonacci e que, sob algumas restrições, essa representação é única (e praticamente análoga à
da sequência de Fibonacci). Até mesmo o algoritmo para encontrar essa representação é similar.
Para escrever os elementos de Zk−1 como soma de vetores de K-bonacci de maneira única não
há um algoritmo, mas é possı́vel provar a existência dessa representação, o que faremos por
indução. Inicialmente, definamos o que é uma sequência de K-bonacci, para todo K ≥ 2:
Definição 0.1 (Sequência de K-bonacci) A sequência de K-bonacci é definida recursivamente por
Fi = 0
para − k + 2 ≥ i ≥ 0
F1 = 1
Fi =
k
X
Fi−j ,
para i ∈ Z
j=1
Note que para K = 2, a sequência definida acima é exatamente a sequência de Fibonacci.
Teorema 0.1 (Primeiro Teorema de Zeckendorf ) Todo n ∈ Z∗+ pode ser escrito de maneira
única como combinação linear de elementos da sequência de K-bonacci sobre Z2 , isto é,
X
cj Fj
n=
j≥2
tal que cj ∈ {0, 1} e cj cj+1 . . . cj+k−1 = 0 para todo j.
A sequência {cj } que satisfaz cj ∈ {0, 1} e cj cj+1 . . . cj+k−1 = 0 para todo j é chamada de
representação padrão, à qual denotaremos simplesmente por (RP ).
Definição 0.2 (Vetores de K-bonacci) Os vetores de K-Bonacci em Zk−1 são obtidos recursivamente por
→
−
→
−
X0 = 0
→
−
→
X =−
e ,
para 1 ≤ i ≤ k − 1
−i
−
→
Xn =
i
k
X
−
→
X n−i ,
para todo n ∈ Z∗+
i=1
k−1
X−
−
→
→
−
→
X n = X n+k −
X n+i ,
para todo n ∈ Z∗−
i=1
−
em que →
e i é o i-ésimo vetor canónico de Rk−1
O principal teorema deste trabalho é o resultado a seguir, que generaliza um resultado já
conhecido para sequências de Fibonacci.
Teorema 0.2 (Segundo Teorema de Zeckendorf ) Todo vetor de Zk−1 tem uma única representação padrão (RP), isto é,
X −
→
→
−
v =
ci X −i
i≥1
em que ci ∈ {0, 1} e ci ci+1 . . . ci+k−1 = 0 para todo i.
A fim de ilustrar o resultado definimos o conjunto dos vetores com uma representação n-bit
como sendo
n
X
→
−
→
→
D = {−
v ∈ Z2 ; −
v =
c X }.
n
i
−i
i=1
Segue da definição que a cardinalidade de Dn é Fn+2 , onde Fi é um elemento da sequência
→
de tribonacci (K=3). Note que Di ⊂ Dj para todo i ≤ j e que todo −
v ∈ Z2 pertence a algum
Di . A partir dos conjuntos Di , quando i cresce, é possı́vel construir uma figura conhecida como
fractal de Rauzy, a qual pretendemos apresentar neste trabalho.
Classificação: Teoria dos números (11 - Number theory)
Palavras chave: Sequência de K-bonacci, Vetor de K-bonacci, Zeckendorf, Fractal de Rauzy.
Referências
[1] P. G. Anderson, M. Bicknell-Johnson, Multidimensional Zeckendorf Representations, (2010)
[2] M. W. Bunder, Zeckendorf representations using negative Fibonacci numbers, The Fibonacci Quarterly, 30.2 (1992), 111?115.
[3] L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Pellian representations, The Fibonacci
Quarterly, 10.5 (1972), 449?488.
[4] A. S. Fraenkel, Systems of numeration, American Mathematical Monthly, 92 (1985),
105?114.
[5] J. Shallit, What this country needs is an 18 piece, Mathematical Intelligencer, 25 (2003),
Part 2:20?23.
[6] E. Zeckendorf, Repr´esentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Liege, 41 (1972), 179?182.