Sequenza che si annulla spesso

[jordan]

Sia $ \{a_n\}_{n \in \mathbb{N}_0} $ la seuqenza così definita: $ a_1=0 $, $ a_n=a_{[\frac{n}{2}]}+(-1)^{n(n+1)/2} $, dove $ [x] $ denota la parte intera. Per ogni intero $ k \ge 0 $, trovare il numero $ n(k) $ di interi $ n $ tali che $ 2^k \le n < 2^{k+1} $ e $ a_n=0 $.

[FeddyStra]

Estratto delle soluzioni dei problemi dell'Olicontest, che avrei anche inviato se non avessi avuto la febbre...

[Davide90]

Mi sembra che sia perfetta. Bella soluzione, complimenti!
Posso chiederti come ti è venuta l'idea di trovare una formula chiusa per $ $ a_ n $ considerando n in base 2

P.S.: Non avevo mai visto il trucchetto di inserire $ $ \cos^2 (\frac {\pi}{2} \cdot k ) $ per indicare lo sdoppiamento a seconda della parità di k.... simpatico

[julio14]

Non ho letto nel dettaglio, ma i numeri venivano praticamente uguali ai miei quindi sono andato direttamente in fondo. Non ho usato l'induzione estesa, ho semplicemente detto che calcolando $ $a_n $ applicando più volte la definizione, ad ogni passaggio tolgo una cifra e se ho una permanenza sommo 1, se ho una variazione sottraggo 1, come si verifica facilmente modulo 4, solo che alla fine tolte tutte le cifre tranne l'ultima sono rimasto con 1, e $ $a_1=-1 $, quindi c'è da contare un -1 che tu non hai messo. Segue che il caso impossibile è per k pari, mentre per k dispari non viene $ $\binom k {\frac k2} $ ma $ $\binom k {\frac {k+1}2} $

EDIT mi sa tanto che sono partito da a_0=0 e non da a_1=0.... argh! evabbè mi sono giocato l'unico ex in cui speravo punteggio pieno

[jordan]

P.S.: Non avevo mai visto il trucchetto di inserire $ $ \cos^2 (\frac {\pi}{2} \cdot k ) $ per indicare lo sdoppiamento a seconda della parità di k.... simpatico

Be perchè $ \displaystyle \frac{1+(-1)^n}{2} \binom{n}{\frac{n}{2}} $?

@feddy stra, controllato, perfect (e anche scritto bene)
@julio14, se $ m \in [2^k, 2^{k+1}) $ allora in base 2 ha $ k+1 $ cifre.. ci metterai un secondo a capire
(guarda il caso anche il tuo ex-aequo del primo round ha fatto lo stesso erroruccio)

[julio14]

Si che ho k+1 cifre l'ho capito, infatti ci sono k coppie di cifre consecutive, il mio problema è che ho letto male e pensavo a_0=0 non a_1=0: così una volta arrivato a 1 nel calcolo, non mi sono fermato, ma ho aggiunto un -1, perché se a_0=0 allora a_1=-1. In pratica il mio risultato vale se devo trovare gli a_n=-1

devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo devo leggere bene il testo

[Davide90]

Ci può stare anche $ $ (k-1) -2 \left[ \frac {k-1}{2} \right] $