Sequenza di interi

[jordan]

Dimostrare che esiste ed unica una sequenza di $\epsilon_3, \epsilon_4, \epsilon_5, \ldots$ in $\{1,-1\}$ tali che se $a_1=1,a_2=2,a_4=12$ e $a_{n+1}a_{n-1}=a_n^2+\epsilon_n$ per ogni intero $n\ge 3$ allora $a_n$ è intero per ogni intero $n \ge 1$.

[Tess]

È facile vedere che la sequenza è unica (se esiste) da quando gli $a_n$ sono maggiori di 2.
Non so quanto sia facile vedere che la sequenza a segni alterni avvera cioò che chiede il problema.
È interessante osservare che con questa sequenza, comunque si scelga $a_2$, gli altri $a_i$ sono interi;
e che la successione, fissati i primi 2 valori, sembra una ricorsione lineare. (in particolare vorrei far notare che se $a_2=1$, la conosciamo bene la successione)

Quasi a proposito di questo problema ne propongo uno simile (anche se forse è poco di algebra...)
Trovare tutti gli $n$ tali che esiste una successione $a_1,\dots,a_n$ tale che $$ (a_{k+1}+1)(a_{k-1}+1)=a_k^2+1$$ per ogni $1<k<n$.

[Gottinger95]

Innanzitutto la sequenza degli epsilon è unica, perchè scrivendo in questo modo la ricorrenza
\(a_n = \sqrt{a_{n-1} a_{n+1} + \epsilon_n}\)
si evince che \(a_{n-1}a_{n+1} + \epsilon_n = a^2\) per qualche \(a \in \mathbb{N}\). Se per assurdo anche \(a_{n-1}a_{n+1} - \epsilon_n = b^2\), allora
\(a^2-b^2 = 2\epsilon_n\), che è assurdo modulo 4.
Adesso dimostriamo che le ricorrenze
(A) \(a_{n+1} = 2a_n + a_{n-1}\)
(B) \(a_{n+1}a_{n-1} = a_n^2 + \epsilon_n\)
sono equivalenti. Sia \(P(n)\) la proposizione "le due formulazioni della ricorrenza sono equivalenti fino ad \(a_n\)", e siano \(A(n),B(n)\) le due formulazioni della ricorrenza.
INDUZIONE
Passo Base: \(n=3\).
Con (A) troviamo \(a_3 = 2a_2 + a_1 = 5\); con (B) abbiamo \( a_3 = \sqrt{a_2a_4 \pm 1} = \sqrt{25} = 5 \).
Scartiamo \(-5\) atrimenti avremmo \(a_2 = \sqrt{ a_1a_3 \pm 1}\) con argomento della radice negativo.
Passo Induttivo. \(P(n) \rightarrow P(n+1)\), ossia \(A(1), \ldots, A(n+1), B(n) \rightarrow B(n+1)\).
Si ha
\(a_n a_{n-2} = a_{n-1}^2 + \epsilon_{n-1}\)
\(a_n(a_n - 2a_{n-1}) -\epsilon_{n-1}= a_{n-1}^2 \)
\(a_n^2-\epsilon_{n-1} = a_{n-1}(a_{n-1} +2a_n)\)
\(a_n^2-\epsilon_{n-1} = a_{n-1}a_{n+1}\)
che è \(B(n+1)\). Da questo otteniamo anche \(\epsilon_n = -\epsilon_{n-1}\), da cui, in accordo con il caso base, si ha \(\epsilon_n = (-1)^n\).

Ps.: io ho intuito che fosse lineare solo per evidenza numerica, ma c'è qualcosa di più generale che possa far capire che una ricorrenza è riducibile a una lineare?
L'unica cosa che a occhio mi quadra è che nella (B) ho \( a_n = \sqrt{a_{n-1}a_{n+1}-(-1)^n} = \sqrt{quadratico} \sim lineare \), ma in modo così vago non è per niente applicabile.

[Tess]

ma c'è qualcosa di più generale che possa far capire che una ricorrenza è riducibile a una lineare?

No perché non è lineare. Invece, come ho fatto notare, una volta che fissi i primi 2 valori diventa una successione lineare.
La differenza di fondo è che le successioni lineari danno come successione una cosa del tipo $a_n=\alpha r_1^n+\beta r_2^n$ con $r_1, r_2$ che non dipendono dai valori iniziali della successione, mentre in questa si ottiene che dipendono dalla partenza.

[Gottinger95]

Intendi che la formula chiusa in funzione dei due termini iniziali sarebbe più complessa di una lineare? Cioè, anche \(r_1,r_2\) dipendono dai termini iniziali?
Anzi, forse sarebbe più fruttuoso chiedere qualche rudimento sulle ricorrenze in cui compaiono termini di secondo grado!

[EvaristeG]

Purtroppo una teoria generale (come per quelle lineari, per intenderci) non c'è.

[Gottinger95]

Ok, immagino che non sia trattabile a livello così basso, insomma. Grizie a tutti

[<enigma>]

Visto che può tornare utile a qualcuno, tratto qualche caso riguardante le sequenze quadratiche. Neanche per queste c'è una teoria ben definita, ma dei trucchi che variano di caso in caso. Di seguito alcuni esempi famosi.

