Successioni di Fibonacci generalizzate, con implementazione in Sage

Ricerca di teoria dei numeri

Successioni di Fibonacci generalizzate

Con implementazioni in Sage

Sebastiano Ferraris

2011

Sommario

Queste pagine sono l’evoluzione di una ricerca presentata nell’anno accademico 2008-2009 per l’esame del corso di Crittografia tenuto dal prof. Umberto Cerruti all’università di Matematica di Torino.

Oltre a diverse aggiunte e correzioni si distingue sostanzialmente dalla versione originale per le implementazioni in Sage lasciate nell’ultimo capitolo. Mi sono poi divertito a raccogliere alcuni problemi di diverse difficoltà in ogni paragrafo, dato che non esiste processo mentale che valga la pena di affrontare senza un’esperienza viva che lo sostenga.

Desidero ringraziare Francesco Giovo per l’aiuto nella stesura e per la revisione.

Nella prima parte della ricerca viene introdotta brevemente la successione di Fibonacci, con alcune delle proprietà più importanti. Infine, affrontando proprietà meno intuitive, si arriverà gradualmente ad una generalizzazione delle successioni, proposta nella seconda parte. La terza parte è una raccolta di funzioni implementate con Sage, che mi sono state di aiuto per capire meglio alcune proprietà.

Per suggerimenti, correzioni e commenti di qualsiasi tipo contattatemi pure.

sebastiano.ferraris@gmail.com

Torino, 22 dicembre 2011.

Indice

• 1 Successione di Fibonacci e proprietà principali 2
• 1.1 Il problema di Fibonacci 2
• 1.2 Proprietà principali 5
• 1.3 Fibonacci e la sezione aurea 11
• 1.4 Fibonacci dal triangolo di Tartaglia 15
• 1.5 Fibonacci e i Numeri di Lucas 17
• 1.6 La Formula di De Moivre per Lucas: verso la generalizzazione 18
• 2 Successione di Fibonacci generalizzata 20
• 2.1 Definizioni principali 20
• 2.2 Fibonacci generalizzata, come spazio vettoriale 22
• 2.3 Polinomio caratteristico 23
• 2.4 Proprietà principali 25
• 3 Implementazioni in Sage 30
• 3.1 Il problema di Fibonacci 30
• 3.2 Proprietà principali 31
• 3.3 Fibonacci e la sezione aurea 32
• 3.4 Fibonacci dal triangolo di Tartaglia 32
• 3.5 Fibonacci e i numeri di Lucas 33
• 3.6 Fibonacci generalizzata 33

Capitolo 1: Successione di Fibonacci e proprietà principali

1.1 Il problema di Fibonacci

Oltre ad aver diffuso il sistema di numerazione posizionale, Fibonaccin nel Liber abaci, rese noto il seguente problema:

Data una coppia di conigli neonati, trovare il numero di conigli che possono nascere dal loro incontro in un anno, se valgono le seguenti ipotesi:

• Ogni coniglio, dalla nascita, impiega un mese per diventare maturo.
• Ogni coppia di conigli genera una coppia di neonati ogni mese.
• Tutti i conigli sono immortali.

Se la coppia di conigli iniziali è nata, per esempio, il primo gennaio, allora il primo febbraio diventano maturi e il primo marzo generano una seconda coppia; il primo aprile, la seconda coppia diventa matura e la prima ne genera un’altra, e così via, fino ad avere il risultato espresso nella tabella sottostante:

Se rappresentiamo le coppie di conigli neonati con e le coppie di conigli maturi con allora possiamo visualizzare l’insieme di coppie per ogni mese con un’altra tabella:

Mesi G. F. M. A. M. G. L. ...

• ◦ • • • • •

◦ ◦ • • •

◦ ◦ • •

◦ ◦ •

◦ ◦ •

◦ ◦

◦ ◦

Coppie ...

◦ ◦

◦

◦

◦

◦

◦

Totale 1 1 2 3 5 8 13 ...

Possiamo notare che ogni colonna è formata dalle coppie di conigli del mese precedente, diventati tutti maturi sommati ad un numero di coppie di conigli neonati pari al numero di conigli maturi del mese precedente, quindi pari al numero totale di conigli di due mesi prima.

La successione dei numeri di conigli in vita per ogni mese costituisce la successione di Fibonacci. Si verifica immediatamente che ogni suo elemento, a partire dal terzo, è somma dei due precedenti. Può essere quindi definita per ricorrenza:

F₀ = 0

F₁ = 1

F_n = F_n−1 + F_n−2

Problemi

