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; esso afferma che ogni intero ha una e una sola rappresentazione di Zeckendorf.

Definizione di una rappresentazione di Zeckendorf[modifica | modifica wikitesto]

Una 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 e

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

Esempi e falsi esempi[modifica | modifica wikitesto]

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

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:

  • Questa rappresentazione non è di Zeckendorf, perché e sono numeri di Fibonacci consecutivi.
  • Questa rappresentazione non è di Zeckendorf, perché il numero di Fibonacci compare due volte.
  • 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 , addendo vietato dalla terza richiesta fatta nella definizione.

Esistenza della rappresentazione di Zeckendorf e suo ottenimento tramite algoritmo ingordo[modifica | modifica wikitesto]

Di seguito dimostreremo che, fissato un qualunque intero positivo , si può costruire una somma che soddisfa le condizioni di Zeckendorf usando un semplice algoritmo ingordo, ovvero scegliendo ad ogni passo il più grande numero di Fibonacci possibile.
Iniziamo a formalizzare questa idea.

Sia il numero che si vuole rappresentare. Introduciamo la funzione:

Che, dato un numero , restituisce il più grande numero di Fibonacci non più grande di o equivalentemente, il numero di Fibonacci precedente il primo numero di Fibonacci più grande di .
Possiamo indicare questo numero con il nome parte di Zeckendorf o se vogliamo parte di Fibonacci del numero .
A titolo di esempio, avvantaggiandoci dell'aver già studiato il caso nel capitolo precedente, possiamo calcolare la parte di Zeckendorf (o di Fibonacci) del numero cento, risulta:

L'idea dell'algoritmo ingordo è che, preso un numero iniziale, ad 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 .

Riesponiamo questa idea appoggiandoci al formalismo delle successioni ricorrenti.
Per amor di brevità e per disinteresse del nominalismo nel proseguo 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 ecc. Con l'usuale convenzione che fa si che l'ordinale sia funzione dell'indice della parte.

Costruiamo le due successioni:

Che chiameremo successione degli avanzi e:

Che chiamiamo successione delle parti.

Dimostriamo 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[modifica | modifica wikitesto]

In simboli:

Sostituendo nella definizione logica di osserviamo che, affinché sia vera la disuguaglianza, basta chiedere che sia identicamente vera la seguente disequazione:

Supponiamo dunque per assurdo che non sia cosi per qualche n:

Utilizzando la definizione ricorsiva della successione degli avanzi:

ovvero

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

ergo, nel caso fosse, saremmo di fronte a un'incongruenza e quindi la disequazione è sempre vera e con essa la disuguaglianza.

Moralmente possiamo dire che ciò si verifica perché l'ingordigia fa preferire all'algoritmo un unico boccone grosso di peso a due bocconi più piccoli anche se di peso equivalente .

Ogni addendo compare una e una sola volta[modifica | modifica wikitesto]

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 limitiamo 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 , queste tre ipotesi implicano che, per ogni naturale non nullo, esiste sempre un numero di Fibonacci positivo più piccolo o uguale, in simboli:

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.

In particolare, l'ultima catena di disequazioni, garantisce che ogni numero di Fibonacci compaia una ed una sola volta.

L'algoritmo non produce mai come risultati o [modifica | modifica wikitesto]

Per quel che riguarda l'assenza di F_1 ci rifacciamo alla definizione di algoritmo ingordo, e osserviamo che esso non potrà mai, per costruzione logica, fornire come uscita .
Ciò è dovuto al fatto che:

è che affinché possa essere un'uscita dell'algoritmo, dovrebbe esistere un intero che verifichi la seguente e:

Ma tale intero ovviamente non esiste.
Per ragioni analoghe, posto per la definizione ricorsiva, l'algoritmo non può produrre come uscita .

L'algoritmo termina sempre in un numero finito di passaggi[modifica | modifica wikitesto]

Abbiamo 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[modifica | modifica wikitesto]

L'unicità si ottiene efficientemente per assurdo. Supponiamo che un numero abbia due decomposizioni distinte.

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

Il nuovo numero così ottenuto sarà indicato come , 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.

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 distinte, anche , 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à supponiamo a questo punto:

Per il seguitò introduciamo la seguente identità, valida per  :

Dove la disequazione è vera perché la successione di Fibonacci è crescente e la seconda parte è semplicemente la definizione ricorsiva di .
Possiamo a questo punto scrivere la seguente catena di equazioni e disequazioni:

Ora, essendo il numero rappresentato secondo Zeckendorf, l'ultimo termine della disequazione è tale da soddisfare la seguente disequazione:

e questo perché le rappresentazioni di Zeckendorf non ammettono parti successive che siano numeri di fibonacci successivi. Sostituendo anche questa disequazione nella catena:

Che iterato fino alla fine del processo da:

Elidendo l'esubero rimane:

Il primo termine tra parentesi potrebbe anche essere nullo, ma sicuramente non è negativo, il secondo, essendo rappresentato secondo Zeckendorf, è quantomeno , ergo :

Assurdo.

Ogni rappresentazione di Zeckendorf di un numero è pertanto unica

Codifica di Fibonacci binaria[modifica | modifica wikitesto]

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

Possiamo scrivere banalmente i numeri rappresentati secondo Zeckendorf nella forma:

e omettendo i moltiplicandi di Fibonacci come stringa binaria

Alcuni esempi chiariranno meglio cosa si è fatto:

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[modifica | modifica wikitesto]

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

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.
Applichiamo il procedimento tutte le volte necessarie.

1º Passaggio
2º Passaggio

Tale operazione è giustificata dal fatto che

Somma ordinaria tra rappresentazioni Zeckendorf binarie[modifica | modifica wikitesto]

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

A titolo di esempio:

Che con la notazione binaria introdotta diventa:

Addendo
Addendo

Che computato diventa

Parziale
Riporto

Che a sua volta da

che non è una rappresentazione Zeckendorf

Applicando la procedura di normalizzazione otteniamo infine:

E che ci conferma che, anche con questa notazione:

Prodotto di Fibonacci[modifica | modifica wikitesto]

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 se stante.

Date le rappresentazioni di Zeckendorf di due naturali

si definisce prodotto di Fibonacci

.

Un contr'esempio dimostra esplicitamente la non equivalenza tra questa operazione ed il prodotto usuale, siano dunque:

Applicando la definizione e mandando avanti i conti

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.

Note[modifica | modifica wikitesto]


Bibliografia[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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