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

[Dorian1]

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.

[Dorian1]

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$

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

"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$

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)}$

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

"miuemia":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)$

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Esatto!
E credo di esserci riuscito.

"miuemia":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)$.

[Dorian1]

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

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

"Dorian":Qualche rilancio?

Ehm no

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

[Dorian1]

Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

[Gaal Dornick]

Provo che $AAn in NN, n>=1: n$ è somma di elementi distinti di ${F_n}_(n in NN)$

ove $F_0=1, F_1=2...$ e vale che $F_n
La dimostrazione è per induzione:
n=1 $1=F_0$

supponiamo che la tesi sia verificata per $i se $n$ è di Fibonacci, ok.
se $n$ non è di Fibonacci ($=> n>=4$)
determino il più grande numero di Fibonacci
poichè $lim_(i) F_i=+oo$ definitivamente $F_i>=n$
sia $A={F_i|F_i>=n, i in NN}$
$A$ è un sottoinsieme non vuoto di $NN$, quindi è dotato di minimo.
Sia $nu in NN t.c. F_(nu)=minA$
sia $bar(nu)=nu-1$: sicuramente $F_(nu)>=n>=4>3=F_2$, $F_2
Sicuramente $F_(bar(nu))$ non è in A quindi $F_(bar(nu)) Inoltre è il più grande numero di Fibonacci a farlo (per la stretta crescenza di ${F_i}$)
$0 per l'ipotesi induttiva $n-F_(bar(nu))$ è somma di elementi distinti di ${F_i}$. Proviamo che tra questi non può esservi $F_(bar(nu))$: se per assurdo vi fosse, si avrebbe:
$n<=F_(bar(nu)+1)=F_(bar(nu))+F_(bar(nu)-1) I WIN


In realtà è molto costruttiva come dimostrazione: la feci per provare che valeva la tesi..e scrivere il programma che calcola esplicitamente questa decomposizione. Carina, mi divertii molto.

[G.D.5]

"Dorian":Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

Anche noto come Teorema di Zeckendorf.

[Dorian1]

"WiZaRd":[quote="Dorian"]Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

Anche noto come Teorema di Zeckendorf.[/quote]

Non lo sapevo... Nel mio libro è presentato semplicemente come esercizio...

[Dorian1]

"WiZaRd":
Anche noto come Teorema di Zeckendorf.

Guardando meglio, l'esercizio chiede di dimostrare una proposizione più debole del teorema di Zeckendorf... Infatti a noi va bene anche una decomposizione in numeri di Fibonacci consecutivi!

[Dorian1]

Qualcuno ha dato un'occhiata al link segnalato da Wizard?
Ho una perplessità: si dice che

se $N$ è un sottinsieme non vuoto e finito di $NN$ di numeri non consecutivi ($|i-j|>1, AAi,j in N, i!=j$), allora:

$sum_(i in N) F_i

ma preso $N={1,3,5}$, abbiamo che $F_1+F_3+F_5=1+2+5=8=F_6$, quindi la disuguaglianza vale in senso lato.

Il problema è questo: come è possibile dedurre l'unicità della somma di Zeckendorf se la disuguaglianza non è stretta?

[G.D.5]

Non mi intendo di TdN: conoscevo questo risultato e ne conoscevo il nome, ma non ho mai conosciuto la dimostrazione. Quindi non ti so dire. Prova a dare un'occhiata [http://planetmath.org/?op=getobj&from=objects&id=8810]quiì[/url].

[Dorian1]

Com'è noto:

$lim_(n->+oo) F_(n+1)/(F_n)=phi$;

dove $phi$:=$(1+sqrt(5))/2$.

Ma non tutti sanno che:

$-phi=sin(666°)+cos(6*6*6°)$...

Impressionante, vero?

[miuemia]

non capisco bene gli esponenti

[Dorian1]

"miuemia":non capisco bene gli esponenti

Non sono esponenti, stanno solo ad indicare che l'angolo è espresso in gradi...