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.
Best Answer
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.