Una successione definitivamente periodica-parte 2

[jordan]

Siano fissati due interi positivi $ a_0,a_1 $ e l'intero non negativo $ k $.
Definiamo la successione degli $ \{a_i\}_{i \in \mathbb{N}} $ tali che $ a_{n+2}=\varphi(a_{n+1})+\varphi(a_n)+2k $ per ogni $ n \in \mathbb{N} $.

Mostrare che tale successione da un certo punto in poi diviene periodica.


(Paolo Leonetti e Salvatore Tringali)

Nb. Qui $ \varphi(n)=|\{a \in \mathbb{N}_0:(a,n)=1\}| $
Nb2. Qui il caso $ k=1 $

[piever]

Uhm, mi sono messo a pensare a questo problema ieri e per colpa di un tizio che me lo aveva detto sbagliato (cioè non con 2k ma con k) ho sprecato una quantità immonda di neuroni.

Cmq ecco la mia soluzione:

Sia $ p_1=3 $, $ p_2=5 $, $ p_3=7 $, $ p_4=11 $ e così via l'elenco dei primi dispari.

Prendiamo n enorme tale che per ogni i tra 1 e k, $ p_i|n+i $ (n è molto più grande di $ p_{k} $ e esiste per il teorema cinese del resto)

Ora, poniamo $ b_i=\phi(a_i) $ e la ricorrenza diventa $ b_{n+2}=\phi(b_{n+1}+b_n+2k) $

Ora, se i $ b_i $ sono limitati lo sono anche gli $ a_i $ (in quanto $ a_n=b_{n-1}+b_{n-2}+2k $) quindi basta dimostrare che i $ b_i $ sono limitati (e quindi periodici, eccetera)

Claim: non riescono a superare n. Infatti la prima volta che lo superano abbiamo che $ \phi(b_{n+1}+b_n+2k)>n $, quindi la $ \phi $ di un numero pari (perché i $ b_i $ sono pari, essendo delle $ \phi $) minore o uguale a 2(n+k) è maggiore di n, ma la $ \phi $ di questa cosa è $ \displaystyle\le (n+k)\frac{p_{k}-1}{p_{k}} $ (dimezzo perché è pari, e poi moltiplico per (p-1)/p per il più piccolo primo dispari che lo divide, che sicuramente è minore o uguale di $ \displaystyle p_{k} $). Quindi dovremmo avere $ \displaystyle (n+k)(p_{k}-1)>np_{k} $ che fallisce per n sufficientemente grande.

Quasi dimenticavo: bel problema

[stefanos]

