Una successione definitivamente periodica-parte 2

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Una successione definitivamente periodica-parte 2

Messaggio da jordan » 06 mag 2009, 14:21

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 $
The only goal of science is the honor of the human spirit.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 28 giu 2009, 13:23

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 :D
Ultima modifica di piever il 29 giu 2009, 16:08, modificato 1 volta in totale.
"Sei la Barbara della situazione!" (Tap)

stefanos
Messaggi: 229
Iscritto il: 02 giu 2008, 13:23
Località: Roma
Contatta:

Messaggio da stefanos » 28 giu 2009, 17:00

Oops! :roll:
Vabbe`, eravamo in piscina... non posso ricordarmi tutti i problemi xD
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 29 giu 2009, 15:33

Due cose.
piever ha scritto:Prendiamo n enorme tale che per ogni i tra 1 e 2k, $ p_i|n+i $
Precisamente, dov'è che ti servi di questa condizione?
piever ha scritto:... 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} $?
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 29 giu 2009, 16:14

Uhm, diciamo che ti sei risposto da solo :P

$ \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? :P
"Sei la Barbara della situazione!" (Tap)

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 29 giu 2009, 19:51

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?
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 30 giu 2009, 12:53

FeddyStra ha scritto: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 :oops:

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

ciau!
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 30 giu 2009, 13:12

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). []
jordan ha scritto: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.[]
The only goal of science is the honor of the human spirit.

Rispondi