Curiosità ($n$-esima...) sui numeri di Fibonacci

[Dorian]

Sia $F_n$ l'ennesimo numero della successione di Fibonacci. Dimostrare che:

$MCD(F_(n+1),F_n)=1$ , $AA n in NN$

ossia che numeri di Fibonacci consecutivi sono coprimi.

[Megan00b]

Induzione no?
per F(1)=1, F(2)=2 è vero.
supponi vero per F(n-1), F(n).
ossia: MCD(F(n-1), F(n))=1.
In altre parole se contemporaneamente d|F(n-1) e d|F(n) allora d=1.
Consideri b=MCD(F(n+1), F(n)),
allora in particolare b|F(n) e b|F(n+1)=F(n)+F(n-1)
quindi b|F(n) e b|F(n-1)
e per ipotesi induttiva allora b=1.
Credo worki.

[Dorian]

Ok!
Rilancio, elaborare una dimostrazione che faccia uso dell'identità di Cassini:

$F_(n+1)F_(n-1)-(F_n)^2=(-1)^n$ , $AA n in NN$

[Martino]

Ok!
Rilancio, elaborare una dimostrazione che faccia uso dell'identità di Cassini:

$F_(n+1)F_(n-1)-(F_n)^2=(-1)^n$ , $AA n in NN$

Dato un divisore comune $d>0$ di $F_n$ e $F_{n+1}$ allora dall'identità di cui sopra $d$ divide $(-1)^n$ e quindi $d=1$.

Rilancio: dimostrare che se $(n,m)=1$ allora $(F_n,F_m)=1$.

[miuemia]

per il quesito proposto da martino, si può utilizzare il fatto

$MCD(F_n,F_m)=F_{MCD(n,m)}$

dunque se $MCD(n,m)=1$ allora $MCD(F_n,F_m)=F_1=1$...
rilancio...

dimostrare

$MCD(F_n,F_m)=F_{MCD(n,m)}$

[Martino]

rilancio...

dimostrare

$MCD(F_n,F_m)=F_{MCD(n,m)}$

Allora vediamo.
Ricordo di aver visto questo risultato da qualche parte ma non ricordo dove ne' come fosse dimostrato.

Io ho pensato cosi': consideriamo il numero aureo (o la sezione aurea, non so mai quale sia), l'unico numero reale positivo $a$ tale che $a^2=a+1$. Si vede subito che un tale $a$ non e' razionale. In particolare $QQ[a]$ ha dimensione 2 su $QQ$.
Si vede facilmente (per induzione) che dato $n ge 1$ e definito $F_0=0$ si ha

(1) $a^n = F_n a + F_{n-1}$.

Ne segue che se $n,x in NN$ allora

$F_{nx}a+F_{nx-1} = a^{nx} = (a^n)^x = (F_n a+F_{n-1})^x = sum_{i=0}^x ((x),(i)) F_n ^i a^i F_{n-1}^{x-i} = sum_{i=0}^x ((x),(i)) F_n ^i (F_i a+F_{i-1}) F_{n-1}^{x-i}$.

E allora usando l'indipendenza lineare su $QQ$ di $1$ e $a$ possiamo vedere l'identita' qui sopra come un'identita' di polinomi nella variabile $a$ e quindi uguagliare i coefficienti di $a$ ottenendo:

(2) $F_{nx} = sum_{i=0}^x ((x),(i)) F_n ^i F_i F_{n-1}^{x-i}$,

