[Algoritmi] Dimostrazione di serie e invariate

[LorenzoBottiglia]

Ciao, ho un problema con questa dimostrazione:

$ sum_(i=1)^(n) i/2^i <2 $

Qualche consiglio? Inoltre ho un problema nel calcolo dell'invariante. Io ho capito la definizione, ma non ci sono dei metodi che ti permettono di trovare l'invariante facilmente e per essere sicuri che sia corretta?

Grazie mille in anticipo.

[apatriarca]

È da un po' di tempo che non vedo la teoria di questo genere di cose e non ricordo cosa sia l'invariante di cui parli. Tuttavia puoi provare nel seguente modo:
\[ \begin{align*}
\sum_{i=1}^n \frac{i}{2^i} = \frac{1}{2} \, \sum_{i=1}^n \frac{i}{2^{i-1}} &= \frac{1}{2} \, \left. \sum_{i=1}^n i\,x^{i-1} \right|_{x=1/2} \\
&= \frac{1}{2} \, \left. \frac{d}{dx} \, \sum_{i=1}^n x^i \right|_{x=1/2} \\
&< \frac{1}{2} \, \left. \frac{d}{dx} \, \sum_{i=0}^{\infty} x^i \right|_{x=1/2} \\
&= \frac{1}{2} \, \left. \frac{d}{dx} \, \frac{1}{1-x} \right|_{x=1/2} \\
&= \frac{1}{2} \, \left. \frac{1}{(1-x)^2} \right|_{x=1/2} \\
&= \frac{1}{2} \, 4 = 2.
\end{align*} \]