Successioni di Fibonacci generalizzate, con implementazione in Sage

1.Successione di Fibonacci e proprietà principali

Passo iniziale: per n = 0 si verifica la tesi

F = F 1=1

1 2

−

Passo induttivo: sia vero per n 1

n−1

X F = F + F + ... + F = F = F

2j+1 1 3 2n−1 2n

2(n−1)+2

j=0

Sommiamo ad entrambi i membri F ed ottengo

2n+1

F + F + ... + F + F = F + F

1 3 2n−1 2n+1 2n 2n+1

da cui, sapendo che F + F = F , risulta

n n+1 n+2

n

X F = F

2j+1 2n+2

j=0

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

equazione F = F F + F F

a+b b+1 a b a−1

Dimostrazione. Consideriamo la seguente catena di equazioni:

F = 1F + F

n n−1 n−2

F = 1(F + F ) + F = 2F + F

n n−2 n−3 n−2 n−2 n−3

F = 2(F + F ) + F = 3F + 2F

n n−3 n−4 n−3 n−3 n−4

F = 3(F + F ) + F = 5F + 3F

n n−4 n−5 n−4 n−4 n−5

.. ..

. .

F = F F + F F per k < n

n k+1 n−k k n−k−1

Capito il meccanismo, la dimostrazione rigorosa dell’ultima equazione può essere

trovata per induzione (esercizio).

Se poi in F = F F +F F effettuiamo le seguenti sostituizioni : a+b = n,

n k+1 n−k k n−k−1

−

k = b, e quindi per n k = a, allora abbiamo che

F = F F + F F

a+b b+1 a b a−1

7

1.Successione di Fibonacci e proprietà principali ⇒

Proprietà 1.2.5 (Divisibilità). Dati gli interi postitivi m, n, si ha che m|n

|F

F m n

Dimostrazione. Dimostrazione costruttiva. Per ipotesi abbiamo che se m|n allora

∃ | |F

s n = sm. Quindi, per sostituzione, la nuova tesi è F . La dimostra-

m sn

zione parte dalla seguente catena di equazioni, vista anche nella dimostrazione

precedente F = 1F + F

sm sm−1 sm−2

= 2F + F

sm−2 sm−3

= 3F + 2F

sm−3 sm−4

..

.

= F F + F F per k < sm

k+1 sm−k k sm−k−1

−

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

..

.

= F F + F F

(s−1)m+1 sm−(s−1)m (s−1)m sm−(s−1)m−1

= F F + F F

α m β

(s−1)m

per qualche intero α e β. A questo punto ripetiamo la stessa catena di equazioni

−

per F , fermandoci a k = (s 2)m:

(s−1)m F = F F + (F F + F F )F

0 0

sm α m α m β β

(s−2)m

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 = δ F

sm m

Proprietà 1.2.6 (Euclide per Fibonacci). Per la successione di Fibonacci vale un

analogo dell’algoritmo di Euclide dato dalla seguente equazione:

M CD(F , F ) = M CD(F , F )

m n n r

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

8

1.Successione di Fibonacci e proprietà principali

Dimostrazione. Abbiamo subito che:

M CD(F , F ) = M CD(F , F )

m n n qn+r

Per la proprietà di Scomposizione 1.2.4 vale

M CD(F , F ) = M CD(F , F F + F F )

m n n r qn+1 qn r−1

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

M CD(F , F ) = M CD(F , F F )

m n n r qn+1 |F

Inoltre, dato che i numeri di Fibonacci successivi sono coprimi ed F abbiamo

n nq

M CD(F , F ) = M CD(F , F )

m n n 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

i loro indici.

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

M CD(F , F ) = F

i j M DC(i,j)

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

M CD(i, j) = M CD(j, r ) = M CD(r , r ) = ... = M CD(r , 0) = r

1 1 2 n n

Allora dalla proprietà precedente abbiamo

M CD(F , F ) = M CD(F , F ) = ... = M CD(F , F ) = F = F

i j j r r 0 r M DC(i,j)

n n

1 9

1.Successione di Fibonacci e proprietà principali

Problemi

Problema 1.2.1 (Somma di 10 consecutivi). Dimostra che la somma di dieci

numeri della successione di Fibonacci consecutivi è uguale al settimo numero dei

dieci scelti moltiplicato per 11: n+10

X F = 11F

j n+7

j=n+1

Problema 1.2.2 (Somma di n consecutivi). Usando la 1.2.2, dimostra che 11F +

7

1 = F , e che la somma di un numero qualsiasi di termini consecutivi è data dalla

12

differenza di due termini della successione, come

n

X −

F = F F

j n+2 m+2

j=m

Problema 1.2.3. Completa la 1.2.4, dimostrando rigorosamente che

F = F F + F F

n k+1 n−k k n−k−1

per k < n.

Problema 1.2.4. La dimostrazione di 1.2.5, è decisamente laboriosa. Trova una

dimostrazione alternativa (prova anche per induzione su s).

Problema 1.2.5 (Formula di Cassini). Dimostra che vale l’identità

2 n−1

−

F F F = (−1)

