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.[]
