Rewriting nested summations that sometimes sum to zero

Question

Is there a way of re-writing the following formula in terms of just $n$:

$$r = \sum_{i=1}^{n}\sum_{j=i+1}^n\sum_{k=i+j-1}^n 1 $$

From what I understand, when $i+j-1 \gt n$ the inner-most sum is zero, and this is where my attempts collapse as I'm not sure what to do to cover it.

BTW this problem is from 'The Algorithm Design Manual', exercise 2.4. I've managed to do the re-writing for examples without this 'inner-sum=zero' condition, but I am stumped on this one.

Answer 1

The middle sum will be from $i+1$ to $n+1-i$ because, after that, the $k$ sum is empty.

The first sum goes from $1$ to $\lfloor n/2\rfloor$.

Let $h=i+j-1$, and then $h$ goes from $2i$ to $n$, and $k$ from $h$ to $n$.

$$\sum_{i=1}^{\lfloor n/2\rfloor}\sum_{h=2i}^{n}\sum_{k=h}^{n}1\\ =\sum_{i=1}^{\lfloor n/2\rfloor}\sum_{h=2i}^{n}(n-h+1)\\ =\sum_{i=1}^{\lfloor n/2\rfloor}\frac{n-2i+1}2(n-2i+2)\\ ={n\choose 2}+{n-2\choose2}+{n-4\choose2}+\ldots $$

Answer 2

Feeling just stupid after my bad and wrong answer, I started from Michael's answer and arrived to $$r_{2m}= \frac{1}{6} m (m+1) (4 m-1)$$ $$r_{2m+1}=\frac{1}{6} m (m+1) (4 m+5)$$