5 5 5 5 5 5 5

(1)

Lezione del 23 marzo 2007

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) Si ricava anche:

(1-)

²

= 1-2+

²

e tenendo conto di (*) si ottiene:

(1-)

²

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

F

n

= [

ⁿ

– (1-)

ⁿ

]/

⁵

per ogni naturale n.

Ragioniamo di nuovo per induzione (II

^a

forma). Per n=1 si ha:

[ – (1-)]/

5

= (2-1) /

5

= 1 = F

1

Supponiamo la formula vera per ogni k<n e dimostriamola per n; poiché è vera 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 n di divisioni effettuate nell’algoritmo Euclideo è  log



a , e inoltre tale maggiorazione è ottimale, cioè per opportune scelte dei valori di a,b il numero delle divisioni è proprio = log



a (caso peggiore).

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

) .

.

(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-2

=r

n-1

q

n

+r

n

(q

n

0, r

n

=0)

(con r

n-1

=mcd(a,b)).

Per costruzione si ha :

a > b > r

1

> r

2

> …….. > r

n-1

> 0=r

n

dunque i quozienti q

i

sono tutti non nulli (se fosse q

i

=0 si avrebbe r

i-2

=r

i-1

q

i

+r

i

, da cui r

i-2

=r

i

, contraddizione); in particolare ogni quoziente q

i

è 1.

Poniamo per omogeneità r

0

=b (in modo che la prima e la seconda divisione siano rispettivamente a=r

0

q

1

+r

1

, 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):

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 e per j=n-1, si ha:

b = r

0

 F

n+1

r

1

 F

n

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

n+2

>

ⁿ

, da cui log



(a)>n, dunque n  log



a .

Tale maggiorazione è ottimale nel senso che per opportuni valori di a,b il numero n delle divisioni è proprio = log



a (caso peggiore).

Precisamente poniamo a=F

n+2

, b=F

n+1

e , ricordando le eguaglianze che legano i numeri di Fibonacci, osserviamo che le divisioni dell’algoritmo Euclideo in questo caso sono le seguenti:

F

n+2

= F

n+1

1+F

n

(q

1

=1 , r

1

=F

n

) F

n+1

= F

n

1+F

n -1

(q

2

=1 , r

2

=F

n-1

) .

.

F

4

= F

3

1+F

2

(q

n-1

=1 , r

n-1

=F

1

=1=mcd(F

n+2

,F

n+1

)) F

3

= 2 = F

2

2+0 (q

n

=2, r

n

=0)

quindi le divisioni sono in numero di n (abbiamo incidentalmente anche dimostrato che 2 numeri di Fibonacci consecutivi sono coprimi).