• $a_{n+1}=2a_n ^2 -1$, $a_0=2$ (SL03-N7). Con la sostituzione $a_n=\cosh x_n$ si arriva a $x_n =\log(2+ \sqrt 3) \cdot 2^n$ e quindi \[a_n = \frac 1 2 [(2+\sqrt 3)^{2^n}+(2-\sqrt 3)^{2^n}].\]
• OGF degli alberi binari. $a_{n+1}=a_n(1-a_n)$, $a_0=\frac 1 2$. Questa successione converge monotonamente a $0$-altrimenti ci sarebbe un punto fisso in $(0,1)$. Ponendo $b_n=\frac 1 {a_n}$, questa soddisfa \[ b_{n+1}=\frac {b_n}{1-b_n ^{-1}}=b_n+1+\frac 1 {b_n}+\frac 1 {b_n ^2}+ \dots, \quad b_0=2. \]
  Questo implica che $b_n \sim n$: in effetti, usando una forma troncata,
  \[ b_{n+1}=b_n+1+\frac {1}{b_n}+\frac{b_n ^{-2}}{1-b_n ^{-1}} \implies b_{n+1}=n+2+\sum_{i=0} ^n b_i ^{-1}+ \sum_{j=0} ^n \frac {b_j ^{-2}}{1-b_j ^{-1}}: \]
  il fatto che $b_n>n$ implica che la prima somma è $O(\log n)$, mentre la seconda è $O(1)$. Da qui per raffinamenti successivi si arriva a
  \[ b_n=n+\log n+C+O\left ( \frac {\log n}{n}\right ) \]
  che descrive quindi molto bene il comportamento di $a_n$.
• Alberi debolmente binari. Se $a_{n+1}=a_n ^2+2$, $a_0=2$, allora \[\lim _{n \rightarrow \infty} a_n ^{2^{-n}}= \xi =2,483253 \dots.\]
• Processo di Galton-Watson. Se $a_0=0$ e $a_{n+1}=(1-p)+p a_n ^2$, allora \[C(p):= \lim_{n \rightarrow \infty} \frac {1-a_n}{(2p)^n}=\prod_{i=0}^\infty \frac {1+a_i}{2}.\]
• Fermata ottimale. Se $a_0=0$ e $a_{n+1}=\frac 1 2 (1+a_n ^2)$, allora \[ a_n \sim 1-\frac 2 {n+\log n+b}, \quad b=1,767993 \dots\]
• Un esempio banale. Se $a_0=2$, $a_{n+1}=a_n ^2$ allora $a_n =2^{2^n}$.
• Alberi fortemente binari. Se $a_0=1$, $a_{n+1}=a_n ^2+1$, allora $a_n= \left \lfloor \beta ^{2^n} \right \rfloor$ dove $\beta=1,502836 \dots$
• Sequenza di Sylvester. Se $a_1=2$, $a_{n+1}=a_n ^2-a_n+1$, allora $a_n= \left \lfloor \chi ^{2^n}+\frac 1 2 \right \rfloor$ dove $\chi=1,264084 \dots$.
• Ricorsione di Lucas. Se $|a_0|>2$ e $a_{n+1}=a_n ^2 -2$, allora \[ a_n= \left ( \frac 1 2 a_0+\frac 1 2 \sqrt {a_0 ^2-4} \right ) ^{2^n}+ \left ( \frac 1 2 a_0-\frac 1 2 \sqrt {a_0 ^2-4}\right ) ^{2^n} .\]
  Se $|a_0|<2$ è tutta un'altra storia, e riguarda la teoria dei sistemi dinamici.
• La mappa logistica. $0 \leq a_0 \leq 1$, $a_{n+1}=c a_n(1-a_n)$. Di nuovo, c'entrano i sistemi dinamici e la teoria ergodica.
• Forse la più famosa, la definizione dell'insieme di Mandelbrot: se $z_0=0$ e $z_{n+1}=z_n ^2+c$, l'insieme di Mandelbrot è l'insieme dei punti $c \in \mathbb C$ per i quali la successione non diverge. In tal caso si può dimostrare che $|c|<2$.
• La ricorsione di Davison-Shallit. Se $a_0=a_1=1$ e $a_{n+1}=a_{n-1}(a_n+1)$: in tal caso $a_n \sim \left \lfloor \xi ^{\varphi^n} \eta ^{(1-\varphi)^n} \right \rfloor$ per $\xi=1,350506 \dots$ e $\eta=1,429815 \dots$. Un'altra ricorsione di questo tipo è $a_0=0$, $a_1=1$, $a_{n+1}=a_n+a_{n-1} ^2$, che soddisfa $a_{2n} \sim (1,436 \dots )^{\sqrt 2 ^{2n}}$, $a_{2n+1} \sim (1,451 \dots)^{\sqrt 2 ^{2n+1}}$. Ma queste sono già ricorsioni di secondo ordine, quindi mi fermo qui. Come vedete, la zoologia è estremamente varia.

[Gottinger95]

Sapreste consigliarmi un libro che tratta ricorrenze non lineari in modo elementare (non intendo semplice, ma con metodi non analitici)?
In realtà anche un libro sulle ricorrenze lineari non mi farebbe schifo. Insomma, un libro sulle ricorrenze, cacchio.