OliForum Matematico

Sia fissata la successione $x_1=2, x_2=3, x_3=6$, $x_{n+3}=x_{n+2}+x_{n+1}+x_n$ per ogni $n\ge 1$. Dimostrare che esiste un intero $m$ tale che $10^{2013} \mid x_m$.

Wow, tribonacci numbers!

c'eri tu oggi a Torino?

P.S: problema carino! (peccato averne sentito la soluzione senza averci provato...)

Drago96 ha scritto: c'eri tu oggi a Torino?

Tu dici?

mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione... qualche anima pia che già la conosce me la manderebbe per pm??

patatone ha scritto:mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione...

Invito Drago (che ancora non ho capito chi è) a ripetere la dimostrazione

patatone ha scritto:mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione... qualche anima pia che già la conosce me la manderebbe per pm??

TI propongo le idee chiave della soluzione:
1) Chiamo $x_{-1}=0, x_0=1$. Allora vale $x_{n+3}=x_{n+2}+x_{n+1}+x_n$ per ogni $n\ge -1$.
2) La successione è fortemente periodica, cioè non ha antiperiodo, modulo qualsiasi numero.
3) Unendo i 2 fatti precedenti si ha che è infinite volte nulla modulo $10^{2013}$ e ciò dimostra la tesi.

Come dimostro il punto 2??

Nota che la relazione di ricorrenza può essere rigirata anche per ricavare $x_n$ sapendo $x_{n+1}, x_{n+2}, x_{n+3}$. Quindi...

scambret ha scritto:Come dimostro il punto 2??

Modulo $n$ le possibili "terne" di $(x_i,x_{i+1},x_{i+2})$ di residui sono in numero finito. Questo significa che i residui diventano periodici definitivamente..

Un bound molto grezzo su quanto puo' valere tale periodo qui

La cosa che non mi spiego è che le terne sono finite, ma nessuno mi dice che modulo $10^{2013}$ la somma dei resti è 0. O è altamente probabile che stia rincretinendo..

Anche io forse non ho ben capito quello che intendete
Se per esempio prendo la ricorrenza \(x_{n+3} = x_{n+2} -x_{n+1}+x_n\), anche questa si può rigirare per ottenere \(x_n\), e perciò la terna \((x_{n+3},x_{n+2},x_{n+1})\) può assumere solo alcuni valori. Di fatto, se pongo \(x_1 = x_2 = x_3 = 1\), mi viene \(x_n=1\) per ogni \(n\), ed effettivamente è fortemente periodica, ma nessuno dei termini è divisibile per alcun numero. L'esempio è banale, ma la domanda in sè è: come dimostro che il periodo passa per tutti i valori modulo \(n\) e non solo per alcuni?

Questo è il punto, infatti: le possibili terne sono in numero finito, quindi i resti diventeranno periodici. Se i resti diventano periodici modulo $m\ge 2$ con periodo $T(m)$ allora la "sequenza periodica di resti" è $a_0,a_1,a_2,\ldots,a_{T(m)-1}$. Noi conosciamo tre elementi consecutivi di questa sequenza (per inciso, $a_i:=a_j$ se e solo se $T(m) \mid i-j$ cosicchè la sequenza degli $a_i$ è definita per ogni $i$ intero). Adesso, ci disegnamo una circonferenza, fissiamo un verso di percorrenza, e disegniamo gli $n$ punti distinti $a_0,a_1,\ldots,a_{T(m)-1}$ in ordine. Dato che, una volta fissati $a_{n+1},a_{n+2},a_{n+3}$ possiamo ricavarci sia $a_{n+4}$ che $a_n$ (modulo $m$), allora è vero che possiamo ricavarci l'intera "sequenza periodica di resti" sia in senso orario che in senso antiorario. Spero adesso sia piu' chiaro

Gottinger95 ha scritto:L'esempio è banale, ma la domanda in sè è: come dimostro che il periodo passa per tutti i valori modulo \(n\) e non solo per alcuni?

gli esempi banali sono fondamentali per capire dove le cose non funzionano!
comunque, nessuno ti dice che la successione becchi tutti i resti! ti dice solo che, se ne becca uno, lo becca infinite volte. infatti poi si è dovuti tornare indietro e trovare $x_{-1}=0$ (o $x_{-2}=0$, non ricordo). se mi dai tre valori a caso per $x_0$, $x_1$ e $x_2$ la cosa si fa molto più oscura (e potrebbe benissimo essere falsa, direi).