Fibonacci con n zeri
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.
Risposte
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...
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...
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
. (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$.
Avresti potuto scrivere direttamente la generalizzazione, essendo giusta e molto carina
. (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$.
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.
Grazie per il chiarimento e complimenti per problema e dimostrazione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo