title: Teorema di Zeckendorf
text: # Teorema di Zeckendorf
  
  Il teorema di Zeckendorf, dal matematico belga Edouard Zeckendorf, è un teorema sulla rappresentazione di interi come somme di numeri di Fibonacci; esso afferma che ogni intero ha una e una sola rappresentazione di Zeckendorf.
  
  ## Definizione di una rappresentazione di Zeckendorf
  
  Un intero è rappresentato secondo Zeckendorf se è espresso come somma di numeri di Fibonacci e se tale somma verifica le seguenti proprietà:
  
  * tra gli addendi della somma non compaiono numeri di Fibonacci consecutivi
  * gli addendi sono distinti, ovvero non ci sono addendi doppioni
  * tra gli addendi della somma non compaiono $F_{0}$ e $F_{1}$
  
  Una somma che rispetti queste condizioni è detta rappresentazione di Zeckendorf.
  
  ### Esempi e falsi esempi
  
  A titolo di chiarimento si mostra esplicitamente la rappresentazione di Zeckendorf del numero cento:
  
      $100=89+8+3=F_{11}+F_{6}+F_{4}$
  
  Non è difficile, partendo dalla rappresentazione fornita e ricordando le proprietà di costruzione dei numeri di Fibonacci, esprimere il numero cento come somma di altri numeri di Fibonacci.
  
  Ecco degli esempi:
  
      $100=55+34+8+3=F_{10}+F_{9}+F_{6}+F_{4}$
  * Questa rappresentazione non è di Zeckendorf, perché $55$ e $34$ sono numeri di Fibonacci consecutivi.
  
      $100=55+21+21+3=F_{10}+F_{8}+F_{8}+F_{4}$
  * Questa rappresentazione non è di Zeckendorf, perché il numero di Fibonacci $21$ compare due volte.
  
      $100=89+8+2+1=F_{11}+F_{6}+F_{3}+F_{2}=F_{11}+F_{6}+F_{3}+F_{1}$
  * In questa rappresentazione il problema cambia a seconda dell'ottica scelta: si possono vedere gli addendi 1 e 2 ancora una volta numeri di Fibonacci consecutivi o, qualora si scelgano i pedici affinché non lo siano, rifiutarla perché in essa compare $F_{1}$, addendo vietato dalla terza richiesta fatta nella definizione.
  
  ## Esistenza della rappresentazione di Zeckendorf e suo ottenimento tramite algoritmo ingordo
  
  Di seguito dimostreremo che, fissato un qualunque intero positivo $N$, si può costruire una somma che soddisfa le condizioni di Zeckendorf usando un semplice algoritmo ingordo, ovvero scegliendo a ogni passo il più grande numero di Fibonacci possibile.
  
  Segue una formalizzazione di questa idea.
  
  Sia $N$ il numero che si vuole rappresentare. Si introduca la funzione:
  
      $P(N):=\left\{F_{i}\in \left\{F_{n}\right\}|F_{i}\leq N,F_{i+1}>N\right\}$
  
  Che, dato un numero $N$, restituisce il più grande numero di Fibonacci non più grande di $N$ o equivalentemente, il numero di Fibonacci precedente il primo numero di Fibonacci più grande di $N$. Si può indicare questo numero con il nome parte di Zeckendorf o se si vuole parte di Fibonacci del numero $N$. A titolo di esempio, avvantaggiandoci dell'aver già studiato il caso nel capitolo precedente, si può calcolare la parte di Zeckendorf (o di Fibonacci) del numero cento, risulta:
  
      $P(100)=F_{11}=89$
  
  L'idea dell'algoritmo ingordo è che, preso un numero iniziale, a esso si sottragga la sua parte di Zeckendorf. Così facendo si ottiene un secondo numero del quale si calcola la parte di Zeckendorf, poi nuovamente si sottrae e così via. L'insieme delle varie parti di Zeckendorf così ottenute costituirà la rappresentazione di Zeckendorf del numero $N$.
  
  Si può ora esporre questa idea appoggiandoci al formalismo delle successioni ricorrenti. Per amor di brevità e per disinteresse del nominalismo nel prosieguo ci riferiremo alle varie parti di Zeckendorf (o di Fibonacci) con il semplice nome di parti.
  
  In particolare useremo i nomi: prima parte, seconda parte, terza parte, ecc. Con l'usuale convenzione che fa sì che l'ordinale sia funzione dell'indice della parte.
  
  Si costruiscano le due successioni:
  
      $N_{n}={\begin{cases}N_{1}=N\\N_{i+1}=N_{i}-F_{j_{i}}\\se\;N_{i}=0\;la\;successione\;termina\end{cases}}$
  
  Che chiameremo successione degli avanzi e:
  
  $F_{j_{n}}:=\left\{F_{i}\in \left\{F_{n}\right\}|F_{i}\leq N_{n},F_{i+1}>N_{n}\right\}$
  
  che sarà chiamata successione delle parti.
  
  Si dimostra che la somma della successione delle parti, per come è costruita, rispetta tutte le richieste di Zeckendorf.
  
  ### Lemma 1: Due parti successive non sono mai numeri di Fibonacci successivi
  
  In simboli:
  
      $P(N_{n+1})\not =F_{(j_{n}-1)}\;\forall n\in \mathbb {N}$
  
  Sostituendo nella definizione logica di $P$ si osserva che, affinché sia vera la disuguaglianza, basta chiedere che sia identicamente vera la seguente disequazione:
  
      $N_{n+1}<F_{({j_{n}}-1)}\;\forall n\in \mathbb {N}$
  
  Si supponga dunque per assurdo che non sia così per qualche n:
  
      $N_{n+1}\geq F_{(j_{n}-1)}$
  
  Utilizzando la definizione ricorsiva della successione degli avanzi:
  
      $N_{n}-F_{(j_{n})}\geq F_{(j_{n}-1)}$
  
  ovvero
  
      $N_{n}\geq F_{(j_{n})}+F_{(j_{n}-1)}=F_{(j_{n}+1)}$
  
  Ma per ipotesi è vero proprio l'opposto per ipotesi.
  
      $F_{(j_{n}+1)}>N_{n}$
  
  ergo, nel caso fosse, saremmo di fronte a un'incongruenza e quindi la disequazione è sempre vera e con essa la disuguaglianza.
  
  Moralmente si può dire che ciò si verifica perché l'ingordigia fa preferire all'algoritmo un unico boccone grosso di peso $F_{(j_{n}+1)}$ a due bocconi più piccoli anche se di peso equivalente $F_{(j_{n})}+F_{(j_{n}-1)}=F_{(j_{n}+1)}$.
  
  ### Ogni addendo compare una e una sola volta
  
  Questo risultato si ottiene agevolmente a partire dallo studio delle tre successioni che compaiono all'interno della sezione.
  
  Per lo studio della successione di Fibonacci si rimanda alla voce specifica e ci si limita qui a prendere nota che essa è positiva, divergente e crescente per ogni indice positivo.
  
  Dal risultato precedente segue, per costruzione, che la successione degli avanzi è positiva e sempre decrescente.
  
  Ciò si verifica perché l'enne+1-esimo avanzo è ottenuto, per costruzione, come differenza di un numero positivo (l'avanzo precedente) con un numero di Fibonacci inferiore o uguale (la parte dell'avanzo precedente) e certamente positivo. Questa proprietà è legata al fatto che la successione di Fibonacci è crescente, positiva, divergente e si ha $F_{0}=0$, queste tre ipotesi implicano che, per ogni $N$ naturale non nullo, esiste sempre un numero di Fibonacci positivo $F_{i}$ più piccolo o uguale, in simboli:
  
  $\forall n\in \mathbb {N^{+}} ,\;\exists \;F_{i}\in \left\{F_{n}\right\}\;|0<F_{i}\leq N$
  
  Di contro, questo secondo risultato, implica che anche la successione delle parti, essendo i numeri di Fibonacci positivi e crescenti per indici positivi, è decrescente, e questo teorema è vero tanto nelle parti quanto nei loro pedici di Fibonacci.
  
  In simboli i tre risultati si sintetizzano.
  
      $N_{1}>N_{2}>...>N_{k}$
      $F_{(j_{1})}>F_{(j_{2})}>...>F_{(j_{k})}>0$
      $j_{1}>j_{2}>...>j_{k}>0$
  
  In particolare, l'ultima catena di disequazioni, garantisce che ogni numero di Fibonacci compaia una e una sola volta.
  
  ### L'algoritmo non produce mai come risultati $F_{1}$ o $F_{0}$
  
  Per quel che riguarda l'assenza di F_1 ci si rifà alla definizione di algoritmo ingordo, e si osserva che esso non potrà mai, per costruzione logica, fornire come uscita $F_{1}=1$. Ciò è dovuto al fatto che:
  
      $F_{1}=F_{2}=1$
  
  è che affinché $F_{1}$ possa essere un'uscita dell'algoritmo, dovrebbe esistere un intero che verifichi la seguente e:
  
      $1\leq N,1>N$
  
  Ma tale intero ovviamente non esiste.
  
  Per ragioni analoghe, posto $F_{-1}=1$ per la definizione ricorsiva, l'algoritmo non può produrre come uscita $F_{0}$ .
  
  ### L'algoritmo termina sempre in un numero finito di passaggi
  
  Si è dimostrato precedentemente che l'algoritmo produce sempre avanzi positivi minori dell'avanzo iniziale, i numeri positivi minori di N sono un numero finito, ergo l'algoritmo si arresta in un numero finito di passaggi
  
  ## Unicità della rappresentazione di Zeckendorf
  
  L'unicità si ottiene efficientemente per assurdo. Si supponga che un numero $M>0$ abbia due decomposizioni distinte.
  
      $M=F_{j_{i}}+...+F_{j_{1}}$
      $M=F_{k_{l}}+...+F_{k_{1}}$
  
  Si eliminino per prima cosa da ambo le rappresentazioni gli elementi ripetuti ovvero gli:
  
      $F_{n}|F_{k_{l}}=F_{j_{i}}$
  
  Il nuovo numero così ottenuto sarà indicato come $M^{*}$, ed avrà anch'esso due rappresentazioni. Ovviamente, essendo scomparsi dei termini, gli indici andranno riassegnati e ad essere cambiato saranno anche il loro complessivo dei termini costituenti le rappresentazioni.
  
      $M^{*}=F_{j_{i^{*}}^{*}}+...+F_{j_{1}^{*}}$
      $M^{*}=F_{k_{l^{*}}^{*}}+...+F_{k_{1}^{*}}$
  
  Avendo solamente tolto addendi entrambe le rappresentazioni ottenute saranno ancora di Zekendorf; non c'è infatti rischio di aver aggiunto doppioni o addendi in posizioni vietate. Inoltre, dato che abbiamo supposto le due rappresentazioni di $M$ distinte, anche $M^{*}>0$ , poiché somma di quantità positive e non nulle. Il caso in cui tutti i termini si fossero elisi vicendevolmente va escluso perché, se così fosse, verrebbe meno l'ipotesi che le due rappresentazioni siano distinte.
  
  Senza perdere di generalità si supponga a questo punto:
  
      $F_{j_{1}^{*}}>F_{k_{1}^{*}}$
  
  Per il seguito si introduce la seguente identità, valida per $n\geq m+1\geq 0$ :
  
      $F_{n}\geq F_{m+1}=F_{m}+F_{m-1}$
  
  Dove la disequazione è vera perché la successione di Fibonacci è crescente e la seconda parte è semplicemente la definizione ricorsiva di $F_{m+1}$. Si può scrivere a questo punto la seguente catena di equazioni e disequazioni:
  
      $F_{k_{l^{*}}^{*}}+...+F_{k_{2}^{*}}+F_{k_{1}^{*}}=(F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{j_{1}^{*}}\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{k_{1}^{*}}+F_{k_{1}^{*}-1}$
  
  Ora, essendo il numero $M^{*}$ rappresentato secondo Zeckendorf, l'ultimo termine della disequazione $F_{k_{1}^{*}-1}$ è tale da soddisfare la seguente disequazione:
  
      $F_{k_{1}^{*}-1}\geq F_{k_{2}^{*}}+F_{k_{2}^{*}-1}$
  
  e questo perché le rappresentazioni di Zeckendorf non ammettono parti successive che siano numeri di fibonacci successivi. Sostituendo anche questa disequazione nella catena:
  
      $M^{*}=F_{k_{l^{*}}^{*}}+...+F_{k_{2}^{*}}+F_{k_{1}^{*}}\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{k_{1}^{*}}+F_{k_{2}^{*}}+F_{k_{2}^{*}-1}$
  
  Che iterato fino alla fine del processo da:
  
      $M^{*}=F_{k_{l^{*}}^{*}}+...+F_{k_{2}^{*}}+F_{k_{1}^{*}}\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+(F_{k_{l^{*}}^{*}}+...+F_{k_{2}^{*}}+F_{k_{1}^{*}})+F_{k_{l^{*}}^{*}-1}$
  
  Elidendo l'esubero rimane:
  
      $0\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{k_{l^{*}}^{*}-1}$
  
  Il primo termine tra parentesi potrebbe anche essere nullo, ma sicuramente non è negativo, il secondo, essendo $M^{*}>0$ rappresentato secondo Zeckendorf, è quantomeno $F_{1}=1$, ergo :
  
  $0\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{k_{l^{*}}^{*}-1}>0+1$
  
  Assurdo.
  
  Ogni rappresentazione di Zeckendorf di un numero è pertanto unica
  
  ## Codifica di Fibonacci binaria
  
  I numeri codificati secondo Zeckendorf si possono scrivere in maniera analoga ai numeri binari. In particolare, posti
  
      $\sum \epsilon _{i}\in \left\{0,1\right\}$
  
  Si possono scrivere banalmente i numeri rappresentati secondo Zeckendorf nella forma:
  
      $\sum \epsilon _{i}F_{i}$
  
  e omettendo i moltiplicandi di Fibonacci come stringa binaria
  
  Alcuni esempi chiariranno meglio cosa si è fatto:
  
      $9_{10}=8_{10}+1_{10}=F_{6}+F_{2}=0010001$
      $15_{10}=13_{10}+2_{10}=F_{7}+F_{3}=00010001$
  
  Tale modo di codificare i numeri, con l'omissione dei due zeri all'inizio e l'aggiunta di un uno alla fine, viene utilizzato in informatica e prende il nome di codifica di Fibonacci. Essa ha la proprietà di presentare una coppia di 1 appaiati solamente alla fine del numero e permette per questo di memorizzare gli interi senza imporre loro una dimensione a priori, come ad esempio si fa nelle architetture a 32 bit. Si tratta di un esempio di notazione dotata di codice prefisso (suffisso in questo caso).
  
  ### Normalizzazione di un numero
  
  Si supponga di avere un numero espresso in binario di Fibonacci ma non ben rappresentato secondo Zeckendorf.
  
  A titolo d'esempio un numero del genere è il seguente.
  
      $14_{10}=0011101$
  
  Che non è in forma corretta perché ci sono degli 1 adiacenti. Per portarlo nella forma corretta quello che si deve fare è leggerlo da destra a sinistra e, quando si trovano coppie di 1, sostituire queste con uno 0 e lo zero precedente la coppia (a destra)con un 1.
  
  Si applica il procedimento tutte le volte necessarie.
  
      $0010011\;\;$ 1º Passaggio
      $00100001$ 2º Passaggio
  
  Tale operazione è giustificata dal fatto che
  
      $F_{n+1}=F_{n}+F_{n-1}$
  
  ### Somma ordinaria tra rappresentazioni Zeckendorf binarie
  
  Così come si può costruire un algoritmo di somma tra numeri in binario si può fare altrettanto con i numeri rappresentati secondo Zeckendorf. Le tabelle della soma rimangono fondamentalmente invariate con l'unica differenza che, rispetto all'usuale somma binaria, i riporti non sono fatti solo in avanti di una posizione ma anche indietro di due. Il perché si capisce facilmente leggendo la seguente identità:
  
      $F_{n}+F_{n}=F_{n-2}+F_{n-1}+F_{n}=F_{n-2}+F_{n+1}$
  
  A titolo di esempio:
  
      $3_{10}+11_{10}=14_{10}$
  
  Che con la notazione binaria introdotta diventa:
  
      $00001\;\;\;\;+$ Addendo
      $0000101=$ Addendo
  
  Che computato diventa
  
      $0000001+$ Parziale
      $001001\;\;=$ Riporto
  
  Che a sua volta da
  
      $0010011$ che non è una rappresentazione Zeckendorf
  
  Applicando la procedura di normalizzazione si ottiene infine:
  
      $00100001$
  
  E che ci conferma che, anche con questa notazione:
  
      $3_{10}+11_{10}=F_{7}+F_{2}=13_{10}+1_{10}=14_{10}$
  
  ### Prodotto di Fibonacci
  
  Mediante la codifica di Zeckendorf si può definire l'operazione "prodotto di Fibonacci". Tale operazione non coincide identicamente con l'usuale moltiplicazione e non è distributiva rispetto all'usuale somma, si tratta pertanto di un'operazione binaria a sé stante.
  
      $\circ :=\mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$
         $(a,b)=a\circ b$
  
  Date le rappresentazioni di Zeckendorf di due naturali
  
      $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$
      $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$
  
  si definisce prodotto di Fibonacci
  
      $a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}$.
  
  Un contr'esempio dimostra esplicitamente la non equivalenza tra questa operazione ed il prodotto usuale, siano dunque:
  
      $a=5_{10}=F_{5}$
      $b=4_{10}=F_{2}+F_{4}$
  
  Applicando la definizione e mandando avanti i conti
  
  $5_{10}\circ 4_{10}=F_{5}\circ (F_{2}+F_{4})=F_{2+5}+F_{4+5}=F_{7}+F_{9}=13_{10}+34_{10}=47_{10}\not =20=5\times 4$
  
  Dove l'ultima parte è stata aggiunta per confronto.
  
  Knuth dimostrò il fatto notevole che questa operazione è associativa. La dimostrazione si appoggia sull'equivalenza procedurale (da un punto di vista formale) tra prodotto tra numeri scritti in binario e prodotto Fibonacci tra numeri espressi in binario di fibonacci.
  
  Si veda anche A101330.
  
  