Il piu' grande numero dispari che divide k

[salva90]

Sul testo "Number theory" di Naoki Sato mi ha incuriosito il seguente esercizio, che non sono riuscito a risolvere:
Sia $ g(k) $ il piu' grande divisore dispari di $ k $. Dimostrare che
$ \displaystyle \ 0<\sum_{k=1}^n {g(k)/k} -{2/3n}<{2/3} $.
Non essendo proposta la soluzione, chiedo aiuto a voi e ringrazio in anticipo chi dedicherà un pò del suo tempo ad aiutarmi.

[Nonno Bassotto]

Ti dò un hint: g(k)/k si semplifica molto, e può assumere solo alcuni valori... Per quanti k assume un fissato valore?
Comunque per fare questo esercizio è utile (non indispensabile) conoscere le serie geometriche

[salva90]

Ho solo scoperto che diventa sempre 1 fratto la max potenza di due che divide k, quindi 1 per tutti i k dispari. Lavorandoci a giorno nuovo può darsi che ci arrivo, ora sono un pò stanco (ho passato la giornata su un libro di geometria!). Comunque grazie mille, nonno bassotto

[salva90]

Penso di essere riuscito a risolverne una parte:
$ \frac {g(k)}{k}=\frac{1}{2^i} $ dove $ 2^i $ è la massima potenza di 2 che divide $ k $. Tale frazione assume valore $ 1 $ se $ k $ è dispari, quindi per $ \frac{n}{2} $ valori di $ k $ per $ n $ pari, $ \frac{n+1}{2} $ per $ n $ dispari. Allo stesso modo assume valore $ \frac{1}{2} $ per $ \frac{1}{4}* $: $ n $,$ n+1 $,$ n+2 $ o $ n+3 $ valori di $ k $(a seconda della classe di congruenza di $ n $ mod $ 4 $) .E così via. Quindi la somma cercata è maggiore di:$ 1*\frac{1}{2}n+\frac{1}{2}*\frac{1}{4}n... $. Mettendo in evidenza $ 1/2n $ ottengo una progressione geometrica di ragione $ 1/4 $, i cui termini sommati mi danno $ 4/3 $. moltiplicando per $ 1/2n $ ottengo che la somma cercata è maggiore di $ \frac{2n}{3} $, e la prima parte dovrebbe essere dimostrata. Per la seconda buio totale

[Nonno Bassotto]

Ok, ci sei quasi. Però il numero esatto di multipli di $ 2^k $ minori o uguali a n non è $ n/2^k $, ma la sua parte intera. Se fai il conto bene ti vengono entrambe le disuguaglianze. Se vuoi posso postare altri hint

[salva90]

Se mi ridai un aiutino piccolo piccolo te ne sarò eternamente grato!

[Marco]

Un aiutino te lo do io. Il problema ha una "ciclicità" naturale, che sono le potenze di 2. Perché non provi a parte il caso n potenza di 2?

[salva90]

Ho capito il tuo suggerimento ma il mio problema è un'altro: impostata la disuguaglianza, ottengo un valore leggermente diverso da quello cercato e non riesco a capire perchè. Probabilmente sbaglio qualcosa senza rendermene conto: hai presente quando un es non ti viene e poi quando scopri la spluzione ti chiedi:"Ma certo!Perchè non ci ho pensato prima?"

[Marco]

Ok. Quanto vale $ \sum \frac{g(k)}{k} $, nel caso potenza di 2?

[salva90]

Mi risulta la seguente somma: $ 2^{i-1}+2^{i-3}+...+2^{-(i-1)}+2^{-i} $. E' corretto o posso trovarlo in un modo piu' semplice?

[Marco]

Ok. Fin qui è giusto. Riesci a scriverla in forma chiusa (="senza i puntini")?

Se sì, ok, fallo. Se no, clicca qui!

Quando hai fatto, dimostrami questo:

$ $ \frac{g(k)}{k} = \frac{g \left( 2^t + k \right)}{2^t + k} $
se $ 0 < k < 2^t $.

[salva90]

Tale somma è una progressione geometrica che ha per risultato (se non erro):
$ $\frac{1}{2^i}\frac{2^{2(i+1)}-1}{2^2-1} $. Per quanto riguarda la dimostrazione: sia $ k=a2^i $, con $ a $ dispari. Allora $ \displaystyle\frac{g(k)}{k}=\frac{1}{2^i} $. Aggiungendo $ 2^t, t > i $, si ottiene $ k+2^t=2^i(2^{t-i}+a)} $ quindi $ \displaystyle\frac{g(k+2^t)}{k+2^t}=\frac{2^{t-i}+a}{2^i(2^{t-i}+a)}=\frac{1}{2^i} $

[Marco]

