Soluzione di una sommeatoria

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
scorpio2002
Messaggi: 2
Iscritto il: 27 giu 2007, 15:15

Soluzione di una sommeatoria

Messaggio da scorpio2002 »

Salve a tutti. Questo è il mio primo post sul forum, sn un informatico in cerca di aiuto. Dovrei risolvere questa sommatoria:

sommatoria per i da 1 a log(n) di i*2^(i-1)

Non riesco priorio a farla, se non ci fosse l'i che moltiplica la potenza del due sarebbe una serie geometrica e il gioco sarebbe facile. Ma così non so dove mettere mani.

Grazie per l'aiuto
Donato
pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 »

$ \displaystyle \sum_{i=0}^{\log n}i2^{i-1} $

Allora, l'estremo di sopra deve essere naturale, quindi n deve essere potenza della base del logaritmo (è 10 per caso?)

Detto ciò, vediamo che

$ \displaystyle f(x)=\sum_{i=0}^{\log n}ix^{i-1}= \sum_{i=0}^{\log n}\frac{d}{dx}x^{i}=\frac{d}{dx}\sum_{i=0}^{\log n}x^i=\frac{d}{dx}\frac{x^{\log n+1}-1}{x-1} $

L'ultimo passaggio è proprio lo scrivere la sommatoria di una serie geometrica.
Quindi espliciti f e trovi f(2).
scorpio2002
Messaggi: 2
Iscritto il: 27 giu 2007, 15:15

Messaggio da scorpio2002 »

Perfetto. Ci sono. n è potenza di 2 che è la base del logaritmo. Uqesta sommatoria mi serviva per analizzare il caso medio della ricerca binaria in un array ordinato.

Grazie ancora,
Donato
Rispondi