n+1 n−1

n

detta formula di Cassini. Eventualmente usa la rappresentazione matriciale.

Problema 1.2.6. Dimostra che vale la seguente generalizzazione della formula di

Cassini 2 n−1 2

−

F F F = (−1) F

n+r n−r r

n

dimostrata da Catalan.

Problema 1.2.7 (Numeri primi nella successione di Fibonacci). Congettura e di-

mostra quali posizioni possono occupare i numeri primi nella successione di Fibo-

nacci. Tieni presente che esiste una congettura finora non dimostrata, che afferma

che la successione di Fibonacci contiene infiniti numeri primi.

10

1.Successione di Fibonacci e proprietà principali

1.3 Fibonacci e la sezione aurea

Il rapporto aureo è la suddivisione di un segmento di lunghezza l in due segmenti

di lunghezza a e b tali che a + b = l e tale che sia soddisfatta la proporzione:

a + b a

=

a b

La misura della lunghezza di a in funzione di b viene ricavata dalla sostituzione di

a = xb nelle equazione precedente, per cui otteniamo:

xb + b xb 2

⇒

= x = x + 1

xb b

Non può pertanto fare a meno di sbucare fuori la prossima

Definizione 1.3.1. Si definisce numero aureo il seguente

√ 5

1+ ∼ 1, 618033989...

ϕ = =

2

che coincide con la soluzione dell’equazione di secondo grado:

2

x = x + 1

definita equazione generatrice della sezione aurea.

De Moivre (1667-1754) trovò una formula, nota anche come formula di Binet, che

consente di trovare l’n-esimo numero della successione di Fibonacci come somma di

potenze di numeri irrazionali. Oltre ad essere di per sé sorprendente che il risultato

della somma sia un intero e che gli irrazionali in questione coinvolgano la sezione

aurea, la dimostrazione ci conduce ad una prima importante generalizzazione:

Proprietà 1.3.1 (Formula di deMoivre). L’n-esimo termine della successione di

Fibonacci è dato da: n n

n n

− − −

ϕ (−1/ϕ) ϕ (1 ϕ)

√ √

F = =

n 5 5

dove ϕ è la sezione aurea. 11

1.Successione di Fibonacci e proprietà principali

Dimostrazione. Costruttiva:

n n n n

−(−1/ϕ) −(1−ϕ)

ϕ ϕ −1/ϕ

la seconda uguaglianza = si verifica dal fatto che =

√ √

5 5

−

1 ϕ, che è la seconda soluzione dell’equazione generatrice della sezione aurea

2

x = x + 1.

Mentre possiamo dimostrare la prima equazione sfruttando una particolare gene-

ralizzazione della successione di Fibonacci:

moltiplicando ambo i membri dell’ equazione generatrice della sezione aurea per

n−1

x , otteniamo la seguente equazione

n+1 n n−1

x = x + x

che soddisfa per gli esponenti la ricorsione fibonacciana, e ricordando che le sue

−

soluzioni sono ϕ e 1 ϕ otteniamo le seguenti equazioni:

n+1 n n−1

ϕ = ϕ + ϕ (1.1)

n+1 n n−1

− − −

(1 ϕ) = (1 ϕ) + (1 ϕ) (1.2)

Consideriamo ora le serie geometriche generate dalle precedenti equazioni e

date da ∞

X i → ∞

ϕ

i=1

∞

X i

− →

(1 ϕ) 0

i=1

La prima tende esponenzialmente ad infinito, la seconda tende a zero con lo stesso

ordine.

Ricordando che entrambe le successioni soddisfano la ricorsione fibonacciana, pos-

siamo allora definire un tipo di successione di Fibonacci, come combinazione lineare

dei rappresentanti delle due successioni: n n

F −

(a, b) := aϕ + b(1 ϕ)

n

Che soddisfa anch’essa la ricorsione fibonacciana; infatti

n+1 n+1

F −

(a, b) : = aϕ + b(1 ϕ)

n+1 n n−1 n n−1

− −

= a(ϕ + ϕ ) + b((1 ϕ) + (1 ϕ) )

n n n−1 n−1

− −

= aϕ + b((1 ϕ) + aϕ ) + b(1 ϕ)

F F

= (a, b) + (a, b)

n n−1

12

1.Successione di Fibonacci e proprietà principali

F,

Per avere la successione di Fibonacci da dobbiamo ancora definire le costanti a

√

F F

e b, in modo da ottenere il passo iniziale (a, b) = 0 e (a, b) = 1. Per a = 1/ 5

√ 0 1

−1/

e b = 5 si ha proprio 1 1 1

1

√ √ √ √

− −

F , ) = =0

(

0 5 5 5 5

−

1 1 ϕ 1 ϕ

√ √ √ √

F − −

( , ) = =1

1 5 5 5 5 1

1 −

F , ) sono gli stessi di

Quindi poiché il passo induttivo e i passi iniziali di ( √ √

n 5 5

F le due successioni coincidono, cioè

n 1

1

√ √

−

F , )

