<s>[INST] 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.
 [/INST] 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.
</s>