Pagina 1 di 1

successione finita

Inviato: 31 ago 2009, 19:16
da lucs223
salve a tutti stavo provando a risolvere questo quesito ma mi blocco quindi volevo chiedere un aiuto , grazie in anticipo

definiamo la successione An+1= (3An + 1)/2 e poniamo Ao= n con n dispari
se An è pari la succesione si ferma, se è dispari il procedimento continua

dimostrare che la succesione è finita ( prima o poi si ferma) e calcolre di quanti termini è composta

grazie mille

Inviato: 31 ago 2009, 19:36
da spiglerg
Hmm.. Questo problema e' un vecchio Sant'Anna.
Allora, prova a studiare n modulo 4. Visto che e' dispari, puo' essere o 1 o 3. Se e' $ a_0 \equiv 1 \pmod{4} $ allora $ a_1 \equiv 0 \pmod{4} $, dunque e' pari e la successione termina (2 elementi nella serie). Se invece e' $ a_0 \equiv 3 \pmod{4} $, hai che $ a_1 \equiv 1 \pmod{4} $ e da qui ti riconduci al caso di prima (3 elementi nella serie).

Inviato: 31 ago 2009, 19:50
da dario2994
spiglerg... il tuo ragionamento è sbagliato...
Prova a fissare come primo elemento 15:
15,23,35,53,80
Il tuo errore sta nel supporre:
$ 2/2\equiv 1 \pmod 4 $
Io vi consiglio invece di dimostrare che se la successione ha n elementi allora
$ a_0\equiv -1 \pmod {2^{n-1}} $
Non sono troppo sicuro del lemma (non riesco a formalizzare la dimostrazione) ma dovrebbe essere giusto.

Inviato: 31 ago 2009, 19:53
da spiglerg
Hmm.. si', dovevo controllare meglio.
Comunque l'idea e' che a seconda delle potenze di 2 di cui e' composto un numero (mi riferisco alla notazione binaria) prima o poi hai esaurito i residui dispari, ed hai un numero pari.
Non credo di aver espresso bene il concetto. Provero' a formalizzarlo piu' tardi.

Inviato: 31 ago 2009, 20:57
da Maioc92
molto più semplice:
la formula chiusa della successione è $ a_n=(\frac 3 2)^n(a_0+1)-1 $ da cui deduciamo che la successione si ferma quando n raggiunge l'esponente del fattore 2 nella scomposizione in primi di $ a_0+1 $

Inviato: 31 ago 2009, 21:28
da dario2994
Mi spieghi come si rende in formula chiusa questa funzione perfavore :)

Inviato: 31 ago 2009, 21:43
da Maioc92
lo trovi nei video di Gobbino. Comunque ecco il riassunto:
abbiamo una successione del tipo $ a_{n+1}=ka_n+h $. Vogliamo traslarla in modo da avere una successione tale che $ b_{n+1}=kb_n $ e $ b_n=a_n-r $. Quindi ecco passo per passo come facciamo a trovare r:
$ b_{n+1}=a_{n+1}-r=ka_n+h-r=kb_n+kr+h-r $.
Poniamo $ kr+h-r=0 $ e troviamo $ \displaystyle r=\frac{-h}{k-1} $(ovviamente k è diverso da 1 altrimenti avremmo una normale progressione aritmetica).
A questo punto la progressione traslata è una progressione geometrica, quindi in formula chiusa è uguale a $ b_0k^n $. Ma $ b_0=a_0-r $. Quindi la formula finale sarà $ a_n=b_n+r=(a_0-r)k^n+r $. Sostituisci r e hai finito :wink:
EDIT: cosa importante:in generale puoi sempre trovare una formula chiusa per una successione lineare, se la successione non è lineare allora è meglio cambiare metodo perchè trovare una formula chiusa è una cosa praticamente senza speranze

Inviato: 31 ago 2009, 23:51
da dario2994
Perfetto, chiarissimo, intanto ho trovato una dimostrazione del mio lemma:
Non ho la voglia di scriverla perchè sono stanco ma posto solo il lemmino da cui si ricava facilmente il resto... che vi sfido a dimostrare (facile ;)):
$ \displaystyle \frac{3x+1}{2}\equiv -1\pmod{2^n}\Rightarrow x\equiv -1\pmod{2^{n+1}} $

Inviato: 01 set 2009, 09:35
da jordan
A me pare un'affermazione :roll:

Inviato: 01 set 2009, 10:58
da dario2994
jordan ha scritto:A me pare un'affermazione :roll:
Non ho capito xD
Intendi che era banale il lemmino?
Oppure che era falso xD

Inviato: 01 set 2009, 13:43
da Tibor Gallai
dario2994 ha scritto:
jordan ha scritto:A me pare un'affermazione :roll:
Non ho capito xD
Intendi che era banale il lemmino?
Oppure che era falso xD
Intende dire che c'è una sottile differenza tra Lemma e Proposizione, e lui lo sa bene perché è un luminare di Logica Matematica.