F = (

n n 5 5

e dato che n n

− −

1 1 ϕ (1 ϕ)

√ √ √

F −

( , ) =

n 5 5 5

si ha la tesi. F

Dalla precedente dimostrazione, possiamo notare cha che la successione (a, b),

n

1 −b.

ha come caso particolare la successione di Fibonacci per a = = Nell’otti-

√ 5

ca di spazi vettoriali bidimensionali a coordinate in (a, b), F è rappresentata da

n

un punto sulla bisettrice del secondo e quarto quadrante. Per il generico punto

−b, F −a)

della stessa retta, dato da a = si ha come passo iniziale (a, = 0 e

0

F −a) −

(a, = a(2ϕ 1).

1

Le precedenti considerazioni ci conducono alle successioni generalizzate di Fibo-

nacci che saranno relativamente approfondite nel prossimo capitolo.

Possiamo ancora osservare (e sarà utile alla fine del capitolo), che

n n n n

−

− α β

ϕ (−1/ϕ)

√ =

F =

n −

α β

5

dove α e β sono le radici del polinomio generatore della sezione aurea. −

Concludiamo il paragrafo con il seguente risultato trovato da Keplero (1571

1630) che trova un’altra interessante correlazione fra la sezione aurea e la succes-

sione di Fibonacci. 13

1.Successione di Fibonacci e proprietà principali

Proprietà 1.3.2 (Fibonacci e ϕ). Il Rapporto fra l’ (n + 1)-esimo termine e l’

n-esimo della successione di Fibonacci F , all’aumentare di n, tende al rapporto

n

aureo ϕ. F

Dimostrazione. Possiamo usare la successione ricorsiva (a, b) definita nella di-

n

mostrazione della proprietà precedente.

La tesi può essere riformulata nel seguente modo:

F n+1 = ϕ

lim F

n→∞ n

La cui generalizzazione è data da F (a, b)

n+1

lim = ϕ

F (a, b)

n→∞ n

F

Dato che (a, b) è un caso particolare di F , abbiamo la tesi se la dimostriamo

n n

per la sua generalizzazione: n+1 n+1

−

F aϕ + b(1 ϕ)

(a, b)

n+1 = lim

lim n n

F −

(a, b) aϕ + b(1 ϕ)

n→∞

n→∞ n 1−ϕ n

− )

aϕ + b(1 ϕ)( ϕ

= lim 1−ϕ n

a + b( )

n→∞ ϕ

= ϕ

Problemi

Problema 1.3.1. Possiamo riassumere quanto detto nel paragrafo con uno sche-

ma: n n

o / −(−1/ϕ)

ϕ

2 F = √

x = x + 1

d n 5

8

q

qqq

q

q

qq

qq

$ q

x

F n

Completalo spiegando il significato delle frecce, cioè cosa mette in relazione il poli-

nomio caratteristico con la formula di De Moivre e la formula di De Moivre con la

successione di Fibonacci. Cerca di scoprire il significato della freccia tratteggiata.

14

1.Successione di Fibonacci e proprietà principali

Problema 1.3.2. Il problema precedente può essere generalizzato con il seguente

schema: o / F

2 (a, b) = aα + bβ

x = mx + n

g n 6

m

mmm

mmm

m

m

m

mm

' v m

F (a, b)

n

Completa anche questo spiegando il significato delle frecce. Considera α e β come

2 −

le radici del polinomio caratteristico x mx + n.

Problema 1.3.3. La proprietà 1.3.2 può essere dimostrata direttamente, senza

F

ricorrere alla generalizzazione (a, b). Suggerimento:

n+1 F + F

F n n−1

n+1 ···

= lim =

L = lim F F

n→∞

n→∞ n n F

Problema 1.3.4. Implementa una funzione per il calcolo di (a, b) ed esamina

n+1

come varia la successione al variare di a e b. √ 5

1+

Problema 1.3.5. Cosa succede alla formula di De Moivre, se al posto di ϕ = 2

√

1− 5

si pone ϕ = ?

2

1.4 Fibonacci dal triangolo di Tartaglia

Mettiamo da parte la nostra ricerca della generalizzata di Fibonacci per divagare

su una curiosità: i numeri di Fibonacci possono essere ricavati anche dal triangolo

di Tartaglia: infatti la successione delle somma degli elementi che compongono le

diagonali del triangolo, è costituita dai numeri di fibonacci.

15

1.Successione di Fibonacci e proprietà principali 1

1

2 = 1+1

3=1+2

5=1+3+1

8=1+4+3

1 13 = 1 + 5 + 6 + 1

21 = 1 + 6 + 10 +4

1 1

1 2 1 34 = 1+7+15+10+1

1 3 3 1 .

.

1 4 6 4 1*

1 5 10 10* (5) [1] .

1 6 15* (20) [15] (6) [1]

1 7* (12) [35] (35) [12] (7) [1]

1* (8) [28] (56) [70] (56) [28] (8) [1]

Dalla precedente osservazione si ottiene la seguente formula per definire i nu-

meri di Fibonacci:

Proprietà 1.4.1 (Formula di Lucas 1876).

x(n−1)/2y

− −

n i 1

X

F =

n i

i=0