Problema 1.1.1 (Negativa di Fibonacci). Ci sono diverse definizioni per la successione di Fibonacci negativa, proposte ad esempio da [1]. Calcola alcuni termini di n+1

F_−n = (−1)ⁿ⁺¹ F_n

F_−n = F_−(n−1) − F_−(n−2)

e prova ad inventare qualche altra.

Problema 1.1.2 (Rappresentazione matriciale). C’è un altro modo per rappresentare i numeri di Fibonacci. Verifica che se

0 1

A = 1 1

Allora

F_n−1 F_n

Aⁿ = F_n F_n+1

Problema 1.1.3 (Numeri di Tribonacci e Tetranacci). Generalizza la successione di Fibonacci con la condizione che l’n-esimo numero sia la somma dei k precedenti, avendo definito i primi k come i primi k elementi della successione di Fibonacci.

Per k = 3 la successione è detta successione di Tribonacci. Per k = 4 la successione è detta di Tetranacci.

Problema 1.1.4. Implementa un algoritmo che calcoli il rapporto di due numeri di Fibonacci consecutivi e lista tale rapporto per i primi 500 numeri.

Problema 1.1.5 (Numeri di Repfigit). Considera l’intero M costituito da m cifre d1, d2, . . . , dm: M = d1d2 . . . dm. Allora si può definire una successione di interi

s1 = d1 + d2 + d3 + · · · + dm

s2 = s1 + d2 + d3 + · · · + dm

s3 = s1 + s2 + d3 + · · · + dm

..

. · · ·

sm = s1 + s2 + s3 + · · · + dm

Procedendo con lo stesso ragionamento anche per degli interi successivi, ci si imbatte nei numeri di Repfigit. Chi deve essere M perché si ottenga proprio la successione di Fibonacci?

Problema 1.1.6. Dimostra che la somma dei primi dieci numeri consecutivi della successione di Fibonacci sono uguali al settimo numero della serie moltiplicato per 11.

1.2 Proprietà principali

Ora possiamo addentrarci nelle proprietà della successione di Fibonacci ([4] e [5]).

Proprietà 1.2.1 (Primalità degli elementi consecutivi). Due termini consecutivi della successione sono primi fra loro.

Dimostrazione. Per induzione: per n = 1 verifichiamo la tesi

MCD(F₁, F₂) = MCD(1, 1) = 1

Passo induttivo: prendiamo per vero che

MCD(F_n−1, F_n) = 1

da cui per l’identità di Bézout

∃ m, n ∈ Z | mF_n−1 + nF_n = 1

se per assurdo negassimo il passo successivo, allora

MCD(F_n, F_n+1) ≠ 1

Sempre per l’identità di Bézout, abbiamo che

∀a, b ∈ Z | aF_n + bF_n+1 ≠ 1

ma sapendo che F_n+1 = F_n−1 + F_n

si ha

aF_n + b(F_n−1 + F_n) = 1

cioè ∀a, b ∈ Z

bF_n−1 + (a + b)F_n = 1

In contraddizione con l’ipotesi induttiva.

Proprietà 1.2.2 (Somma degli elementi consecutivi). La somma dei numeri consecutivi della successione, dal primo all’n-esimo, a cui viene sommato 1, risulta essere uguale ad un altro numero della successione che segue di due posti l’n-esimo scelto.

Dimostrazione. Dimostriamo per induzione. La tesi può essere riformulata nel seguente modo:

∑_j=1ⁿ (F_j) + 1 = F₁ + F₂ + ... + F_n + 1 = F_n+2

Passo iniziale: per n = 1 verifichiamo la tesi

F₁ + 1 = F₃ = 1 + 1 = 2

Passo induttivo: sia vero per n − 1

∑_j=1ⁿ⁻¹ (F_j) + 1 = F_n+1

Sommando F_n ad entrambi i membri

∑_j=1ⁿ⁻¹ (F_j) + F_n + 1 = F_n + F_n+1

e sapendo che F_n + F_n+1 = F_n+2, risulta

∑_j=1ⁿ (F_j) + 1 = F_n+2

Proprietà 1.2.3 (Somma di elementi dispari). Sommando solo gli elementi di posto dispari della successione, si ottiene l’elemento della successione successivo all’ultimo sommato.

Dimostrazione. Come prima dimostriamo per induzione. La tesi può essere riformulata nel seguente modo:

∑_j=0ⁿ F_2j+1 = F_2n+2

Passo iniziale: per n = 0 si verifica la tesi

F₁ = F₂ = 1

Passo induttivo: sia vero per n − 1

