Domanda molto stupida sulla sommatoria

[Zingarelli1]

Non so se sia la sezione adatta ma, tant'è.
Studiando per hobby Algoritmi e Strutture dati mi sono imbattuto in questa affermazione:
"La complessità dell'algoritmo è $ sum_(i=1)^n (n-i) = (n(n-1))/2 = n^2/2 - n/2 $."

Ora, chiedo a voi, quali passaggi ha eseguito per ricavare $ (n(n-1))/2 $ dalla sommatoria?
Immagino che la risposta sia stupida, ma proprio non ci arrivo da solo

Grazie in anticipo

[Anacleto13]

E' una somma notevole.. ci sono varie dimostrazioni in rete


https://it.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_·_·_·

[pilloeffe]

Ciao Zingarelli,

Mi accodo alle corrette risposte di coloro che mi hanno preceduto facendoti osservare che la somma proposta si può scrivere in modo più semplice scrivendone esplicitamente i termini:

$sum_{i = 1}^n (n - i) = (n - 1) + (n - 2) + ... + 1 + 0 = sum_{i = 0}^{n - 1} i $

Questo tipo di somme sono ben note e sono già state trattate diverse volte anche su questo forum, ad esempio qui.

[dissonance]

Se sei un informatico, dai un'occhiata a questo articolo di Knuth:

https://arxiv.org/abs/math/9205211

Con le notazioni di Knuth quella somma verrebbe calcolata così:
\[
\sum_i (n-i)[1\le i\le n]=\sum_i (n-i)[0\le n-i\le n-1],\]perché \([1\le i \le n]=[0\le n-i \le n-1]\), e quindi con la sostituzione \(j=n-i\)
\[
\sum_i (n-i)[0\le n-i\le n-1] =\sum_j j[0\le j\le n-1]= \sum_{j=0}^{n-1} j.\]
E questo è esattamente lo stesso risultato trovato da pilloeffe.


Mi piace molto l'approccio di Knuth alla matematica. Se ti interessa calcolare somme, leggi il secondo capitolo del suo libro "Concrete Mathematics": https://en.wikipedia.org/wiki/Concrete_Mathematics