Ok dopo avere letto la soluzione figa (quella di Marco) vediamo anche quella brutta e contosa (cavoli la mia prima soluzione con le funzioni generatrici..)
Ricordo la seguente, valida in un opportuno insieme
(“would be valid as an identity in the ring of formal power series”)
$ \sum x^n = \frac{1}{1-x} $
Se non specificato le sommatorie sono intese da 0 a + infinito.
Lemma 1: $ \sum n x^n =\sum (n+1)x^{n+1} = \frac{x}{(1-x)^2} $
$ LHS=\sum x \frac{d}{dx} x^n $
$ = x \frac{d}{dx}\sum x^n $
$ = x\frac{d}{dx} \frac{1}{1-x} = \frac{x}{(1-x)^2} $
Lemma 2: $ \sum (n+1)x^n = \frac{1}{(1-x)^2} $
LHS$ = \frac{\sum (n+1)x^{n+1}}{x} $
$ = \frac{1}{(1-x)^2} $
Lemma 3: $ \sum(n+1)^2 x^n = \frac{x+1}{(1-x)^3} $
$ LHS = \frac{d}{dx}\sum (n+1)x^{n+1} $
$ = \frac{d}{dx}\frac{x}{(1-x)^2} $
$ = \frac{x+1}{(1-x)^3} $
Problema vero e proprio:
$ \displaystyle f(n) = \sum_{i=0}^n i $
Da cui ricavo la relazione ricorsiva:
$ 1)\displaystyle f(n)=n+f(n-1) $ per $ \displaystyle n > 0 $
$ \displaystyle f(0)=0 $
Sia A(x) la funzione generatrice di f(n).
$ \displaystyle A(x)=\sum f(n) x^n $
Moltiplico la 1 per $ x^n $ ottenendo:
$ 2)\displaystyle f(n)x^n = (n) x^n+f(n-1)x^n $
dalla 2 deduco (sommando da 0 a infinito):
$ \displaystyle\sum f(n)x^n =A(x)-f(0)=A(x)=xA(x)+\sum nx^n $
ovvero:
$ \displaystyle A(x)=\frac{\sum nx^n}{1-x} $
$ \displaystyle = \frac{x}{(1-x)^3} $
$ \displaystyle =\frac{1}{2} (\frac{x+1}{(1-x)^3}-\frac{1}{(1-x)^2}) $
$ \displaystyle =\frac{1}{2}(\sum (n+1)^2x^n-(n+1)x^n) $
$ \displaystyle =\sum \frac{n(n+1)}{2}x^n $
Quindi $ \displaystyle f(n)= \frac{n(n+1)}{2} $