Summations

The sum of the numbers x0, x1, ..., xn is usually written as as x0+x1+...+xn but a shorter notation is: Σni=0xi. In this case, if n=0 then the sum is 0.

Some frequently used summations and identities:

• Σni=0cxi+yi = cΣni=0xi + Σni=0yi
• Σni=0i = n/2(n+1)
• Σni=0xi = (xn+1-1)/x-1

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.