Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the sum of this

$$ \{n,n-1,...,3,2,1\}, ...... \{5,4,3,2,1\}, \{4,3,2,1\}, \{3,2,1\}, \{2,1\}, \{1\} $$

I am learning Data Structures and Algorithms now, I want to calculate the time-complexity of a nested loop. I suspect there is term and formula for this pattern.

    static int count = 0;

    //time complexity of this nested loop
    public static void run(int n) {
        for (int i = 1; i * i < n; i++) {
            for (int j = i; j * j < n; j++) {
                for (int k = j; k * k < n; k++) {

    public static void cal(int n) {
        int total = 0;
        int temp = (int) Math.pow(n, 0.5);
        for (int i = temp; i > 0; i--) {
            total += i * (i + 1) / 2;

    public static void main(String[] args) {
share|cite|improve this question
This doesn't have any influence on the program, but your naming convention is bad. – Norbert Jun 16 '12 at 17:59
up vote 4 down vote accepted

Each of the sums separately is $\sum_{j=1}^k j = \frac{1}{2}k^2 + \frac{1}{2}k$.

In addition, $\sum_{k=1}^n k^2 = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n$,

both of which can be proved by induction.

The total sum is then $$\sum_{k=1}^n \sum_{j=1}^k j = \sum_{k=1}^n (\frac{1}{2}k^2 + \frac{1}{2}k) = \frac{1}{2}\sum_{k=1}^n k^2 + \frac{1}{2} \sum_{k=1}^n k = \frac{1}{6} n^3 + \frac{1}{2} n^2 + \frac{1}{3} n = \frac{n(n+1)(n+2)}{6}$$

share|cite|improve this answer
Note that this is just $n+2\choose3$. In general, the sum of $n\choose k$ from $n=1$ to $m$ is $m+1 \choose k+1$, by a simple counting argument. – Erick Wong Jun 16 '12 at 18:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.