Mmmm.... quasi giusto. Credo che hai scalato di uno gli indici [hai un i+1 al posto di un i] e che hai scordato di aggiungere l'ultimo termine, quello che non è in serie geometrica (oppure che lo hai considerato in serie geometrica, ma non lo è).

Insomma, per i=1, la somma dovrebbe fare 1 + 1/2 = 3/2, invece ti risulta 5/2...

Il risultato corretto, scritto in modo maneggevole è:
$ $\sum_{k=1}^{2^i} \frac{g(k)}{k} = \frac{2}{3} 2^i + \frac{1}{3} 2^{-i} $.

Spero sia ovvio come da qui si possa dimostrare la tesi nel caso potenze di 2...

Dimostrazione alternativa per arrivare alla formula senza serie geometriche:

Chiamo
$ $ S_i = \sum_{k=1}^{2^i} \frac{g(k)}{k} $.

Si può scrivere una relazione per ricorrenza per $ S_i $ nel modo seguente:

$ S_{i+1} $ è una somma con il doppio dei termini di $ S_i $. La prima metà dei termini è proprio $ S_i $. La seconda metà è di nuovo $ S_i $, ad eccezione dell'ultimo termine, che invece di essere $ 1/2^i $ è in realtà $ 1/2^{i+1} $.

Allora:
$ $ S_{i+1} = S_i + \left( S_i - \frac{1}{2^i} + \frac{1}{2^{i+1}} \right) = 2 S_i - \frac{1}{2^{i+1}} $.

Il termine iniziale della ricorsione è dato da
$ S_0 = 1 $.

Con queste, la formula si dimostra subito per induzione.

--------------------------

Ora vediamo il caso generico. Il lemmino che ti ho fatto dimostrare ti dice che dopo la massima potenza di 2 $ \leqslant $ di n, la funzione da sommare si ripete. Quindi si potrebbe spezzare la somma... Riesci a vedere come si continua?

[salva90]

Quindi potrei porre $ $\sum_{k=1}^n \frac{g(k)}{k}=\sum_{k=1}^{2^i} \frac{g(k)}{k}+\sum_{k=n-2^i}^n \frac {g(k)}{k}, 2^i\leq n $ e da qui, sfruttando il lemma e la ricorrenza delle potenze di due, impostare la disuguaglianza che mi dà il risultato cercato...dovrei avere capito. Grazie Marco
Comunque, penso che ci sia una soluzione piu' immediata: l'esercizio, essendo proposto nella primissima sezione del libro, non dovrebbe richiedere ragionamenti complicati. Purtroppo, se esiste, non la trovo. Incapacita?

[Marco]

Beh, intanto la dispensa di Sato è roba tosta, non ti credere. Se un esercizio sta a pagina 4 di 45, non significa che sia facile...

Mah, visto con occhio didattico, ti direi che l'esercizio ha tutta l'aria di un problema pensato per far ragionare in base 2.

Se uno si fa i primi termini trova:

$ $ \frac{1}{3}, $

$ $ \frac{1}{6}, \ \frac{3}{6}, $

$ $ \frac{1}{12}, \ \frac{5}{12}, \ \frac{3}{12}, \ \frac{7}{12}, $

$ $ \frac{1}{24}, \ \frac{9}{24}, \ \frac{5}{24}, \ \frac{13}{24}, \ \frac{3}{24}, \ \frac{11}{24}, \ \frac{7}{24}, \ \frac{15}{24}, \dots $

Scritta in questo modo, senza semplificare i fattori comuni, forse la struttura è più chiara. L'idea è dimostrare che:

(i) possiamo suddividere la sequenza in blocchi lunghi 1, 2, 4, 8, 16, ecc... in modo tale che ogni blocco è multiplo di 1/3, 1/6, 1/12, 1/24, ecc...

Una volta scritti i blocchi con i denominatori così descritti, ogni blocco individua una sequenza di numeratori:

(ii) il primo termine della sequenza di ogni blocco è sempre 1.

(iii) ogni sequenza di numeratori si ottiene dalla precedente intercalando un nuovo numero dispari, ottenuto dal precedente aggiungendo 2, 4, 8, 16, ecc...

(iv) l'ultimo termine è sempre il massimo

(v) la sqquenza dei numeratori sono sempre tutti e soli i numeri dispari minori di 2, 4, 8, 16, ecc...

[nota: (i) + (v) ==> tesi]

(i) è abbastanza facile da dimostrare: basta vedere quand'è la prima volta che compare un addendo non multiplo del denominatore precedente.

(ii) (iii) (iv) (v) si fanno per induzione sui blocchi.

E comunque, secondo me, l'idea brillante è scrivere i numeratori in base 2 e leggerli al contrario...