L'n-esimo primo di N è non maggiore di 2^{2^{n -1}} + 1

[HiTLeuLeR]

Quello che vi propongo è davvero un superclassico! Ebbene sì, siamo alla frutta. In assenza di Simo, l'unico a tenere vivo il subforum di TdN, postando risposte sensate ai problemi proposti, è il nostro Igor (già, questa aspirerebbe ad essere un'invettiva bella e buona, se soltanto non fosse per il fatto che mi scopro tremendamente stanco! Ditevi fortunati... ). Certo anche HumanTorch merita una menzione d'onore, altro non fosse (e non è poco!!!) per il grande impegno, l'interesse e lo studio con cui si applica! Mi sono perciò detto che, al fine di coinvolgere anche gente al di fuori della cerchia (...), forse è il caso di evitare i self-posed, di abbassare un attimino il livello dei problemi e andare così più sulla letteratura. Spero almeno che il Satanasso apprezzi lo sforzo e la smetta di rimbrottarmi ad ogni rinnovata occasione, grrr...

Problema: sia $ \{p_n: n \in\mathbb{N}_0\} $ la sequenza ordinatamente crescente di tutti e soli i numeri primi di $ \mathbb{N} $ ($ p_1 = 2, p_2 = 3, p_3 = 5, \ldots) $. Senza usare risultati troppo raffinati, dimostrare che, per ogni intero $ n > 0 $: $ p_n \leq 2^{2^{n-1}} + 1 $, e stabilire quando vale l'uguaglianza.

[enomis_costa88]

Visto che stanotte non ho proprio sonno ho provato a buttare giù qualcosina..

Step 1: Per un fatto noto (non troppo raffinato spero) tra n e 2n (estremi esclusi) per n>1 c’è un numero primo. Posso dedurne che tra $ 2^n $ e $ 2^{n+1} $ c’è un primo.

Lemma:
So che 2 è primo; tra 2 e $ 2^2 $ c’è almeno un primo oltre a due (due in totale). Dimostro (induttivamente) ora che è sempre così.
Hp: tra 1 e $ 2^{n+1} $ ho almeno n+1 primi. So che tra $ 2^{n+2} $ avrò almeno un altro primo quindi ho minimo n+2 primi e ciò dimostra il lemma.

Step 2: $ p_n \leq 2^n $ perché se $ p_n > 2^n $ ci sarebbe almeno un primo (della successione p_i con $ i \leq n $ ) che non appartiene a nessuno degli n cassetti [1;2][2;4][..] $ [2^{n-1};2^{n}] $ e quindi n-1 camice da mettere in n cassetti e un cassetto vuoto ma ciò è assurdo perché contraddice un risultato precedente.

Step 3: $ 2^n \leq 2^{2^{n-1}}+1 $
Tolgo l’uno che mi sta molto antipatico..e lavoro sugli esponenti:
la th è riscritta come:
$ 2^n \leq 2^{2^{n-1}} $ ovvero per la crescenza della funzione $ 2^n $: $ n \leq 2^{n-1} $
Passo 1) $ 1\leq 1 $
Passo 2) HP: $ n \leq 2^{n-1} $ ; TH: $ n+1 \leq 2^n $ .
Moltiplico per 2 l’ipotesi e (sapendo che $ n \ge 1 $ ) ottengo la catena $ 2^n \ge 2n \ge n+1 $ da cui la tesi induttiva.

Ora so che: $ p_n \leq 2^n \leq 2^{2^{n-1}} < 2^{2^{n-1}}+1 $ ovvero la tesi (si noti che avendo dimostrato la seconda disuguaglianza senza quell'uno antipatico l'uguaglianza non dovrebbe essere verificata).

Sogni d'oro a coloro che riescono a dormire..

[HiTLeuLeR]

[...] Per un fatto noto (non troppo raffinato spero) tra n e 2n (estremi esclusi) per n>1 c’è un numero primo.

Ok, la tua dimostrazione è corretta, soltanto che usa un risultato davvero troppo raffinato, o almeno così si è convenuto di ritenere altrove (click). Del resto, ammettendo di poter utilizzare il teorema di Chebyshev (i.e., il risultato di cui si discute), la tesi risulta notevolmente raffinata ($ p_n \leq 2^n $, per ogni $ n\in\mathbb{N}_0 $). Questo per dire che il tuo proof non va bene, viste le precise richieste formulate nella consegna del problema:

[...] Senza usare risultati troppo raffinati, dimostrare che [...]

