Dubbio su sommatoria
Ciao a tutti ragazzi, sto studiando la dimostrazione della complessità di un algoritmo e mi sono imbattuto in due sommatorie che mi sta causando qualche problema ( spero possiate comunque aiutarmi).
Allora la prima sommatoria è la seguente:
$c + c\sum_{i=1}^{k-c} \frac{c}{k-i+1} = c ( 1+ H(k) - H(c) )$
dove c e k sono delle costanti con k>c, mentre H è una serie armonica.
Ora su questa credo di aver capito il procedimento ma non ne sono sicuro. In poche parole applicando la proprietà di scomposizione trasformo la sommatoria in:
$c - \sum_{i=1}^{c} \frac{c}{k-i+1} + \sum_{i=c+1}^{k} \frac{c}{k-i+1} $
ed entrambe le sommatorie quindi dovrebbero essere delle serie armoniche. Giusto ??
In seguito è presente un altro passaggio che mi desta qualche dubbio:
$c + \sum_{i=1}^{k-c} \frac{c}{k-i+1} \le \c[1+sum_{l=c+1}^{k} \frac{1}{l}]= c ( 1+ H(k) - H(c) )\le cH(k)$
Ora il mio dubbio riguarda la possibilità di poter riscrivere :
$ \sum_{i=c+1}^{k} \frac{c}{k-i+1}$
come:
$\c[1+sum_{l=c+1}^{k} \frac{1}{l}]$
Spero qualcuno possa aiutarmi. VI ringrazio in anticipo.
Allora la prima sommatoria è la seguente:
$c + c\sum_{i=1}^{k-c} \frac{c}{k-i+1} = c ( 1+ H(k) - H(c) )$
dove c e k sono delle costanti con k>c, mentre H è una serie armonica.
Ora su questa credo di aver capito il procedimento ma non ne sono sicuro. In poche parole applicando la proprietà di scomposizione trasformo la sommatoria in:
$c - \sum_{i=1}^{c} \frac{c}{k-i+1} + \sum_{i=c+1}^{k} \frac{c}{k-i+1} $
ed entrambe le sommatorie quindi dovrebbero essere delle serie armoniche. Giusto ??
In seguito è presente un altro passaggio che mi desta qualche dubbio:
$c + \sum_{i=1}^{k-c} \frac{c}{k-i+1} \le \c[1+sum_{l=c+1}^{k} \frac{1}{l}]= c ( 1+ H(k) - H(c) )\le cH(k)$
Ora il mio dubbio riguarda la possibilità di poter riscrivere :
$ \sum_{i=c+1}^{k} \frac{c}{k-i+1}$
come:
$\c[1+sum_{l=c+1}^{k} \frac{1}{l}]$
Spero qualcuno possa aiutarmi. VI ringrazio in anticipo.
Risposte
Poni \(l=k-i+1\), come si fa per gli integrali. Quando \(i\) varia tra \(c+1\) e \(k\), la nuova variabile \(l\) varia tra \(1\) e \(k-c+2\), quindi
\[
\sum_{i=c+1}^k \frac{c}{k-i+1} = \sum_{l=1}^{k-c+2} \frac{c}{l}, \]
ci stiamo avvicinando.
\[
\sum_{i=c+1}^k \frac{c}{k-i+1} = \sum_{l=1}^{k-c+2} \frac{c}{l}, \]
ci stiamo avvicinando.
Ciao Alpaca,
Benvenuto sul forum!
Ci sono un po' di cose che non mi tornano in ciò che hai scritto, te le elenco un po' così come mi vengono...
Qui mi sa che c'è una $c $ di troppo, in particolare quella a numeratore dell'argomento della somma.
No, $H$ non è una serie armonica, ma un numero armonico, e tipicamente si definisce
$H(m) := sum_{i = 1}^{m} 1/i = 1 + 1/2 + 1/3 +... + 1/m = sum_{i = 1}^{m} 1/(m - i + 1) $
ove nell'ultima eguaglianza si è effettuata una riflessione di indici (puoi verificare che è vera scrivendo esplicitamente i termini). Quindi si ha:
$ H(k) = sum_{i = 1}^{k} 1/i = sum_{i = 1}^{k} 1/(k - i + 1) $
$ H(c) = sum_{i = 1}^{c} 1/i = sum_{i = 1}^{c} 1/(c - i + 1) $
A questo punto, tornando alla prima somma che hai scritto, credo che in realtà sia come segue:
$ c + c sum_{i = 1}^{k - c} 1/(k - i + 1) = c[1 + sum_{i = 1}^{k - c} 1/(k - i + 1)] = c[1 + sum_{i = 1}^{k} 1/(k - i + 1) - sum_{i = 1}^{c} 1/(c - i + 1)] = $
$ = c[1 + H(k) - H(c)] \le c H(k) $
Benvenuto sul forum!
Ci sono un po' di cose che non mi tornano in ciò che hai scritto, te le elenco un po' così come mi vengono...
"Alpaca":
Allora la prima sommatoria è la seguente:
$ c+ c sum_{i = 1}^{k - c} c/(k - i + 1) = c(1+H(k)−H(c)) $
Qui mi sa che c'è una $c $ di troppo, in particolare quella a numeratore dell'argomento della somma.
"Alpaca":
mentre H è una serie armonica.
No, $H$ non è una serie armonica, ma un numero armonico, e tipicamente si definisce
$H(m) := sum_{i = 1}^{m} 1/i = 1 + 1/2 + 1/3 +... + 1/m = sum_{i = 1}^{m} 1/(m - i + 1) $
ove nell'ultima eguaglianza si è effettuata una riflessione di indici (puoi verificare che è vera scrivendo esplicitamente i termini). Quindi si ha:
$ H(k) = sum_{i = 1}^{k} 1/i = sum_{i = 1}^{k} 1/(k - i + 1) $
$ H(c) = sum_{i = 1}^{c} 1/i = sum_{i = 1}^{c} 1/(c - i + 1) $
A questo punto, tornando alla prima somma che hai scritto, credo che in realtà sia come segue:
$ c + c sum_{i = 1}^{k - c} 1/(k - i + 1) = c[1 + sum_{i = 1}^{k - c} 1/(k - i + 1)] = c[1 + sum_{i = 1}^{k} 1/(k - i + 1) - sum_{i = 1}^{c} 1/(c - i + 1)] = $
$ = c[1 + H(k) - H(c)] \le c H(k) $
Ok, si effettivamente avevo messo una c di troppo. Ok ti ringrazio per l'aiuto. Volevo solo porti un ultima domanda su un passaggio che mi desta ancora qualche dubbio:
Allora nell'ultimo passaggio tu mi ha scritto che
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1} ]= c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]=c[1+H(k)-H(c)]$
Ora questa parte mi è chiara, il dubbio è presente nella parte successiva.
Nel primo post , quello in cui ho riportato tutto il procedimento presente sul libro, si ha che
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1}] = c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]\le c[1+\sum_{l=c+1}^{h} \frac{1}{l}]$
A questo putno la diseguaglianza viene riscritta come:
$c(1+H(k)-H(c)\le cH(k)$
Ora il mio dubbio è se :
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1} ]= c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]$
Allora ne deriva che:
$c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]$
Lo posso riscrivere come:
$c[1+\sum_{i=c+1}^{k} \frac{1}{k-i+1}] = c[1+\sum_{i=c+1}^{k}\frac{1}{i}]$
Ma a questo punto posso riscrivere in questo modo?
$c[1+\sum_{i=c+1}^{k}\frac{1}{i}] = cH(k)$
Cioè se H è un numero armonico del tipo:
$1+\frac{1}{2} +frac{1}{3}+ ... + \frac{1}{n}$
nel mio caso avrei:
$1+ \frac{1}{c+1}+..+\frac{1}{k}$
ossia mi mancherebbero al denominatore tutti quei termini compresi tra 1 e c+1, posso comunque rappresentare la cosa come numero armonico?
Ti ringrazio ancora per l'aiuto
Allora nell'ultimo passaggio tu mi ha scritto che
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1} ]= c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]=c[1+H(k)-H(c)]$
Ora questa parte mi è chiara, il dubbio è presente nella parte successiva.
Nel primo post , quello in cui ho riportato tutto il procedimento presente sul libro, si ha che
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1}] = c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]\le c[1+\sum_{l=c+1}^{h} \frac{1}{l}]$
A questo putno la diseguaglianza viene riscritta come:
$c(1+H(k)-H(c)\le cH(k)$
Ora il mio dubbio è se :
$c+ c\sum_{i=1}^{k-c} \frac {1}{k-i+1} = [1+\sum_{i=1}^{k-c} \frac{1}{k-i+1} ]= c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]$
Allora ne deriva che:
$c[1+ \sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1}]$
Lo posso riscrivere come:
$c[1+\sum_{i=c+1}^{k} \frac{1}{k-i+1}] = c[1+\sum_{i=c+1}^{k}\frac{1}{i}]$
Ma a questo punto posso riscrivere in questo modo?
$c[1+\sum_{i=c+1}^{k}\frac{1}{i}] = cH(k)$
Cioè se H è un numero armonico del tipo:
$1+\frac{1}{2} +frac{1}{3}+ ... + \frac{1}{n}$
nel mio caso avrei:
$1+ \frac{1}{c+1}+..+\frac{1}{k}$
ossia mi mancherebbero al denominatore tutti quei termini compresi tra 1 e c+1, posso comunque rappresentare la cosa come numero armonico?
Ti ringrazio ancora per l'aiuto
"Alpaca":
Ti ringrazio ancora per l'aiuto
Prego!
"Alpaca":
ossia mi mancherebbero al denominatore tutti quei termini compresi tra 1 e c+1, posso comunque rappresentare la cosa come numero armonico?
Posso sbagliarmi, ma direi che è proprio perché ti mancano dei termini che puoi scrivere quel $\le $...
Infatti si ha:
$ sum_{i=1}^{k}\frac{1}{k-i+1} - \sum_{i=1}^{c} \frac{1}{c-i+1} = sum_{i=c + 1}^{k}\frac{1}{k-i+1} = sum_{i=c + 1}^{k} \frac{1}{i} \le \sum_{i=1}^{k} \frac{1}{i} = H(k) $
Ok grazie mille ora tutto chiaro 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo