Successione limitata

[FeddyStra]

Sia $ \{a_n\}_{n\in\mathbb N^+} $ la successione a termini interi positivi definita tramite la ricorrenza $ \displaystyle a_{n+2}=\frac{a_n+a_{n+1}}{MCD(a_n,a_{n+1})} $.
Per quali valori valori iniziali di $ a_1 $ e $ a_2 $ la successione è periodica?

PS: non mi ricordo la fonte di questo problema, quindi è possibile che sia già presente sul forum, benchè io non l'abbia trovato. In tal caso chiedo scusa ai mod, i quali possono rimuovere il topic.

[ndp15]

[OT]
Domanda: data una successione in $ N $, se essa è limitata allora è periodica? Scusate se è troppo stupida come domanda
[/OT]
Soluzione (banale) $ a_1=a_2=2 $

[julio14]

Perché OT?
Comunque in questo caso si (non in generale ogni successione, pensa alla successione delle cifre di pi: è limitata fra 0 e 9, eppure non è periodica) perché se è limitata si ha a disposizione un numero finito di coppie consecutive possibili, quindi prima o poi si torna da un punto da cui si era già passati, segue che la successione è periodica.

[ndp15]

Perché OT?
Comunque in questo caso si (non in generale ogni successione, pensa alla successione delle cifre di pi: è limitata fra 0 e 9, eppure non è periodica) perché se è limitata si ha a disposizione un numero finito di coppie consecutive possibili, quindi prima o poi si torna da un punto da cui si era già passati, segue che la successione è periodica.

OT semplicemente perchè questa è la richiesta

Per quali valori valori iniziali di a_1 e a_2 la successione è periodica?

e io non rispondevo direttamente a cio'.
Comunque grazie per la risposta, in effetti non avevo pensato all'esempio che mi hai fatto

[FeddyStra]

In realtà il problema originario chiedeva di determinare quando la successione è limitata, tuttavia, essendo i due fatti equivalenti, ho preferito proporlo così.

[kn]