[ma_go]

Questo per dire che il tuo proof non va bene, viste le precise richieste formulate nella consegna del problema:

[...] Senza usare risultati troppo raffinati, dimostrare che [...]

ehm.. volendo fare i pignoli, queste non mi sembrano "precise richieste"...
direi che la prossima volta potresti pure dire "senza fare ricorso al teorema di chebycheff (o chebyshev, come preferisci).

[HiTLeuLeR]

Inserisco il problema nel subforum di TdN, che fa capo alla sezione del problem solving olimpico. Altrove, un mod (fph) dichiara che il teorema di Chebychev non è Matematica olimpica, indi è risultato raffinato. Ne deduco che nel risolvere il problema proposto non posso ricorrere al teorema di Chebychev. Punto! Deh, che vuoi farci, ma_go? Abbiamo appena dimostrato che non è da tutti essere pignoli...

[Igor]

Lemma #1.

$ (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1)=(2^{2^n}+1)+2 $

Si verifica per induzione.

Lemma #2

$ p_{n+1}\leq p_1p_2\ldots p_n+1 $

Consideriamo infatti il termine $ p_1p_2\ldots p_n+1 $.Esso non è divisibile per nessuno dei $ p_i $, quindi o è primo, o esiste almeno un altro primo maggiore di $ p_n $.In ogni caso il lemma resta verificato.

Torniamo ora al problema di partenza e lavoriamo per induzione.

Per $ n=1 $ la tesi è verificata, in quanto si ha $ 2\leq 3 $.

Supponiamola ora vera per i primi $ n $ interi positivi.Dimostriamo allora che essa è valida anche per $ n+1 $.Abbiamo infatti

$ p_{n+1}\leq p_1p_2\ldots p_n+1 $ $ \leq (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1) $ $ =2^{2^n}+2 $

Dato che $ 2^{2^n}+2 $ non è mai un numero primo, ne ricaviamo la tesi.

Riguardo l'uguaglianza, poichè non è verificata nè per $ n=1 $ nè per $ n=2 $, non sarà verificata per nessun $ n\in\mathmm{N} $.

[HiTLeuLeR]

Lemma #1: $ (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1)=(2^{2^n}+1)+2 $

Si verifica per induzione.

...ma tu, evidentemente, non l'hai verificato! Avresti scoperto infatti che il claim qui sopra è *falso*. Casomai è vero che, per ogni $ n\in\mathbb{N} $: $ \displaystyle 2 + \prod_{i=0}^n (2^{2^i} + 1) = 2^{2^{n+1}} + 1 $.

Lemma #2: $ p_{n+1}\leq p_1p_2\ldots p_n+1 $ [...]

Sì, l'idea centrale è proprio questa! Adesso però devi rivedere gli argomenti conclusivi, se vuoi che la tua dimostrazione sia giudicata corretta. Mettiti al lavoro appena puoi, io aspetterò...

[HiTLeuLeR]

Ok, me ne occupo io, perché inizio a pensare che Igor non abbia più alcun interesse a rimettersi su un problema che, sostanzialmente, ha già risolto, seppure con qualche sbavatura di troppo.

Claim: per ogni intero $ n > 0 $: $ p_n \leq 2^{2^{n-1}} $.

Dim.: la tesi è banale per $ n = 1 $, ché $ p_1 = 2 \leq 2^{2^0} $. Fissato $ n\in\mathbb{N}_0 $, ammettiamone quindi la consistenza per ogni $ k = 1, 2, \ldots, n $. E allora $ \displaystyle p_{n+1} \leq 1 + \prod_{k=1}^n p_k $, poiché $ \displaystyle 1 + \prod_{k=1}^n p_k $ è un intero $ > 1 $ e non è divisibile per alcun primo dell'insieme $ \{p_k\}_{k=1}^n $. Ergo, dalle ipotesi assunte: $ \displaystyle p_{n+1} \leq 1 + \prod_{k=1}^n 2^{2^{k-1}} = 1 + 2^{1 + 2 + \ldots + 2^{n-1}} = $ $ 1 + 2^{2^n - 1} < 2^{2^n - 1} + 2^{2^n - 1} = 2^{2^n} $. Di qui - per induzione estesa - la tesi, q.e.d.

Il claim implica la tesi asserita nella consegna del problema, e dimostra nondimeno che l'uguaglianza colà suggerita, in effetti, non è mai soddisfatta. E adesso me ne sto zitto...