∑_j=0ⁿ⁻¹ F_2j+1 = F₁ + F₃ + ... + F_2n−1 = F_2n = F_2(n−1)+2

Sommiamo ad entrambi i membri F_2n+1 ed ottengo

F₁ + F₃ + ... + F_2n−1 + F_2n+1 = F_2n + F_2n+1

da cui, sapendo che F_n + F_n+1 = F_n+2, risulta

∑_j=0ⁿ F_2j+1 = F_2n+2

Proprietà 1.2.4 (Scomposizione). Per i numeri di Fibonacci vale la seguente equazione:

F_a+b = F_b+1F_a + F_bF_a−1

Dimostrazione. Consideriamo la seguente catena di equazioni:

F_n = 1F_n−1 + F_n−2

F_n = 1(F_n−2 + F_n−3) + F_n−2 = 2F_n−2 + F_n−3

F_n = 2(F_n−3 + F_n−4) + F_n−3 = 3F_n−3 + 2F_n−4

F_n = 3(F_n−4 + F_n−5) + F_n−4 = 5F_n−4 + 3F_n−5

.. ..

. .

F_n = F_k+1F_n−k + F_kF_n−k−1 per k < n

Capito il meccanismo, la dimostrazione rigorosa dell’ultima equazione può essere trovata per induzione (esercizio).

Se poi in F_n = F_k+1F_n−k + F_kF_n−k−1 effettuiamo le seguenti sostituzioni: a + b = n, k = b, e quindi per n − k = a, allora abbiamo che

F_a+b = F_b+1F_a + F_bF_a−1

Proprietà 1.2.5 (Divisibilità). Dati gli interi positivi m, n, si ha che m | n ⇒ F_m | F_n.

Dimostrazione. Dimostrazione costruttiva. Per ipotesi abbiamo che se m | n allora ∃s | n = sm. Quindi, per sostituzione, la nuova tesi è F_m | F_sm. La dimostrazione parte dalla seguente catena di equazioni, vista anche nella dimostrazione precedente:

F_sm = 1F_sm−1 + F_sm−2

= 2F_sm−2 + F_sm−3

= 3F_sm−3 + 2F_sm−4

..

.

= F_k+1F_sm−k + F_kF_sm−k−1 per k < sm

Posso procedere finché k = (s − 1)m, quindi

..

.

= F_(s−1)m+1F_{sm−(s−1)m} + F_(s−1)mF_{sm−(s−1)m−1}

= F_αF_m + F_βF_m

per qualche intero α e β. A questo punto ripetiamo la stessa catena di equazioni per F_(s−1)m, fermandoci a k = (s − 2)m:

F_sm = F₀F_sm + (F_αF_m + F_βF_m)F₀

Procedendo in questo modo, cioè ripetendo la catena di equazioni per F_(s−h)m, finché di volta in volta non si arriva a k = (s − h − 1)m per h = 1, . . . , s + 2 arriveremo ad una somma di fattori, ciascuno dei quali è moltiplicato per F_m.

Raccogliendo il fattore comune si ha:

F_sm = δF_m

Proprietà 1.2.6 (Euclide per Fibonacci). Per la successione di Fibonacci vale un analogo dell’algoritmo di Euclide dato dalla seguente equazione:

MCD(F_m, F_n) = MCD(F_n, F_r)

Dove r è il resto della divisione di m per n, cioè m = qn + r.

Dimostrazione. Abbiamo subito che:

MCD(F_m, F_n) = MCD(F_n, F_qn+r)

Per la proprietà di Scomposizione 1.2.4 vale

MCD(F_m, F_n) = MCD(F_n, F_qn+1F_r + F_qnF_r−1)

Ma n | nq, quindi per la proprietà della divisibilità si ha:

MCD(F_m, F_n) = MCD(F_n, F_qn+1 | F_r)

Inoltre, dato che i numeri di Fibonacci successivi sono coprimi ed F_n e F_nq abbiamo

MCD(F_m, F_n) = MCD(F_n, F_r)

Concludiamo il paragrafo con una peculiare proprietà:

Proprietà 1.2.7 (MCD per Fibonacci). Il massimo comun divisore fra due numeri di Fibonacci è ancora un numero di Fibonacci la cui posizione è data dal MCD dei loro indici.

Dimostrazione. La tesi può essere riformulata nel seguente modo:

MCD(F_i, F_j) = F_MCD(i,j)

Si applica l’algoritmo di Euclide per MCD(i, j), quindi:

MCD(i, j) = MCD(j, r₁) = MCD(r₁, r₂) = ... = MCD(r_n, 0) = r_n