Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

mochow's blog

Sum of Series
By mochow, 10 years ago, In English

Let us have a look at this series:

nm + (n-1)(m-1) + (n-2)(m-2) + (n-3)(m-3) + ...... + (until either n==1 or m==1).

Example:

Let, n=5, m=3. So we need to find the summation of

5.3 + 4.2 + 3.1

Well, what I need is a closed form. And how should I find out a closed form of such kind of series?

Thanks in advance! :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

let's assume that n < m
we know that 1*1 + 2*2 + 3*3 + ... + k*k = (2k + 1)(k + 1)k / 6
so we just need to calculate (m — n)*n + (m — n) * (n-1) + ... which is equal to (m — n) * (n + 1)n/2
so it will be (2n+1)(n+1)n/6 + (m-n)(n+1)n/2 = ((n+1)(n)(3m — n + 1))/6

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay I got it. Tricky and beautiful.

    PS: Did you participate Codechef's Kodeathon? You are so fast! :)

    → Reply
»
10 years ago, # |
← Rev. 14   Vote: I like it +3 Vote: I do not like it

Let's suppose that n ≤ m.

S = n2·m - (n + m)n(n - 1) / 2 + (n - 1)n(2n - 1) / 6

→ Reply