Appunti algoritmi e strutture dati, parte 1

FORMULA DI BINET (m-ESIMO NUMERO DI FIBONACCI SENZA RICORSIONE)

Ricorsivamente, l'ennesimo numero di Fibonacci si ricava così:

F_m = { 1 se m = 1, 2 F_m-1 + F_m-2 se m > 3

FORMULA DI BINET: ∀m ∈ N (F_m = ¹/_√5 (Φ^m - φ^m))

DIMOSTRAZIONE

Consideriamo un numero x_r, appartenente alla sequenza di Fibonacci, possiamo rappresentarlo come un segmento formato dalla somma di due segmenti a e b, costituenti F_m-1 e F_m-2: sono legati dalla proporzione a:b: a : a·b → ^a+b/_a → ^a/_a + ^b/_a = ^b/_a a questo punto sostituiamo ^a/_b con Φ: 1 + ¹/_Φ = Φ Φ² = Φ + 1 (Φ² - Φ - 1 = 0) {Φ = ^1±√5/₂ {φ = ^{4 - √5}/₂ } }

INDUZIONE

caso base m = 4, 2

F₄ = 1 ¹/_√5 (Φ¹ - φ¹) = 1 - ¹/_√5 ( ^1+√5/₂ - ^1-√5/₂ ) = ¹/_√5 ( ^1+√5 - -1+√5² ) = ^2√5/_2√5 = 1 OK

F₂ = 1 ¹/_√5 (Φ² - φ²) = 1 - ¹/_√5 ( ( ^1+√5/₂ )² - ( ^1-√5/₂ )² ) = ¹/_√5 ( ^1+2√5+5/₄ - ^1-2√5+5/₄ ) = ¹/_√5 ( ^{1+2√5+5 - 1+2√5-5}/₄ ) = ¹/_√5 ( ^4√5/₄ ) = ^4√5/_4√5 = 1 OK

FORMULA DI BINET

Ricosivamente, l'ennessimo numero di fibonacci si calcola cosi:

∀m∈ℕ (F_m = ¹/_√5 (Φ^m - ϕ^m))

DIMOSTRAZIONE

Consideriamo un numero x_r appartenente alla sequenza di fibonacci, possiamo rappresentarlo come un segmento formato dalla somma di due segmenti a e b, costituenti F_m-1 e F_m-2: aa ab aaab/aa b/a

1+b/a a questo punto sostituiamo b/a con Φ : 1+¹/_Φ = Φ

INDUZIONE

caso base m=4 :2

PASO INDUTTIVO n ≥ 3.

Assumo che la proprietà sia valida fino a n-1.Per definizione F_n = F_n-1 + F_n-2 e per ipotesi induttiva¹/_√5 (Φ^n-1 - Φ_^ ^n-1)+ ¹/_√5 (Φ^n-2 - Φ_^ ^n-2) = ¹/_√5 (Φ^n-1 - Φ_^ ^n-1 + Φ^n-2 - Φ_^ ^n-2) =

= ¹/_√5 [(Φ^n-1 + Φ^n-2) - (Φ_^ ^n-1 + Φ_^ ^n-2)] e adesso è della forma ¹/_√5 (Φⁿ - Φ_^ ⁿ).

Bisogna dimostrare che Φⁿ = Φ^n-1 + Φ^n-2 e Φ_^ ⁿ = Φ_^ ^n-1 + Φ_^ ^n-2Φⁿ = Φ^n-1 + Φ^n-2 = Φ_^ ⁿ (Φ + 1/_{Φ ^}²) =

Abbiamo visto che Φ+1=Φ² quindi Φ_^ (Φ²/_{Φ ^}²) = ΦⁿLo stesso procedimento vale per Φ_^.

Nella dimostrazione per induzione bisogna usare tutte le ipotesi e riuscire ad arrivare nella forma della tesi.

Tradotto in termini informatici: Fib1 (int n) —> intreturn: ¹/_√5 (Φⁿ - Φ_^ ⁿ