Supponiamo che $ \displaystyle~\nexists K:MCD(a_K,a_{K+1})=1 $ e supponiamo $ \displaystyle~a_i\neq a_{i+1},~\forall i\ge 1 $.
Poniamo $ \displaystyle~m_{i+2}=\max(a_i,a_{i+1}),~\forall i\ge1 $.
Per ogni i avviene che:
- se $ \displaystyle~m_{i+2}=\max(a_i,a_{i+1})=a_i $, abbiamo $ \displaystyle~a_{i+2}=\frac{a_i+a_{i+1}}{MCD(a_i,a_{i+1})}\le\frac{a_i+a_{i+1}}{2}<a_i $ e quindi $ \displaystyle~m_{i+3}=\max(a_{i+1},a_{i+2})<\max(a_i,a_i)=m_{i+2} $
- se $ \displaystyle~m_{i+2}=\max(a_i,a_{i+1})=a_{i+1} $, otteniamo $ \displaystyle~a_{i+2}=\frac{a_i+a_{i+1}}{MCD(a_i,a_{i+1})}\le\frac{a_i+a_{i+1}}{2}<a_{i+1} $ e analogamente $ \displaystyle~a_{i+3}=\frac{a_{i+1}+a_{i+2}}{MCD(a_{i+1},a_{i+2})}\le\frac{a_{i+1}+a_{i+2}}{2}<a_{i+1} $, quindi $ \displaystyle~m_{i+4}=\max(a_{i+2},a_{i+3})<\max(a_{i+1},a_{i+1})=m_{i+2} $
Inoltre in generale $ \displaystyle~m_{i+3}=\max(a_{i+1},a_{i+2})\le\max(a_{i+1},\max(a_i,a_{i+1})) $$ \displaystyle~\le\max(\max(a_i,a_{i+1}),\max(a_i,a_{i+1}))=m_{i+2} $, quindi $ \displaystyle~\{m_i\} $ è debolmente decrescente. Ma per quanto detto sopra vale $ \displaystyle~m_{2i+2}<m_{2i} $, quindi $ \displaystyle~\{m_2i\} $ è strettamente decrescente: $ \displaystyle~\exists N:m_{2N}=1 $, perciò sarà $ \displaystyle~MCD(a_{2N},a_{2N-1})=1 $, assurdo.
Quindi se $ \displaystyle~a_i\neq a_{i+1},~\forall i\ge 1 $ allora $ \displaystyle~\exists K:MCD(a_K,a_{K+1})=1 $.
Da qui in poi i termini consecutivi sono sempre primi tra loro:
infatti, per induzione, se vale $ \displaystyle~MCD(a_J,a_{J+1})=1 $ per un $ \displaystyle~J\ge K $ allora $ \displaystyle~a_{J+2}=a_J+a_{J+1} $ e $ \displaystyle~MCD(a_{J+1},a_{J+2})=MCD(a_{J+1},a_J+a_{J+1})=MCD(a_J,a_{J+1})=1 $, quindi vale anche per $ \displaystyle~J+1 $.
Ma allora abbiamo che $ \displaystyle~a_{i+2}=a_{i+1}+a_i>a_{i+1},~\forall i\ge K $, quindi la successione non è limitata.
Ora notiamo (forse era meglio scriverlo prima... ) che $ \displaystyle~MCD(a_i,a_{i+1})\mid MCD(a_j,a_{j+1}),~\forall j\le i $, infatti (induzione a scendere) $ \displaystyle~MCD(a_i,a_{i+1})\mid MCD(a_j,a_{j+1})\Rightarrow MCD(a_i,a_{i+1})\mid $$ \displaystyle~MCD(a_j,a_{j-1}+a_j)\Rightarrow MCD(a_i,a_{i+1})\mid MCD(a_j,a_{j-1}) $
L'unico caso che resta da esaminare è quando $ \displaystyle~\exists S:a_S=a_{S+1} $.
Abbiamo che in questo caso vale $ \displaystyle~a_{S+2}=2 $, quindi per non ricadere nel caso di una successione con i termini consecutivi primi tra loro (non limitata) deve essere $ \displaystyle~2\mid a_S $. Considerando la nuova successione $ \displaystyle~\{a_i\}_{i>S} $ questa è limitata solo se esiste un altro $ \displaystyle~S'>S $ tale che $ \displaystyle~a_{S'}=a_{S'+1} $ (o se $ \displaystyle~a_{S+1}=2 $). Torniamo alla successione $ \displaystyle~\{a_i\}_{i\ge 1} $ e ricordiamo che vale $ \displaystyle~MCD(a_{S'},a_{S'+1})\mid MCD(a_{S+1},a_{S+2})=2 $. Quindi o abbiamo $ \displaystyle~a_{S'}=2 $ o $ \displaystyle~MCD(a_{S+1},a_{S+2})=1 $, da cui una successione non limitata.
Riassumendo l'unica possibilità per una successione periodica (definitivamente) è quando $ \displaystyle~\exists T:a_T=a_{T+1}=2 $: in questo caso i termini successivi sono tutti 2 e $ \displaystyle~MCD(a_T,a_{T+1})=2\mid MCD(a_i,a_{i+1}),~\forall i\le T) $.
Di nuovo per induzione a scendere abbiamo che $ \displaystyle~a_i=a_{i+1}=2\Rightarrow \frac{a_{i-1}+2}{MCD(a_{i-1},2)}=\frac{a_{i-1}+2}{2}=2\Rightarrow a_{i-1}=2 $.
Gli unici valori iniziali che generano una successione periodica sono pertanto $ \displaystyle~a_1=a_2=2 $.

@FeddyStra: Se con "periodica" intendevi "periodica fin dall'inizio" l'ultima parte si può evitare

OMG quante induzioni!!!

Quoto