Per valutare il numero di divisione nell’algoritmo Euclideo delle divisioni successive, ci serviremo dei numeri di Fibonacci.

(1)

Lezione del 12 marzo 2008

Per valutare il numero di divisione nell’algoritmo Euclideo delle divisioni successive, ci serviremo dei numeri di Fibonacci.

La successione di Fibonacci.

La successione dei numeri di Fibonacci è la successione di numeri naturali F

n

(n>0) definita ponendo: F

1

=F

2

=1, F

n

=F

n-1

+F

n-2

(per ogni n>2).

Quindi F

3

=2; F

4

=3, F

5

=5, F

6

=8 etc…

Tale successione interviene in molti problemi combinatori.

Problema: trovare una formula algebrica per il calcolo del generico numero di Fibonacci F

n

. A tale scopo ricordiamo alcune classiche nozioni geometriche.

Se AB è un segmento di estremi A,B è di lunghezza a (con a reale >0), si chiama parte aurea di AB un segmento AC (dove C è un punto interno ad AB) tale che la lunghezza x di AC sia media proporzionale fra a e la lunghezza (a-x) del segmento CB:

a : x = x : (a-x)

e da ciò si ricava x

²

+ax-a

²

= 0, da cui x = a(-1

⁵

)/2

Essendo x>0, l’unico valore accettabile è x = a(-1+

5

)/2, da cui a/x = 2/(-1+

5

)=(

5

+1)/21,61 (è il cosiddetto rapporto aureo o numero d’oro).

Il concetto di parte aurea di un segmento ha molte applicazioni geometriche: per esempio il lato del decagono regolare ha la stessa lunghezza della parte aurea del raggio della circonferenza circonscritta.

Se  indica il numero d’oro, descriviamo alcune proprietà di tale numero reale:

1) Poiché x è soluzione di x

²

+ax-a

²

= 0, dividendo per x

²

si ottiene che  = a/x soddisfa l’identità:

1 +  - 

²

= 0 da cui:



²

= 1+ () 2) Da () si ricava anche:

(1-)

²

= 1-2+

²

= 2- (**)

Il numero d’oro ha una relazione con la successione dei numeri di Fibonacci F

n

.

Calcolando le potenze di base  ad esponente naturale e confrontandole con alcuni valori di F

n

, osserviamo che:

F

2

=1 < 

¹

1,61 < F

3

=2 < 

²

2,6 < F

4

=3 < 

³

4,2 < F

5

=5 e si può congetturare che si abbia :

F

n+1

< 

ⁿ

< F

n +2

(***) per ogni naturale n.

Possiamo dimostrare che ciò è vero, ragionando per induzione (II

^a

forma). Per n=1 abbiamo già notato che (***) è vero.

Supponiamolo vero per tutti i k<n, e dimostriamolo vero per n; poiché (***) è per ipotesi vero in particolare per k=(n-1), k=(n-2), si ha F

n

< 

^{n -1}

< F

n +1

, F

n-1

< 

^{n -2}

< F

n

, da cui, sommando, si ha:

F

n+1

= F

n

+F

n-1

< 

^{n –1}

+ 

^{n –2}

< F

n+1

+F

n

= F

n+2

Ma dalla (**) segue che:



^{n –1}

+ 

^{n –2}

= 

^{n –2}

(1+) = 

ⁿ

quindi la (***) é vera per n.

Dimostriamo ora la seguente formula algebrica per il calcolo del generico numero di Fibonacci:

(2)

F

n

= [

ⁿ

– (1-)

ⁿ

]/

⁵

per ogni naturale n.

Ragioniamo di nuovo per induzione (II

^a

forma). Per n=1 si ha:

[ – (1-)]/

⁵

= (2-1) /

⁵

= 1 = F

1

Supponiamolo vero per ogni k<n e dimostriamolo per n; poiché è vero in particolare per k=(n-1), k=(n-2), si ha:

F

n-1

= [

^n-1

– (1-)

^n-1

]/

⁵

, F

n-2

= [

^n-2

– (1-)

^n-2

]/

⁵

e sommando si ottiene (tenendo conto di (*) e (**)):

F

n-1

+ F

n-2

= F

n

= [

^n-2

(1+) - (1-)

^n-2

(2-)]/

⁵

= [

ⁿ

– (1-)

ⁿ

]/

⁵

come si voleva.

Dimostreremo ora che, dati 2 numeri naturali a,b con a>b, il numero di divisioni effettuate nell’algoritmo Euclideo per il calcolo del mcd(a,b) è  log



a (parte intera di log



a), e inoltre il caso peggiore è proprio log



a, nel senso che per opportune scelte dei valori di a,b il numero delle divisioni coincide esattamente con log



a .

Siano a,b numeri naturali, con a>b. Effettuiamo le n divisioni successive dell’algoritmo Euclideo:

a=bq

1

+r

1

(q

1

0, 0<r

1

<b) b=r

1

q

2

+r

2

(q

2

0, 0<r

2

<r

1

) r

1

=r

2

q

3

+r

3

(q

3

0, 0<r

3

<r

2

) .

. .

r

n-3

=r

n-2

q

n-1

+r

n-1

(q

n-1

0, 0<r

n-1

<r

n-2

) r

n-1

=mcd(a,b) r

n-2

=r

n-1

q

n

+r

n

(q

n

0, r

n

=0)

Per costruzione si ha:

a > b > r

1

> r

2

> …….. > r

n-1

> 0=r

n

Osserviamo che tutti i quozienti q

i

sono >0: se fosse q

1

=0, si avrebbe a=r

1

<b (contraddizione); se fosse q

2

=0, si avrebbe b=r

2

<r

1

<b (contraddizione) etc….

Poniamo per omogeneità r

0

=b (in modo che la prima divisione sia a=r

0

q

1

+r

1

e la seconda sia r

0

=r

1

q

2

+r

2

) e dimostriamo che si ha:

r

n-j

 F

j+1

per ogni j=1,2,…,n Ragioniamo per induzione (II

^a

forma).

Per j=1 si ha (essendo r

n-1

>0) : r

n-1

 F

2

= 1.

Supponiamolo vero per tutti i k<j, e dimostriamolo vero per j.

Essendo vero in particolare per k=j-1, k=j-2, si ha:

r

n-j+1

 F

j

, r

n-j+2

 F

j-1

Ricavando il resto r

n-j

dalla divisione numero n-j+2 si ha (tenendo conto che q

n-j+2

1 perché >0):

r

n-j

= r

n-j+1

q

n-j+2

+r

n-j+2

 r

n-j+1

+r

n-j+2

 F

j

+ F

j-1

= F

j+1

come si voleva.

In particolare, per j=n, si ha b = r

0

 F

n+1

e per j=n-1 si ha r

1

 F

n

, dunque dalla prima divisione (essendo q

1

 1) a=r

0

q

1

+r

1

 r

0

+r

1

F

n+1

+F

n

=F

n+2

.

Ma dalla (***) segue a>

ⁿ

, da cui log



(a)>n, ossia n  log



a .

Dimostreremo che, nel caso peggiore, per opportuni valori di a,b il numero n delle divisioni è

proprio = log



a .

Per valutare il numero di divisione nell’algoritmo Euclideo delle divisioni successive, ci serviremo dei numeri di Fibonacci.

Lezione del 12 marzo 2008