In particolare da (2) segue che $F_n$ divide $F_{nx}$. Questo dimostra che la funzione $NN to NN$, $n to F_n$ rispetta l'ordine di divisibilita' (cioe' se $n$ divide $m$ allora $F_n$ divide $F_m$).

Prendendo $x=2$ otteniamo per esempio

$F_{2n} = F_n^2+2F_nF_{n-1} = F_n (F_{n+1}+F_{n-1}),$

Detto $b$ l'unico numero reale negativo che verifica $b^2=b+1$ si ottiene

$F_n = (a^n-b^n)/(a-b)$ per ogni $n ge 1$.

Mi fermo qui nell'attesa che mi venga qualche altra buona idea.

[Gaal Dornick]

Bene! Quindi rimane da provare che: $d//F_n,d//F_m=>d//F_(m,n)$

[Martino]

Esatto!
E credo di esserci riuscito.

rilancio...

dimostrare

$MCD(F_n,F_m)=F_{MCD(n,m)}$

Riepilogo: sia $a$ l'unico reale positivo tale che $a^2=a+1$. Allora come ho osservato si ha:

(1) $a^n = F_n a + F_{n-1}$.

E poi ho dimostrato che la successione di Fibonacci rispetta l'ordine di divisibilità, dato che se $n,x in NN$ allora

$F_{nx}a+F_{nx-1} = a^{nx} = (a^n)^x = (F_n a+F_{n-1})^x =$
$= sum_{i=0}^x ((x),(i)) F_n ^i a^i F_{n-1}^{x-i} = sum_{i=0}^x ((x),(i)) F_n ^i (F_i a+F_{i-1}) F_{n-1}^{x-i}$.

da cui uguagliando i coefficienti di $a$:

(2) $F_{nx} = sum_{i=0}^x ((x),(i)) F_n ^i F_i F_{n-1}^{x-i}$,

Da (2) segue immediatamente che $F_n$ divide $F_{nx}$ (avendo preventivamente definito $F_0=0$). Quindi la funzione $n to F_n$ è crescente rispetto alla relazione d'ordine "divisibile per" su $NN$.

Nell'intervento precedente mi ero fermato qui. Ora prendo $n,m in NN$ e chiamo $d=(n,m)$. Da ciò che abbiamo appena visto $F_d$ divide sia $F_n$ che $F_m$. Come sappiamo (identità di Bezout) esistono due naturali $alpha, beta$ tali che

(3) $alpha n-beta m = d$,

a meno di scambiare tra loro $n$ ed $m$ (possiamo supporre quindi che (3) valga piuttosto che la sua 'omologa').
Ne segue che:

(4) $F_d a+F_{d-1} = a^d = a^{alpha n-beta m} = (a^{alpha n})/(a^{beta m}) = (F_{alpha n}a+F_{alpha n-1})/(F_{beta m}a+F_{beta m-1})$

Ora per "portare su" il denominatore mi interessa esprimere l'inverso in $QQ[a]$ di un generico $0 ne ax+y in QQ[a]$ dove $x,y in QQ$.

Lemma. L'inverso di $0 ne ax+y$ in $QQ[a]$ è $a(-x/(y^2-x^2+xy))+((x+y)/(y^2-x^2+xy))$.
Dimostrazione: omessa (basta fare i conti).

Quindi continuando la (4) ottengo:

$F_d a+F_{d-1} = (F_{alpha n}a+F_{alpha n-1})/(F_{beta m}a+F_{beta m-1}) =$
$=(F_{alpha n}a+F_{alpha n-1}) * ((-F_{beta m})/(F_{beta m-1}^2-F_{beta m}^2+F_{beta m} F_{beta m-1}) a+(F_{beta m}+F_{beta m-1})/(F_{beta m-1}^2-F_{beta m}^2+F_{beta m} F_{beta m-1})) =$
$= ((F_{alpha n} a+F_{alpha n-1})(-F_{beta m}a+F_{beta m}+F_{beta m-1}))/(F_{beta m-1}^2-F_{beta m}^2+F_{beta m} F_{beta m-1}).$

Ora detto $k=beta m$, il denominatore è uguale a $F_{k-1}^2-F_k^2+F_kF_{k-1}$, battezziamolo $G_k$. Per mostrare che $G_k=(-1)^k$ (vedi intervento di Dorian sull'identità di Cassini) basta mostrare che $G_1=-1$ e che $G_k = -G_{k-1}$. Che sia $G_1=-1$ è evidente. Ora basta fare un semplice conto:

$G_k = F_{k-1}^2-F_k^2+F_kF_{k-1} = F_{k-1}^2-(F_{k-2}+F_{k-1})^2+F_{k-1}(F_{k-2}+F_{k-1}) =$
$= -F_{k-2}^2-F_{k-1}F_{k-2}+F_{k-1}^2 = -G_{k-1}$.

Ne risulta allora che:

(5) $F_d a+F_{d-1} = (-1)^{beta m} (F_{alpha n} a+F_{alpha n-1})(-F_{beta m}a+F_{beta m}+F_{beta m-1})$.

Uguagliando i coefficienti di $a$ otteniamo allora dopo qualche semplificazione

$F_d = (-1)^{beta m} (F_{alpha n}F_{beta m-1}-F_{beta m}F_{alpha n-1})$

Siccome $F_n$ divide $F_{alpha n}$ e $F_m$ divide $F_{beta m}$ abbiamo ottenuto una relazione della forma

$F_d = gamma F_n + delta F_m$

con $gamma,delta in ZZ$. Questo implica in modo immediato che ogni divisore comune di $F_n$ e $F_m$ divide anche $F_d$.
Siccome $F_d$ divide $F_n$ ed $F_m$ ottengo subito che $F_d = (F_n,F_m)$.

[Dorian]

Complimenti! Ci stavo lavorando pure io da qualche giorno, ma senza risultati soddisfacenti!
Qualche rilancio?

[Martino]

Qualche rilancio?

Ehm no

Senonché spulciando su Wikipedia si trovano diverse proprietà dei numeri di Fibonacci... potrebbero essere uno spunto..