OliForum Matematico

Sia $ a_1,a_2,... $ una sequenza tale che $ a_1=43, a_2=142 , a_{n+1}=3a_n+a_{n-1} $. Provare che
a) $ a_n $ e $ a_{n+1} $ sono coprimi per ogni $ n\ge 1 $
b) per ogni numero naturale $ m $, esistono infiniti numeri naturali $ n $tali che $ a_n-1 $ e $ a_{n+1}-1 $ sono entrambi divisibili per $ m $

La sequenza degli $(a_n)_{n \in \mathbb{N}_0}$ è tale che
\[ a_n \equiv n \pmod 2 \text{ }\text{ }\text{ }\text{ e }\text{ }\text{ }\text{ } a_n \equiv 1 \pmod 3 \]
per ogni intero positivo $n$. In particolare se esiste un primo $p$ che divide $\text{gcd}(a_i,a_{i+1})$ allora $p \ge 5$, cosicchè deve dividere anche $a_{i-1}$. Significa che definitivamente dividerà anche $\text{gcd}(a_1,a_2)$, che è impossibile.

OK per la prima parte

La prima parte non era molto ok: non è vero che $a_n \equiv n \pmod 2$, ma la sequenza degli $a_n$ è tale che $2\mid a_n$ se e solo se $3\mid n+1$, e in particolare non ci sono due elementi pari consecutivi.. la conclusione segue come sopra.

$ a_3 $ è dispari, come anche $ a_4 $ Non ci dovrebbero essere problemi credo
edit. mea culpa che ho letto di fretta Comunque dovrebbe andare bene. Io lo avevo risolto praticamente come te (avevo fatto partire l'induzione dall'inizio invece che dalla fine, ma penso sia lo stesso)

Sia $(b_n)_{n \in \mathbb{N}_0}$ la sequenza di interi definita da $b_n:=\frac{1}{3}(a_n-1)$. Allora $b_1=14, b_2=47$ e
\[ b_{n+1}=\frac{1}{3}(a_{n+1}-1)=a_n+\frac{1}{3}(a_{n-1}-1)=a_n+b_{n-1}=3b_n+b_{n-1}+1. \]
E' sufficiente che verificare che la sequenza degli $(b_n)_{n \in \mathbb{N}_0}$ è periodica in $\mathbb{Z}/m\mathbb{Z}$ e che $(0,0)$ appartiene a tale periodo. Che sia periodica è banale: le coppie di residui $(b_n,b_{n+1})$ sono in numero finito per cui da un certo punto in poi si ripeteranno (tali coppie sono al massimo $m^2$). Mostrato che è periodica, possiamo andare anche "all'indietro" a calcolare tali residui, tanto sappiano che passano da llì. E difatti $b_{-3}=b_{-2}=0$, $b_{-1}=1$ e $b_0=4$. Questo mostra anche che il numero di interi $n \in [1,x]$ tali che $m \mid \text{gcd}(a_n-1,a_{n+1}-1)$ è almeno
\[ \left\lceil 2x/m^2\right\rceil .\]

Ok, mi pare giusta Vai pure!