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.
 A: The brute force approach is to split $S$ as
$$
   S = \sum_{i=1}^{n-1} i(n-i) = \sum_{i=1}^n i(n-i) = n \sum_{i=1}^n i - \sum_{i=1}^n i^2
$$
and then use two well-known formulas: $1 + \dots + n = \frac{n(n+1)}{2}$ and $1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$.
(I changed the sum to end at $i=n$ instead of $i=n-1$ to make applying these formulas easier; since the $i=n$ term is $n(n-n)=0$, this doesn't affect the result.)
Alternatively, write $i(n-i) =  (n+1) \binom i1 - 2 \binom i2$, split up the sum using this, and then use the formula $$\sum_{i=1}^{n-1} \binom ik = \binom n{k+1}.$$
We can also prove these formulas, but that's harder than simply applying them.
A: 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.
A: 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.
