Su Fibonacci...

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

Sia F(n) l\'n-esimo numero di fibonacci ( F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2) )
 Dimostrare che:
 
 - ogni F(2n+1) si può scomporre in una somma di quadrati;
 - ogni F(2n) non è primo (n>2);
 
 Poi ho notato che F(n) è un numero primo solo se n è primo, ma solo in alcuni casi; purtroppo non riesco a darne una spiegazione. Mi potete aiutare?

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Un aiuto sì... poi però dimostra ciò che ti dico:
 
 Se a|b allora F(a)|F(b).
 Da ciò segue che se n è composto allora lo è anche F(n).
 
 Uno dei primi bei problemi che ho affrontato è questo: sia (a,b) l\'mcd fra a e b
 Allora (F(a),F(b)) = F((a,b)). Se non sbaglio era nel giornalino 3 o 4.

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Catraga, tu dai per scontato il seguente lemma:
 
 \"se F[a]|F[n] -> a|n \".
 
 Sarebbe l\'inverso di quello che ho enunciato. E\' però falso. Non ti do un controesempio perchè non ce ne sono di così immediati.

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Spiacente, ma ho ragione.
 <IMG SRC="images/forum/icons/icon_biggrin.gif">
 Yuri Matijasevich ha pubblicato un bell\'articolo nel Soviet Mathematics, dove applica e dimostra questo ed altri lemmi; anche DEK (D. E. Knuth) mi dà ragione.
 
 Cmq, se proprio ti disgusta tutto ciò, puoi sempre verifiacre che (F[m],F[n]) con m>=n è pari a (F[m-n],F[n]) ovvero a (F[m mod n],F[n])=(F[n],F[r]) ed iterando hai l\'algoritmo euclideo sugli indici dei numeri di fibonacci, quindi:
 (F[m],F[n])=F[(m,n)].

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Questa è un\'altra bella fomula per generare i numeri di fibonacci di indice pari.
 
 Sia
 g[0]=1
 g=Sum[{n,1..i},n.g[i-n]] con i in N
 allora per n>0 si ha
 g[n]=F[2n]

info · Messaggio da **info** » 01 gen 1970, 01:33

Nessuno risponde al primo?
 Allora, (giornalino x docet)
 f(a+1)=f(a)+f(a-1)
 f(a+2)=2f(a)+f(a-1)
 f(a+3)=3f(a)+2f(a-1)
 f(a+4)=5f(a)+3f(a-1)
 .....
 cioè
 f(a+b)=f(b+1)*f(a)+f(b)*f(a-1)
 ponendo a=n+1 e b=n
 f(2n+1)=f(n+1)*f(n+1)+f(n)*f(n)
 f(2n+1)=[f(n+1)]^2+[f(n)]^2
 Qualcuno trova un altro metodo?
 Inoltre, ecco un altro problema (banalissimo come dimostrazione ma interessante).
 Dimostrare che la somma dei primi n numeri di fibonacci +1 è uguale al numero di fibonacci di ordine n+2
 Ciao

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Ah, il lemma sbagliato era il mio. Me ne scuso. In ogni caso i due lemmi non potevano coesistere perchè avrebbero portato un \"se e solo se\" ovunque.
 
 ***
 
 Tutti gli enunciati elementari su Fibonacci si possono dimostrare per induzione, ed in effetti la serie che va sui coglioni cioè no sui conigli è indicatissima per impratichirsi.
 Ci sono valanghe di relazioni notevoli sugli indici.

XT · Messaggio da XT » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-09-29 22:13, lordgauss wrote:
 Ah, il lemma sbagliato era il mio.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Intendi il lemma
 
 a|b-->F(a)|F(b)
 
 ?

info · Messaggio da **info** » 01 gen 1970, 01:33

Qualcuno posta una dimostrazione per induzione del primo problema di Simo (quello dei 2 quadrati)?
 Grazie

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Probabilmente non ti è chiaro come fare perchè sembra che \"manchi un pezzo\": quello degli f con indice pari.
 
 Dimostra queste due asserzioni in coppia: ora è proprio un\'induzione standard.
 
 f(2n) = f(n+1)²-f(n-1)²
 f(2n+1)= f(n+1)²+f(n)²

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

Io l\'ho fatto così:
 sia una successione a tale che a[0]=a ; a[1]=a+k ;a[n]=a[n-1]+a[n-2]
 si ha che a[n]=f[n+1]*a+f[n]*k e supponendo che b=a+k
 a[n]=f[n+1]*a-f[n]*a+f[n]*b=f[n-1]*a+f[n]*b
 
 poniamo a[0]=f[n] e a[1]=f[n+1]
 si ha che a[k]=f[n+k]=f[k-1]*f[n]+f[k]*f[n+1]
 
 per la sol. della 1) abbiamo che (sostituendo n+1 a k)
 f[2n+1]=f[n+(n+1)]=f[n]*f[n]+f[n+1]*f[n+1]=f[n]^2+f[n+1]^2
 
 per la sol. della 2) abbiamo che (sostituendo n a k)
 f[2n]=f[n+n]=f[n-1]*f[n]+f[n]*f[n+1]=f[n]*(f[n-1]+f[n+1])
 quindi f[n]|f[2n]
 
 Come aveva peraltro già dimostrato sapientemente Catraga...
 
 P.S.:Andatevi a risolvere il problemino sulla teoria dei numeri (+ che altro è ancora una congettura da dimostrare per TUTTI i casi)
 <IMG SRC="images/forum/icons/icon21.gif">