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

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 $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.

Bibliografia

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

Voci correlate

• Codifica di Fibonacci
• Edouard Zeckendorf

Altri progetti

Altri progetti

• Wikimedia Commons

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

Collegamenti esterni

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