Teorema di Zeckendorf
# 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.