Oops!
Vabbe`, eravamo in piscina... non posso ricordarmi tutti i problemi xD

[FeddyStra]

Due cose.

Prendiamo n enorme tale che per ogni i tra 1 e 2k, $ p_i|n+i $

Precisamente, dov'è che ti servi di questa condizione?

... poi moltiplico per (p-1)/p per il più piccolo primo dispari che lo divide, che sicuramente è minore o uguale di $ \displaystyle p_{2k} $

Per quale motivo il più piccolo primo dispari che divide $ b_{i+1}+b_i+2k $ dovrebbe essere necessariamente minore o uguale a $ p_{2k} $?

[piever]

Uhm, diciamo che ti sei risposto da solo

$ \displaystyle n+1\le \frac{b_{i+1}+b_i+2k}{2}\le n+k $ (importante: $ \displaystyle\frac{b_{i+1}+b_i+2k}{2} $ è intero, perché i $ b_i $ sono tutti pari)

Quindi chiamando $ \displaystyle\frac{b_{i+1}+b_i+2k}{2}=n+j $ abbiamo che $ \displaystyle p_j|n+j=\frac{b_{i+1}+b_i+2k}{2} $ (ecco a cosa serviva l'ipotesi!) e, siccome $ j\le k $, $ p_j\le p_k $

Ho editato il messaggio originale perché lì avevo scritto 2k invece che k. Funziona lo stesso, ma la stima è più larga senza motivo.

Spero ora sia chiaro...

ciau!

P.S. com'è andata la terza prova, classicista? e cicerone?

[FeddyStra]

U-a-u!!!
Chiarissimo.

Versione benone: ho riconosciuto punior deponente, ma sono incerto su modo ne che c'era più avanti.
Terza prova credo anche bene.
Tu?

[piever]

U-a-u!!!
Chiarissimo.

Versione benone: ho riconosciuto punior deponente, ma sono incerto su modo ne che c'era più avanti.
Terza prova credo anche bene.
Tu?

Maledetto, ci ho messo 1 ora a capire che era "punisce" e non "è punito", nel qual caso la versione avrebbe avuto ancora meno senso (sul mio vocabolario nella definizione di punio c'era scritto in piccolo "o anche punior", ma era quasi illeggibile). "modo ne" io ho messo "purché non", ma non è che aveva davvero qualche significato...

Sorvoliamo sulla terza prova, alcune cose le avrei lasciate in bianco

Forse è meglio chiudere l'OT (in caso rispondimi per messaggio privato, cosa che in effetti avrei potuto fare anch'io )

ciau!

[jordan]

Molto bene piever.
Allego sotto la dimostrazione di Hitleuler, sostanzialmente con la stessa idea di fondo, e sotto ancora quella mia (scusate, è scritta in inglese, ci metterei troppo a tradurla adesso..)



Prova 1. (E' un copia-incolla da qui)

Proposizione 1. Per ogni $ x \ge 0 $, vale che $ 1 - x \le e^{-x} $, e l'uguaglianza sussiste sse $ x = 0 $.

Proof. Basta osservare che la funzione $ f(\cdot): \mathbb{R} \to \mathbb{R}: x \mapsto e^{-x} + x - 1 $ è derivabile (con continuità) nel suo insieme di definizione e $ f^\prime(x) = 1 - e^{-x} $, per ogni $ x \in \mathbb{R} $. Perciocché $ f^\prime(x) \ge 0 $, se $ x \ge 0 $, e in particolare $ f^\prime(x) = 0 $ sse $ x=0 $. Ne viene che $ f(\cdot) $ è monotòna (strettamente) crescente in $ [0, +\infty[ $, e dunque $ f(x) > f(0) $, i.e., $ e^{-x} > 1 - x + f(0) $, per ogni $ x > 0 $. Da qui la tesi, una volta riconosciuto che $ f(0) = 0 $. []

Corollario 1. Siano $ n \in \mathbb{N}_0 := \{1, 2, \ldots\} $ e $ a_1, a_2, \ldots, a_n \in [0, 1] $. Allora $ \displaystyle\prod_{i=1}^n (1 - a_i) \le $$ \displaystyle\exp\!\left(\!-\sum_{i=1}^n a_i\right) $.

Proof. Basta osservare che $ 0 \le 1 - a_i \le \exp(-a_i) $, per ogni $ i=1, 2, \ldots, n $ (in base alla proposizione precedente), e quindi moltiplicare membro a membro le $ n $ disuguaglianze così stabilite ed utilizzare le proprietà comuni della funzione esponenziale. []

Corollario 2. Sia $ \{a_i\}_{i \in \mathbb{N}_0} $ una successione a valori in $ [0, 1] $ tale che la serie $ \displaystyle\sum_{i=1}^\infty a_i $ diverge. Allora $ \displaystyle\prod_{i=1}^\infty (1 - a_i) = 0 $.

Proof. Per via del corollario 1, vale che $ \displaystyle 0 \le \lim_{n \to \infty} \prod_{i=1}^n (1 - a_i) \le \lim_{n \to \infty} $$ \displaystyle\exp\!\left(\!-\sum_{i=1}^n a_i\right) $ $ \displaystyle\!\! = \exp\!\left(\!-\lim_{n \to \infty} \sum_{i=1}^n a_i\right) = 0 $, poiché la serie $ \displaystyle \sum_{i=1}^\infty a_i $ diverge a $ +\infty $, in quanto divergente e a termini non negativi (per ipotesi). Da qui la tesi, per confronto (v. squeezing theorem). []

Siano fissati due interi positivi $ a_0,a_1 $ e un intero non negativo $ k $. Definiamo la successione degli $ \{a_i\}_{i \in \mathbb{N}} $ tali che $ a_{n+2}=\varphi(a_{n+1})+\varphi(a_n)+2k $ per ogni $ n \in \mathbb{N} $. Mostrare che tale successione da un certo punto in poi diviene periodica. [...]

1. Ammettiamo che sia $ p_1, p_2, \ldots, p_i, \ldots $ la successione di tutti e soli i numeri primi naturali $ > 5a_1 + 3a_0 + 7k $, arrangiati in ordine crescente, di modo che $ p_1 < p_2 < \ldots < p_i < \ldots $ Poiché la serie $ \displaystyle\sum_{i=1}^\infty \frac{1}{p_i} $ diverge a $ +\infty $ (v. qui), la produttoria $ \displaystyle \prod_{i=1}^\infty \left(1 - \frac{1}{p_i}\right) $ è infinitesima (v. corollario 2). Di conseguenza esistono $ r_0, r_1, \ldots, r_{k+1} \in \mathbb{N}_0 $ tali che $ 1= r_0 < r_1 < \ldots < r_{k+1} $ e $ \displaystyle\prod_{i=r_j}^{r_{j+1} - 1} \left(1 - \frac{1}{p_i}\right) < \frac{1}{2} $, qualunque sia $ j=0, 1, \ldots, k $.

2. Adesso poniamo $ \displaystyle\pi_{ j } = \prod_{i=r_j}^{r_{j+1}-1} p_i $, per ogni $ j=0, 1, \ldots, k $. Ovviamente $ \gcd(\pi_j, \pi_h) = 1 $, se $ j, h \in \overline{0:1:k} $ e $ j \ne h $. Ergo, in base al teorema cinese del resto, esiste senz'altro $ m \in \mathbb{N}_0 $ tale che $ \pi_0 \mid m $, $ \pi_1 \mid (m-1) $, ..., $ \pi_k \mid (m - k) $. Ed è chiaro che, da una parte, $ m \ge p_1 > 5a_1 + 3a_0 + 7k $; e dall'altra $ \frac{1}{2}(m - j) < m - k $, per qualsiasi $ j = 0, 1, \ldots, k $.

3. Per assurdo, supponiamo che $ \{a_n\}_{n \in \mathbb{N}} $ non sia definitivamente periodica. Poiché $ a_n \in \mathbb{N} $, per ogni $ n = 0, 1, 2, \ldots $, quest'è del tutto equivalente a dire che la successione $ a_0, a_1, a_2, \ldots $ non è limitata (v. qui), perciocché deve esistere un qualche $ v \in \mathbb{N} $ tale che $ a_v \ge 2m $ e $ a_n < 2m $, per ogni $ n = 0, 1, \ldots, v-1 $ (v. principio del buon ordine). Eppure $ \max(a_0, a_1, \ldots, a_5) \le 5a_1 + 3a_0 + 7k < m $, e dunque necessariamente $ v \ge 6 $. Ne segue che $ a_{v-1} \equiv a_{v-2} \equiv 0 \bmod 2 $, poiché di fatto tutti i termini della successione $ \{a_n\}_{n \in \mathbb{N}} $ di indice $ \ge 4 $ sono pari.

4. A questo punto, le possibilità sono soltanto due. La prima è che $ a_{v-1} < 2m - 2k $, e allora banalmente $ \varphi(a_{v-1}) \le \frac{1}{2}a_{v-1} < m - k $. La seconda, coerentemente con la minimalità di $ v $, è che $ 2m - 2k \le a_{v-1} < 2m $ (v. punto 3). In tal caso, poiché $ a_{v-1} $ è pari, per forza $ a_{v-1} = 2m - 2j $, per qualche $ j=1, 2, \ldots, k $, e dunque $ \varphi(a_{v-1}) =\displaystyle \frac{1}{2} a_{v-1} \cdot {\prod_{p\;\! \mid \;\! a_{v-1}}}^{\!\!\!\!\prime} \left(1 - \frac{1}{p}\right) = (m-j) \cdot {\prod_{p\;\! \mid \;\! a_{v-1}}}^{\!\!\!\!\prime} \left(1 - \frac{1}{p}\right) $, dove la produttoria primata si intende estesa a tutti e soli i divisori primi naturali dispari di $ a_{v-1} $. Ora, siccome per costruzione $ \pi_j \mid (m - j) $, risulta $ \displaystyle {\prod_{p\;\! \mid \;\! a_{v-1}}}^{\!\!\!\!\prime} \left(1 - \frac{1}{p}\right) \le {\prod_{i=r_j}^{r_{j+1} - 1} \left(1 - \frac{1}{p_i}\right) < \frac{1}{2} $, quindi ancora $ \varphi(a_{v-1}) < \frac{1}{2}(m - j) \le m - k $.

5. D'altronde, le stesse considerazioni si ripetono anche per $ a_{v-2} $, sicché, in ultima istanza, $ 2m \le a_v = \varphi(a_{v-1}) + \varphi(a_{v-2}) + 2k < 2m $, assurdo! Da qui la conclusione che $ \{a_n\}_{n \in \mathbb{N}} $ è limitata, e subito di seguito la tesi. []



Prova 2. (Mi scuso per eventuali errori di grammatica..)

Suppose that $ k=2\zeta $ is a fixed even positive integer, and consider the recursive sequence $ \{a_i\}_{i \in \mathbb{N}} $ defined by $ a_{n+2}=\phi(a_{n+1})+\phi(a_n)+k $, for all $ n \in \mathbb{N} $, where $ a_0, a_1 \in \mathbb{N}_0 $ are given. Then $ \{a_i\}_{i \in \mathbb{N}} $ is eventually periodic.

We divide this proof in two parts:

Part.1: Case $ \zeta=0 $.

Obviously $ 2 \mid \phi(x) $ for all $ x \ge 3 $, so if $ \max\{a_0,a_2\} \le 2 $ we have surely $ a_i=2 $, for all $ i \ge 2 $ and if $ \min\{a_0,a_1\} \le 2 < \max\{a_0,a_1\} $ we will have $ 2 \mid a_i $ for all $ i \ge 4 $, so we can assume without loss of generality $ \min\{a_0,a_1\} \ge 4 $, both even.

And for every $ x \in 2\mathbb{N} $ the inequality $ \phi(x) \le x\left(1-\frac{1}{2}\right) $ holds, so we have trivially $ a_{n+2} \le \frac{a_{n+1}+a_n}{2} \le \max\{a_{n+1},a_n\} $, and equality holds if and only if $ a_{n+1}=a_n $. So we will have a non-increasing sequence $ \{a_i\}_{i \in \mathbb{N}} $, hence it will be eventually costant. It means also that $ \alpha,\beta \in \mathbb{N}_0 $ exist such that $ a_i=2^\alpha $ for all $ i \in \mathbb{N}+\beta $.

Part.2: Case $ \zeta \ge 1 $.

Suppose that $ \{a_i\}_{i \in \mathbb{N}} $ is not periodic, then not eventually bounded (and in particular not costant).

As always the sequence $ \{a_i\}_{i \in \mathbb{N}} $ is eventually even; define $ \Delta_i:=\{x \in \mathbb{N}:2^h+2(i-1)\zeta < x \le 2^h+2i\zeta\} $, for all $ i \in \mathbb{Z} $ where $ h:=\max\{\lfloor \log_2(a_0)\rfloor +20,\lfloor \log_2(a_1)\rfloor +20,6\lfloor \log_2(\zeta)\rfloor +20\} $. Obviously if $ i \ge i_0:= \lfloor \frac{2^{h-1}}{\zeta} \rfloor $ then there exist $ j \in \Delta_i $ such that $ j \ge 2^{h+1} $.

Now we can do the following observation: if $ w $ is a composite integer such that $ 2^h< 2w < 2^{h+1} $ then $ w $ is not a power of $ 2 $ and there exist $ p \le \sqrt{w} $ such that $ p \in \mathbb{P}\setminus\{2\} $ and $ p \mid w $, so the inequality $ \phi(2w) \le w \left(1-\frac{1}{p}\right) \le w-\sqrt{w} < w-2^{\frac{h}{2}} $ holds.

We can say also that if $ a_j $ and $ a_{j+1} $ are given then $ a_{j+2}=\phi(a_{j+1})+\phi(a_j)+2\zeta \le \frac{1}{2}(a_{j+1}+a_j)+2\zeta \le \max\{a_j,a_{j+1}\}+2\zeta $. It means that if $ \max\{a_j,a_{j+1}\} \in \Delta_y $ for some $ y \in \mathbb{Z} $ then $ a_{j+2} \in \Delta_z, z \in \mathbb{Z} $, with $ z-y \le 1 $.

Better, if $ w \in \mathbb{N}_0 $ is a composite number such that $ 2w \in \Delta_x $, with $ x \in \mathbb{N}_0,x \le x_0 := \lfloor \frac{1}{2\zeta}(2^{\frac{h}{2}}+1)\rfloor $ and $ 2^h \le 2q < 2w $ then $ \phi(2w)+\phi(2q)+2\zeta < (w-2^{\frac{h}{2}})+\frac{1}{2}(2w-2)+2\zeta < 2^h $ (note that the last inequality always holds for the assumption on the bound of $ x \in \mathbb{N}_0 $)

Suppose that the sequence $ \{a_i\}_{i \in \mathbb{N}} $ is not periodic, so it is not eventually bounded: it means that $ j \in \mathbb{N} $ exists such that $ a_j \in \Delta_1 $ and $ a_{j+1} \in \Delta_1 \cup \Delta_2 $.

We know that $ a_j=a_{j+1}=a_{j+2}=\ldots=0 $ in $ \mathbb{F}_2 $ and $ a_{j+t} \in \Delta_r $, with $ (r,t) \in \mathbb{Z}\times \mathbb{N} $ such that $ r \le t+1 $. Now if $ a_{j+t} \in \Delta_x, (x,t) \in \mathbb{N}_0 \times \mathbb{N}, x \le x_0< i_0 $ then it must exist $ p_{j+t} \in \mathbb{P}\setminus \{2\} $ such that $ a_{j+t}=2p_{j+t} $, otherwise $ a_{j+t+2}<a_{j+t+1} \in \Delta_{\ell},\ell \in \mathbb{Z},\ell \le 0 $.

If $ a_j=a_{j+1} $ then $ a_{j+2} \neq a_j $ because of the assumption of non-periodic character of the sequence: so we can assume without loss of generality that there exist $ j,n \in \mathbb{N}_0 $ such that $ a_j,a_{j+1},\ldots,a_{j+k} $ is a (strictly) increasing sequence with $ a_j \in \Delta_1 $ and $ a_{j+n} \in \Delta_{x_0} $. And by the previous observation we can say that all such terms must be in the form of two times a odd prime.

Fact. Define $ b_i:=a_{j+i} $ for all $ i=0,1,2,\ldots,n $. There exist $ 2<p_0<p_1<\ldots<p_n $ primes such that $ b_i=2p_i $ for all such $ i $ and, in particular, $ b_{2i+1}-b_{2i} $ is always a (even) integer for $ i=0,1,\ldots,\lfloor \frac{n-1}{2} \rfloor $.

We can easily see by induction that $ b_{2i+1}-b_{2i}=\frac{4}{3}\zeta(1-4^{-i})+(b_1-b_0)4^{-i} $. The right hand side must be a (positive even) integer, so we that the relation$ 4^{i-1} \mid 3\beta-\zeta $ holds, where $ \beta:=\frac{b_1-b_0}{2} \in \mathbb{N}_0 $. Now if $ 3\beta-\zeta=0 $ we can always start the sequence with $ b_1 $ instead of $ b_0 $ and $ 3 \frac{b_1-b_0}{2}-\zeta=0 $ would imply $ 3\frac{b_2-b_1}{2}-\zeta \neq 0 $ since $ b_0,b_1,b_2 $ would be in aritmetic progression, but it impossible since they are primes greater than $ 3 $ and at least one would be divisible by $ 3 $.

But the greatest power of 2 that can divide $ 3\beta-\zeta \neq 0 $ is at max the greatest power of $ 2 $ that is $ \le \max\{\zeta,3\beta\} $ and it is surely less of $ 2 \cdot(2^{h+1}-2^h) $, so it implies that $ 2(i-1) \le h $, so $ i \le \frac{h}{2}+1 $. It mean that $ \lfloor \frac{n-1}{2} \rfloor \le 2( \frac{h}{2}+1)+1+1 $ (the last $ +1 $ recalls the case of $ \beta=0 $), so $ \implies n \le 2(h+5) $.

But we have that $ a_{j+n} \le a_0+2n\zeta \le (2^h+2\zeta)+4(h+5)\zeta= 2^h +2\zeta(2h+11)<2^h+2\zeta(x_0-1) $, contradicting the assumption $ a_{j+n} \in \Delta_{x_0} $.

In conclusion we have that $ a_{j+n+1} \in \Delta_m $ with $ m \in \mathbb{N}_0, m \le x_0 $ so $ a_{j+n+3}<a_{j+n+2}<2^h $. Hence $ \{a_i\}_{i \in \mathbb{N}} $ is bounded by $ 2^{h+1} $ and the sequence itself will be always eventually periodic.[]