Teorema di Zeckendorf

Da Wikipedia, l'enciclopedia libera.

Il teorema di Zeckendorf, dal matematico belga Edouard Zeckendorf, è un teorema sulla rappresentazione di interi come somme di numeri di Fibonacci.

Il teorema di Zeckendorf afferma che ogni intero positivo è rappresentabile in modo unico come la somma di uno o più numeri di Fibonacci distinti in maniera tale che la somma non includa due numeri di Fibonacci consecutivi. Una somma che rispetti queste condizioni è detta rappresentazione di Zeckendorf.

Per esempio, la rappresentazione di Zeckendorf di 100 è

100 = 89 + 8 + 3

Ci sono altri modi per rappresentare 100 come somma di numeri di Fibonacci, per esempio

100 = 89 + 8 + 2 + 1
100 = 55 + 34 + 8 + 3

ma queste non sono rappresentazioni di Zeckendorf perché 1 e 2 sono numeri di Fibonacci consecutivi, e lo stesso vale per 34 e 55.

Per qualsiasi intero positivo fissato, si può trovare una rappresentazione che soddisfi le condizioni del teorema di Zeckendorf usando un semplice algoritmo greedy, scegliendo ad ogni passo il più grande numero di Fibonacci possibile. È più difficile dimostrare che la rappresentazione così ottenuta sia l'unica, cioè che non esistano altre rappresentazioni che soddisfino le stesse condizioni.

Moltiplicazione di Fibonacci[modifica | modifica sorgente]

Si può definire la seguente operazione a\circ b sui numeri naturali a, b: date le rappresentazioni di Zeckendorf a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2) e b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2) si definisce prodotto di Fibonacci a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}. Per esempio la rappresentazione di Zeckendorf di 1 è 1=F_2 (poiché non sono permesse rappresentazioni con F_1) quindi 1\circ 1=F_{2+2}=F_4=3.

Knuth dimostrò il fatto notevole che questa operazione è associativa. Vedi anche A101330.

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Bibliografia[modifica | modifica sorgente]

  • D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57–60


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica