Equazioni ricorsive informatica 2

[digitex2001]

ciao ragazzi...mi servirebbe un aiutino in questo esercizio di Informatica 2 sulle equazioni ricorsive...

Effettuare l'unfolding della seguente relazione di ricorrenza R(n):

$ R(0) = 0$
$R(n) = R(n-1) + 2n $
poi sviluppiamo la funzione ricorsivamente:

$R(n) = R(n-1) + 2n = R(n-2) +2(n-1) +2n = R(n-3)+2(n-2)+2(n-1)+2n $
poi in questo esercizio svolto trovato nelle dispense giungiamo a :
$ R(n) = 0+2+4+....+2(n-4)+2(n-3)+2(n-2)+2(n-1)+2n $
e quindi a
$ R(n)=2n*n-2(1+2+3+...+n-1)=2n^(2)-2 sum k $
come si è giunti agli ultimi 2 passaggi?non riesco a capirlo..grazie

[hamming_burst]

Ciao,

definiscimi "unfolding".
A seconda del contesto, per me può avere altri significati.

mai visto scrivere le funzioni di ricorrenza con simbolo $R()$...

PS: ricordati di andare a presentarti

[Rggb1]

L'ha sviluppata algebricamente, raggruppando i termini. Fra l'altro, si può continuare poiché nel secondo termine della forma finale, fra parentesi, hai la somma dei numeri da $1$ a $n-1$, che come ben sai vale...

[digitex2001]

ok..piu che altro non ho capito come arriva a scrivere $ 0+2+4...$ come li ottiene?parlo dell inizio della penultima "espressione"...grazie

[hamming_burst]

Ah ok, "unfolding" lo intendi proprio come ciò che significa ... svolgimento.

estendo un poco ciò che dice Rgggb.
La riscrivo che forse ti è più chiara vista in questo modo (è del tutto equivalente).

$2n -> 2*(n-1) -> 2*(n-2) -> 2*(n-3) -> ... -> 2*sum_{i=0}^{n-1} n-i = 2*sum_{k=1}^{n} k = 2*(n*(n+1))/2 = n^2 + n + O(1) in O(n^2)$

I numeri $0+2+4+...$ li pui riscrivere come $2*(0+1+2+...)$ che è la sommatoria $2*sum_{k=0}^{n} k$ tutto qui

Se hai problemi, chiedi pure

[Rggb1]

"ham_burst":... ciò che dice Rgggb.

Troppe 'g'... mi gggira la testa.

[digitex2001]

vi ringrazio entrambi...dawero gentilissimi=)=)