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.

Un intero è rappresentato secondo Zeckendorf se è espresso come somma di numeri di Fibonacci e se tale somma verifica le seguenti proprietà:

1. tra gli addendi della somma non compaiono numeri di Fibonacci consecutivi
2. gli addendi sono distinti, ovvero non ci sono addendi doppioni
3. tra gli addendi della somma non compaiono ${\displaystyle F_{0}}$ e ${\displaystyle F_{1}}$

Una somma che rispetti queste condizioni è detta rappresentazione di Zeckendorf.

A titolo di chiarimento si mostra esplicitamente la rappresentazione di Zeckendorf del numero cento:

${\displaystyle 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:

${\displaystyle 100=55+34+8+3=F_{10}+F_{9}+F_{6}+F_{4}}$

• Questa rappresentazione non è di Zeckendorf, perché ${\displaystyle 55}$ e ${\displaystyle 34}$ sono numeri di Fibonacci consecutivi.

${\displaystyle 100=55+21+21+3=F_{10}+F_{8}+F_{8}+F_{4}}$

• Questa rappresentazione non è di Zeckendorf, perché il numero di Fibonacci ${\displaystyle 21}$ compare due volte.

${\displaystyle 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 ${\displaystyle F_{1}}$, addendo vietato dalla terza richiesta fatta nella definizione.

Di seguito dimostreremo che, fissato un qualunque intero positivo ${\displaystyle 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 ${\displaystyle N}$ il numero che si vuole rappresentare. Si introduca la funzione:

${\displaystyle P(N):=\left\{F_{i}\in \left\{F_{n}\right\}|F_{i}\leq N,F_{i+1}>N\right\}}$

Che, dato un numero ${\displaystyle N}$, restituisce il più grande numero di Fibonacci non più grande di ${\displaystyle N}$ o equivalentemente, il numero di Fibonacci precedente il primo numero di Fibonacci più grande di ${\displaystyle N}$.
Si può indicare questo numero con il nome parte di Zeckendorf o se si vuole parte di Fibonacci del numero ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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.

In simboli:

${\displaystyle P(N_{n+1})\not =F_{(j_{n}-1)}\;\forall n\in \mathbb {N} }$

Sostituendo nella definizione logica di ${\displaystyle P}$ si osserva che, affinché sia vera la disuguaglianza, basta chiedere che sia identicamente vera la seguente disequazione:

${\displaystyle N_{n+1}<F_{({j_{n}}-1)}\;\forall n\in \mathbb {N} }$

Si supponga dunque per assurdo che non sia così per qualche n:

${\displaystyle N_{n+1}\geq F_{(j_{n}-1)}}$

Utilizzando la definizione ricorsiva della successione degli avanzi:

${\displaystyle N_{n}-F_{(j_{n})}\geq F_{(j_{n}-1)}}$

ovvero

${\displaystyle N_{n}\geq F_{(j_{n})}+F_{(j_{n}-1)}=F_{(j_{n}+1)}}$

Ma per ipotesi è vero proprio l'opposto per ipotesi.

${\displaystyle 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 ${\displaystyle F_{(j_{n}+1)}}$ a due bocconi più piccoli anche se di peso equivalente ${\displaystyle F_{(j_{n})}+F_{(j_{n}-1)}=F_{(j_{n}+1)}}$.

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 ${\displaystyle F_{0}=0}$, queste tre ipotesi implicano che, per ogni ${\displaystyle N}$ naturale non nullo, esiste sempre un numero di Fibonacci positivo ${\displaystyle F_{i}}$ più piccolo o uguale, in simboli:

${\displaystyle \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.

${\displaystyle N_{1}>N_{2}>...>N_{k}}$

${\displaystyle F_{(j_{1})}>F_{(j_{2})}>...>F_{(j_{k})}>0}$

${\displaystyle 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.

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 ${\displaystyle F_{1}=1}$.
Ciò è dovuto al fatto che:

${\displaystyle F_{1}=F_{2}=1}$

è che affinché ${\displaystyle F_{1}}$ possa essere un'uscita dell'algoritmo, dovrebbe esistere un intero che verifichi la seguente e:

${\displaystyle 1\leq N,1>N}$

Ma tale intero ovviamente non esiste.
Per ragioni analoghe, posto ${\displaystyle F_{-1}=1}$ per la definizione ricorsiva, l'algoritmo non può produrre come uscita ${\displaystyle F_{0}}$ .

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

L'unicità si ottiene efficientemente per assurdo. Si supponga che un numero ${\displaystyle M>0}$ abbia due decomposizioni distinte.

${\displaystyle M=F_{j_{i}}+...+F_{j_{1}}}$

${\displaystyle M=F_{k_{l}}+...+F_{k_{1}}}$

Si eliminino per prima cosa da ambo le rappresentazioni gli elementi ripetuti ovvero gli:

${\displaystyle F_{n}|F_{k_{l}}=F_{j_{i}}}$

Il nuovo numero così ottenuto sarà indicato come ${\displaystyle 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.

${\displaystyle M^{*}=F_{j_{i^{*}}^{*}}+...+F_{j_{1}^{*}}}$

${\displaystyle 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 ${\displaystyle M}$ distinte, anche ${\displaystyle 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:

${\displaystyle F_{j_{1}^{*}}>F_{k_{1}^{*}}}$

Per il seguito si introduce la seguente identità, valida per ${\displaystyle n\geq m+1\geq 0}$ :

${\displaystyle 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 ${\displaystyle F_{m+1}}$.
Si può scrivere a questo punto la seguente catena di equazioni e disequazioni:

${\displaystyle 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 ${\displaystyle M^{*}}$ rappresentato secondo Zeckendorf, l'ultimo termine della disequazione ${\displaystyle F_{k_{1}^{*}-1}}$ è tale da soddisfare la seguente disequazione:

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle M^{*}>0}$ rappresentato secondo Zeckendorf, è quantomeno ${\displaystyle F_{1}=1}$, ergo :

${\displaystyle 0\geq (F_{j_{i^{*}}^{*}}+...+F_{j_{2}^{*}})+F_{k_{l^{*}}^{*}-1}>0+1}$

Assurdo.

Ogni rappresentazione di Zeckendorf di un numero è pertanto unica

I numeri codificati secondo Zeckendorf si possono scrivere in maniera analoga ai numeri binari. In particolare, posti

${\displaystyle \sum \epsilon _{i}\in \left\{0,1\right\}}$

Si possono scrivere banalmente i numeri rappresentati secondo Zeckendorf nella forma:

${\displaystyle \sum \epsilon _{i}F_{i}}$

e omettendo i moltiplicandi di Fibonacci come stringa binaria

Alcuni esempi chiariranno meglio cosa si è fatto:

${\displaystyle 9_{10}=8_{10}+1_{10}=F_{6}+F_{2}=0010001}$

${\displaystyle 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).

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.

${\displaystyle 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.

${\displaystyle 0010011\;\;}$ 1º Passaggio

${\displaystyle 00100001}$ 2º Passaggio

Tale operazione è giustificata dal fatto che

${\displaystyle F_{n+1}=F_{n}+F_{n-1}}$

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à:

${\displaystyle F_{n}+F_{n}=F_{n-2}+F_{n-1}+F_{n}=F_{n-2}+F_{n+1}}$

A titolo di esempio:

${\displaystyle 3_{10}+11_{10}=14_{10}}$

Che con la notazione binaria introdotta diventa:

${\displaystyle 00001\;\;\;\;+}$ Addendo

${\displaystyle 0000101=}$ Addendo

Che computato diventa

${\displaystyle 0000001+}$ Parziale

${\displaystyle 001001\;\;=}$ Riporto

Che a sua volta da

${\displaystyle 0010011}$ che non è una rappresentazione Zeckendorf

Applicando la procedura di normalizzazione si ottiene infine:

${\displaystyle 00100001}$

E che ci conferma che, anche con questa notazione:

${\displaystyle 3_{10}+11_{10}=F_{7}+F_{2}=13_{10}+1_{10}=14_{10}}$

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.

${\displaystyle \circ :=\mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N} }$

${\displaystyle (a,b)=a\circ b}$

Date le rappresentazioni di Zeckendorf di due naturali

${\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)}$

${\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)}$

si definisce prodotto di Fibonacci

${\displaystyle 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:

${\displaystyle a=5_{10}=F_{5}}$

${\displaystyle b=4_{10}=F_{2}+F_{4}}$

Applicando la definizione e mandando avanti i conti

${\displaystyle 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.

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

• Codifica di Fibonacci
• Edouard Zeckendorf

• Wikimedia Commons contiene immagini o altri file su teorema di Zeckendorf

• (EN) Eric W. Weisstein, Teorema di Zeckendorf / Teorema di Zeckendorf (altra versione), su MathWorld, Wolfram Research.
• Zeckendorf's theorem su cut-the-knot