Finding a closed formula for a simple integer sequence sum I'm trying to compute the average path lengths of a path graph.
I made the following observations:
There are $n$ nodes and $n-1$ edges and:
$n-1$ paths of length $1$
$n-2$ paths of length $3$
$n-3$ paths of length $4$
...
$1$ path of length $n-1$
I'd like to compute this sum, so that I could then find the average by dividing it by $n(n-1)$. It seems very easy yet I'm having trouble finding a closed formula for :
$$
S = \sum_{i = 1}^{n-1}{i (n-i)}
$$
I feel like it's related to the binomial formula.

Since it's induction time for me,
let
$S(n) = \sum_{i = 1}^{n}{i (n-i)}
$.
(As noted in another answer,
the term with $i=n$
is zero.)
Then
$\begin{array}\\
S(n+1) 
&= \sum_{i = 1}^{n+1}{i (n+1-i)}\\
&= \sum_{i = 1}^{n}{i (n+1-i)}\\
&= \sum_{i = 1}^{n}{i ((n-i)+1)}\\
&= \sum_{i = 1}^{n}{i (n-i)}+\sum_{i = 1}^{n}{i}\\
&=S(n)+\frac12 n(n+1)\\
\text{so}\\
S(m)
&=S(0)+\sum_{n=0}^{m-1}(S(n+1)-S(n))\\
&=0+\sum_{n=0}^{m-1}\frac12 n(n+1)\\
\end{array}
$
Then you can use
the methods in
Misha Lavrov's answer
to get the result.
