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.

The answer that's already been given is no doubt the "right" one, but maybe you still find the generating function approach interesting. It's a quite simple idea that you can apply to these kinds of problems very often and that may yield results even if you can't directly find a solution via known formulas as you're able to do in this case. The basic idea is to view as your sequence $$S_n = \sum_{i=1}^{n-1} i(n-i), n \geq 2$$ as the coefficient in a formal power-series defining some function $F(x) = \sum_{n=2}^\infty S_n x^n$. You then try to find a closed form expression for the function and then taylor-expand (or expand in other ways) this closed-form to get back the coefficients which you've defined to be exactly the elements of your sequence. This is basically a discrete integral transformation. To start applying this technique it's often useful to find a recurrence, so we start
$$
S_{n+1} = \sum_{i=1}^n i (n+1 - i) = \sum_{i=1}^n i (n-i) + \sum_{i=1}^n i = \sum_{i=1}^{n-1} i (n-i) + n(n-n) + \frac{n(n+1)}{2} = S_n + \frac{n(n+1)}{2}.
$$
So we have found a recurrence in the sequence. Now you multiply both sides by a power (I like to go with $x^{n+1}$, some authors prefer just always doing $x^n$) of the formal variable $x$ and sum over all possible $n$. So we get
$$
\sum_{n=2}^\infty S_{n+1} x^{n+1} = \sum_{n=2}^\infty S_n x^{n+1} + \frac{n(n+1)}{2} x^{n+1}
\iff \sum_{n=2}^\infty S_{n} x^{n} - S_2 x^2 = x \sum_{n=2}^\infty S_n x^n + \sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1}
$$
At this point we bring in our function $F$ which we defined exactly as this power series that we now have. So we have
$$
F(x) - S_2 x^2 = x F(x) + \sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1}
\iff F(x) = \frac{1}{1-x} (S_2 x^2 + \sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1}).
$$
We readily find $S_2=1$ by just substituting $2$ into the definition of $S_n$ and thus have
$$
F(x) = \frac{1}{1-x} (x^2 + \sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1}).
$$
Lets try to find a closed form expression for $\sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1}$ by focusing on $\sum_{n=0}^\infty n(n+1)x^{n+1}$. To do this note that the geometric series is $\sum_{i=0}^\infty x^i = \frac{1}{1-x}$. Take the derivative on both sides to find $\frac{d}{dx} \frac{1}{1-x} = \sum_{i=0}^\infty ix^{i-1} = \sum_{i=1}^\infty i x^{i-1}$ and again to get
$$
\frac{d^2}{dx^2} \frac{1}{1-x} = \sum_{i=1}^\infty i(i-1)x^{i-2} = \sum_{i=2}^\infty i(i-1) x^{i-2} = \sum_{i=1}^\infty (i+1)i x^{i-1} \\
\iff \sum_{i=1}^\infty (i+1)ix^i = x \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2x}{(1-x)^3}.
$$
Now we just have to do some "bookkeeping" to get this into the form we need. We calculate
$$
\sum_{n=2}^\infty \frac{n(n+1)}{2}x^{n+1} = \frac{x}{2} (\sum_{i=1}^\infty n(n+1) x^n - 1(1+1)x^1) = \frac{x}{2}(\frac{2x}{(1-x)^3} - 2x) = \frac{x^2}{(1-x)^3}-x^2
$$
and thus
$$
F(x) = \frac{1}{1-x} (x^2 + \frac{x^2}{(1-x)^3} - x^2) = x^2 \frac{1}{(1-x)^4} = x^2 \sum_{n=0}^\infty \frac{(n+1)(n+2)(n+3)}{6}x^n = \sum_{n=0}^\infty \frac{(n+1)(n+2)(n+3)}{6} x^{n+2} = \sum_{n=2}^\infty (\frac{(n-1)n(n+1)}{6} - 1)x^n
$$
and since we defined $F$ via such an exact sequence where the coefficients were $S_n$ we have
$$
S_n = \frac{(n-1)n(n+1)}{6}.
$$
Note that this may seem terribly complicated/roundabout but that's because I've chosen to do everything explicitly here. You can also use a "calculus of generating functions" that allows you to skip a lot of steps.
