Successioni e coprimalità

[Boll]

[Aaargh!!! Non si dice coprimità!!! Cambiato il titolo. M.]

Tolte le maiuscole dal titolo...
Ed accontentato HiTLeuLeR.
MindFlyer
-------------------------------------

Problema
Data la seguente successione $ {a_n} $ così definita:

$ a_1=1 $
$ a_n=a_{n-1}+2^n $

Provare che:
i)$ (a_m,a_{m+1})=1 $
ii)$ (a_m,a_{m+2})=1 $
iii) Esiste un insieme infinito di elementi della successione tali che comunque presi a due a due siano coprimi

[bh3u4m]

Si passa per via di progressione geometrica alla forma generale: $ \\ a_n = 2^{n+1} -3 \\ $

$ 2^n = 3 \bmod k \\ 2^{n+1} = 6 \bmod k \\ $
Però dovrebbe essere:
$ 2^{n+1} = 3 \bmod k $

Se k > 3 non è possibile che siano verificate entrambe.

[Sisifo]

Problema
Data la seguente successione $ {a_n} $ così definita:

$ a_1=1 $
$ a_n=a_{n-1}+2^n $

Provare che:
i)$ (a_m,a_{m+1})=1 $
ii)$ (a_m,a_{m+2})=1 $
iii) Esiste un insieme infinito di elementi della successione tali che comunque presi a due a due siano coprimi

i)$ \forall m a_m $ è dispari, facilmente per induzione
$ a_{m+1}-a_m=2^{m+1} $, cioè il loro massimo comun divisore divide $ 2^{m+1} $, per cui essendo entrambi dispari, è 1.

To be continued...

PS: A proposito, non ho capito il senso della dimostrazione di bh3. Me la spieghi? Cos'è k?

[HumanTorch]

Innanzitutto si consideri la successione in questione come, se S(n+1) è la sommatoria della prime n potenze intere non negative di 2, S(n+1)-2, ovvero 2^(n+1)-2-1=2*(2^n-1)-1
Quindi, supponendo per assurdo che gcd[2*(2^n-1)-1;2*(2^(n+1)-1)-1]=G>1,
si avrà che 2*(2^n-1)-1=2*(2^(n+1)-1)-1 mod G, ovvero
1=2 mod G, il che è vero se e solo se G=1.

[Sisifo]

ii) analogamente, $ \forall m a_m $ non è divisibile per tre. Infatti se m=1, $ a_m=1 $, e ragionando per induzione si vede che
$ a_{2m+1} \equiv 1 \bmod 3\\ a_{2m} \equiv 2 \bmod 3 $.
Ragionando come prima,
$ a_{m+2} - a_{m}=2^{m+2}+2^{m+1}=3*2^{m+1} $
cioè il MCD deve dividere $ 3*2^{m+1} $ e per quanto visto prima, è 1

[HumanTorch]

Ho l'esame ECDL, quindi suggerisco solo qualche ideuzza malvagiuzza e lascio ad altri una dimostrazione più rigorosa per il terzo punto: sappiamo che $ 2^n-1 $ rappresenta infiniti multipli di un numero p*q, dove p e q sono primi, essendo $ 2 $ e un qualsiasi primo $ >2 $ primi fra loro(una dimostrazione elementare è nota ed è stata ricordata anche da Gauss nelle Disquisitiones).
Quindi lo stesso vale per $ 2^n-3 $, e quindi, essendo i primi infiniti...

[Boll]

Ok, sia bh3u4m che Sisifo hanno centrato il problema. Non ho capito l'ultimo post di Human Torch, domani rileggo.

[HiTLeuLeR]

Data la seguente successione $ {a_n} $ così definita: $ a_1=1 $; $ a_n=a_{n-1}+2^n $, provare che: [...] iii) esiste un insieme infinito di elementi della successione tali che comunque presi a due a due siano coprimi.

Altri hanno già provato che, per ogni $ n\in\mathbb{N}_0 $: $ a_n = 2^{n+1} - 3 $. Ciò premesso, poniamo dunque $ b_1 := a_2 = 5 $ e $ b_{n+1} := 2^{\prod_{k=1}^n\varphi(b_k)} - 3 $, per ogni $ n\in\mathbb{N}_0 $. Evidentemente, $ \{b_n\}_{n\in\mathbb{N}_0} $ è un'estratta della successione $ \{a_n\}_{n\in\mathbb{N}_0} $. Indi $ \gcd(2,b_n) = 1 $, qualunque sia $ n\in\mathbb{N}_0 $. Inoltre, per induzione: $ 2 < b_n < b_{n+1} $, per qualsivoglia $ n\in\mathbb{N}_0 $. Infine, per il teorema di Euler-Fermat, se $ m, n\in\mathbb{N}_0 $, con $ m < n $: $ b_n \equiv 2^{\prod_{k=1}^{n-1}\varphi(b_k)} - 3 \equiv -2 \bmod b_m $, cosicché (applicando l'algoritmo di Euclide per la ricerca del massimo comun divisore): $ \gcd(b_m, b_n) = \gcd(2, b_m) = 1 $. Ne segue la tesi!

[Boll]

$ \gcd(a_m, a_n) = \gcd(2, a_m) = 1 $. Ne segue la tesi!

Ma non stavi parlando di $ \{b_n\} $, scusami ma se fosse altrimenti ho perso un passaggio

[HiTLeuLeR]

Non ti sei perso alcun passaggio, sta' tranquillo, son io distratto che scrivo formule sconnesse...

[HiTLeuLeR]

Tolte le maiuscole dal titolo...
MindFlyer

Tolte le maiuscole, non ci andrebbe comunque aggiunta una "s" da qualche parte?!? Vada pure per i "susurri" di Montale, ma non credo che a Bollazzo sia prudente e sensato accordare certune licenze grammaticali...

[Boll]

Bene, dopo essermi assentato per qualche giorno leggo ora la soluzione di Euler "corretta" e, per quel che può valere, gli do la mia benedizione e l'Honourable Mention "virtuale" alle IMO '71

Tra l'altro, stranamente, il sovracitato Euler è stato anche piuttosto sintetico, a tratti quasi ermetico, sta migliorando!!! ;)

[HiTLeuLeR]

[...] Euler è stato anche piuttosto sintetico, a tratti quasi ermetico, sta migliorando!!!

Se davvero lo fossi come si vorrebbe, probabilmente tu e qualcun altro finireste per tenere stentatamente il passo... E' dunque questo che si vuole?!? In fondo a me costa ben poco...

[Boll]

Nono, così va benissimo. Secondo me, a livello di sintesi, siamo proprio a posto. Magari se evitassi le notazioni "sborone" e leziosità varie... Ma non ti si può chiedere troppo su, in fondo ognuno ha le sue manie :D:P

[mattilgale]

scusate l'ignoranza... l'intero problema mi è abbastanza chiaro, ma non capisco come fate a determinare la regola generale...

$ a_n=2^{n+1}-3 $

grazie i anticcipoper la risposta