Teorema di Zeckendorf

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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]

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 e

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

Esempi e falsi esempi[modifica | modifica wikitesto]

A titolo di chiarimento si mostra 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 a ogni passo il più grande numero di Fibonacci possibile.
Segue una formalizzazione di questa idea.

Sia il numero che si vuole rappresentare. Si introduca 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 .
Si può indicare questo numero con il nome parte di Zeckendorf o se si vuole parte di Fibonacci del numero .
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:

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 .

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:

Che chiameremo successione degli avanzi e:

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

In simboli:

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

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

Utilizzando la definizione ricorsiva della successione degli avanzi:

ovvero

Ma per ipotesi è vero proprio 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 si può 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 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 , 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 e una sola volta.

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

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

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

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

Si eliminino 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à si supponga a questo punto:

Per il seguito si introduce la seguente identità, valida per  :

Dove la disequazione è vera perché la successione di Fibonacci è crescente e la seconda parte è semplicemente la definizione ricorsiva di .
Si può scrivere a questo punto 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

Si possono 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]

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.

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.

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 si ottiene 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 sé 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]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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