Fibonacci con n zeri

Messaggioda TomSawyer » 07/09/2007, 15:25

Uno carino non difficile: Sia $a_n$ la sequenza di Fibonacci, definita da $a_1=a_2=1$ e $a_{n+1}=a_n+a_{n-1}$, per $n>2$. Dimostrare che per ogni $n \in NN$ esiste un numero di Fibonacci che finisce con $n$ zeri.
I watched a snail crawl along the edge of a straight razor. That's my dream. That's my nightmare. Crawling, slithering, along the edge of a straight... razor... and surviving., Walter E. Kurtz
Avatar utente
TomSawyer
Advanced Member
Advanced Member
 
Messaggio: 1947 di 2270
Iscritto il: 16/11/2005, 16:18

Messaggioda Levacci » 18/09/2007, 14:56

Avvertenze preliminari di carattere oftalmico: la dimostrazione che segue è di faticosa lettura. Non certo per i contenuti ma per la forma dell'esposizione: la mia vecchia ignoranza in materia di LaTeX mi ha costretto ad improvvisare. In particolare ho usato il simbolo di uguaglianza ordinario (=,insomma) come simbolo di congruenza. Matematicamente bestiale, ma questa avvertenza dovrebbe bastare per civilizzare la faccenda. :)

Si tratta di dimostrare che per ogni k appartenente ad N esiste un Fibonacci divisibile per $10^k$.
Lo dimostro (automatica correzione del tiro: cerco di dimostrarlo) per k=1 e generalizzo con una breve riga in fondo.
Consideriamo le coppie di fibonacci della forma $(f(i),f(i+1))$, con i che varia tra $0$ e $99$. Riducendo le coppie modulo $10$ si hanno due possibilità: o esiste una coppia congrua a $(0,0)$ e in questo caso è sufficiente sommare i due fibonacci per trovarne un terzo che soddisfa la tesi, oppure esistono due coppie congruenti. Supponiamo quindi $(f(i),f(i+1))$ congruo a $(f(j),f(j+1))$, $(mod 10)$ e $i>j$. Si ottiene quindi $f(i+1)=f(j+1)$ e $f(i)=f(j)$, $mod(10)$. Sottraendo la seconda congruenza alla prima abbiamo $f(i+1)-f(i) = f(j+1)-f(j)$ e quindi $f(i-1)=f(j-1)$. Si itera il procedimento fino a $f(i-j+1)-f(i-j)= f(1)-f(0)$. A questo punto è sufficiente ricordare che $f(0)=f(1)=1$ per affermare che $f(i-j-1)$ è congruo a $0$ $(mod 10)$.

Generalizzazione di una riga (come promesso): per esponenti $k$ maggiori di $1$ è sufficiente prendere in considerazione le prime $10^(2k)-1$ coppie di fibonacci.

Com'è naturale, aspetto conferme o rimproveri da Tom...
Avatar utente
Levacci
New Member
New Member
 
Messaggio: 15 di 74
Iscritto il: 27/05/2007, 09:33

Messaggioda TomSawyer » 18/09/2007, 22:57

Ciao Levacci! Tranquillo per la notazione, tanto la mia 56kpbs non mi permette di usare MathML.

Avresti potuto scrivere direttamente la generalizzazione, essendo giusta e molto carina :D. (piccolo appunto: la coppia $(0,0)$ non può esserci)

Posto anche una soluzione che differisce pochissimo dalla tua. Consideriamo i $10^{2n}+1$ termini $a_1,... (mod 10^n)$ che formano $10^{2n}$ coppie $(a_1,a_2),(a_2,a_3)...$. Siccome $(0,0)$ non può esserci, abbiamo che il periodo della sequenza è al più $10^{2n}-1$. Ora basta osservare che la prima coppia che si ripete è $(1,1)$, dato che $a_1=a_2=1$, quindi abbiamo che, in $a_1,...,a_p,1,1$, $a_p=1-1=0$.
I watched a snail crawl along the edge of a straight razor. That's my dream. That's my nightmare. Crawling, slithering, along the edge of a straight... razor... and surviving., Walter E. Kurtz
Avatar utente
TomSawyer
Advanced Member
Advanced Member
 
Messaggio: 1971 di 2270
Iscritto il: 16/11/2005, 16:18

Messaggioda Levacci » 19/09/2007, 09:59

Dimenticavo che due fibonacci consecutivi sono sempre relativamente primi. Well, escludendo le prime due coppie.

Grazie per il chiarimento e complimenti per problema e dimostrazione.
Avatar utente
Levacci
New Member
New Member
 
Messaggio: 16 di 74
Iscritto il: 27/05/2007, 09:33


Torna a Pensare un po' di più

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite