41. Zeri in Fibonacci

[simone256]

Dimostrare che, per ogni $ n $, esiste un numero di Fibonacci che termina con $ n $ zeri.

[Troleito br00tal]

Fratello di staffetta!

[Triarii]

Per comodità chiamo con $a_i$ l'$i$-esimo numero di Fibonacci, e con $f_i$ l'$i$-esimo numero di Fibonacci ridotto modulo $n$
Analizziamo i Fibonacci modulo $a$ (in particolare nel problema useremo $a=2^n$ e $a=5^n$). Se risuciamo a dimostrare che le classi di resto modulo $a$ formano un ciclo, la tesi è dimostrata: infatti se $l$ è la lunghezza del ciclo delle classi di resto modulo $2^n$ e $l'$ quella dei resti modulo $5^n$, basterà prendere $a_t$ con $t=mcm(l, l')$ per trovare un numero di fibonacci che termina con $n$ zeri in base 10.
Dimostriamo ora in generale che le classi di resto modulo $n$ formano un ciclo. Intanto si noti che necessariamente prima o poi la sequenza deve tornare ad un situazione già avvenuta. Infatti Scelti 2 numeri consecutivi, il terzo e quelli successivi sono univocamente determinati. Ma le coppie di classi di resto modulo $n$ sono finite, quindi il successivo e tutti i numeri erano già "usciti". Tuttavia questi cicli potrebbero avere un antiperiodo, il che non ci piace, perchè implicherebbe che lo 0 non torna più nelle varie classi di resto. Ma è impossibile che cia sia un antiperiodo: supponiamo infatti che si ripeta solo una parte della sequenza, da $f_i$ in poi. Tutta la sequenza avrebbe un andamento del genere: $f_0,f_1,...,f_{i-1},f_i,f_{i+1},...,f_{j-1},f_j,f_i,f_{i+1}$,... e così via, con tutti i numeri che precedono $f_i$ che non compaiono più nel periodo.
Per la ricorrenza di Fibonacci, deve valere $f_j+f_{i}=f_{i+1}$, ma vale anche $f_{i-1}+f_i=f_{i+1}$, quindi necessariamente $f_{i-1}=f_j$, assurdo (infatti per ipotesi $f_{i-1}$ non poteva ricomparire nel periodo. Quindi non ci possono essere cicli con antiperiodi, e quindi lo 0 deve comparire di nuovo nella sequenza ciclica. Questo completa la dimostrazione

[jordan]

Piu' in generale, fissati degli interi $x_1,x_2,\ldots,x_k$, una funzione $f\colon \mathbb{Z}^k \to \mathbb{Z}$ e gli interi $x_{i+k+1}=f(x_i,x_{i+1},\ldots,x_k)$ allora in $\mathbb{Z}/n\mathbb{Z}$ la successione $(x_i)_{i \in \mathbb{N}}$ è periodica, e tale periodo è minore di $n^k+k$.

In particolare, se $n$ divide $x_i$ per qualche $1\le i\le k$ allora esistono almeno $Cx$ interi positivi minori di $m\le x$ tali che $n$ divide $x_m$, per qualche costante positiva $C=C(n,k)$.

[simone256]

Fratello di staffetta!

Hahahaha esatto

Triarii vai pure

[ma_go]

Piu' in generale, fissati degli interi $x_1,x_2,\ldots,x_k$, una funzione $f\colon \mathbb{Z}^k \to \mathbb{Z}$ e gli interi $x_{i+k+1}=f(x_i,x_{i+1},\ldots,x_k)$ allora in $\mathbb{Z}/n\mathbb{Z}$ la successione $(x_i)_{i \in \mathbb{N}}$ è periodica, e tale periodo è minore di $n^k+k$.

per come è scritto, questo è falso. per avere un enunciato generale, serve che $f$ sia invertibile (su $\mathbb{Z}/n\mathbb{Z}$) nell'ultima variabile, ovvero che tu sia in grado di esprimere $x_n$ in termini di $x_{n+1}, \dots, x_{n+k}$.

[jordan]

ops, you're right!