Editing Summation (section)

== Identities ==
The formulae below involve finite sums; for infinite summations or finite summations of expressions involving [[trigonometric function]]s or other [[transcendental function]]s, see [[list of mathematical series]].

=== General identities ===
: <math>\sum_{n=s}^t C\cdot f(n) = C\cdot \sum_{n=s}^t f(n) \quad</math> ([[distributivity]])<ref name="vpr">{{cite book
 | last1 = Varberg | first1 = Dale E.
 | last2 = Purcell | first2 = Edwin J.
 | last3 = Rigdon | first3 = Steven E.
 | title = Calculus
 | year = 2007
 | publisher = [[Pearson Prentice Hall]]
 | edition = 9th
 | isbn = 978-0131469686
 | page = 217
}}</ref>
: <math>\sum_{n=s}^t f(n) \pm \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left(f(n) \pm g(n)\right)\quad</math> ([[commutativity]] and [[associativity]])<ref name="vpr"/>
: <math>\sum_{n=s}^t f(n) = \sum_{n=s+p}^{t+p} f(n-p)\quad</math> (index shift)
: <math>\sum_{n\in B} f(n) = \sum_{m\in A} f(\sigma(m)), \quad</math> for a [[bijection]] {{mvar|σ}} from a finite set {{mvar|A}} onto a set {{mvar|B}} (index change); this generalizes the preceding formula.
: <math>\sum_{n=s}^t f(n) =\sum_{n=s}^j f(n) + \sum_{n=j+1}^t f(n)\quad</math> (splitting a sum, using [[associativity]])
: <math>\sum_{n=a}^{b}f(n)=\sum_{n=0}^{b}f(n)-\sum_{n=0}^{a-1}f(n)\quad</math> (a variant of the preceding formula)
: <math>\sum_{n=s}^t f(n) = \sum_{n=0}^{t-s} f(t-n)\quad</math> (the sum from the first term up to the last is equal to the sum from the last down to the first)
: <math>\sum_{n=0}^t f(n) = \sum_{n=0}^{t} f(t-n)\quad</math> (a particular case of the formula above)
: <math>\sum_{i=k_0}^{k_1}\sum_{j=l_0}^{l_1} a_{i,j} = \sum_{j=l_0}^{l_1}\sum_{i=k_0}^{k_1} a_{i,j}\quad</math> (commutativity and associativity, again)
: <math>\sum_{k\le j \le i\le n} a_{i,j} = \sum_{i=k}^n\sum_{j=k}^i a_{i,j} = \sum_{j=k}^n\sum_{i=j}^n a_{i,j} =
\sum_{j=0}^{n-k}\sum_{i=k}^{n-j} a_{i+j,i}\quad</math> (another application of commutativity and associativity)
: <math>\sum_{n=2s}^{2t+1} f(n) = \sum_{n=s}^t f(2n) + \sum_{n=s}^t f(2n+1)\quad</math> (splitting a sum into its [[parity (mathematics)|odd]] and [[parity (mathematics)|even]] parts, for even indexes)
: <math>\sum_{n=2s+1}^{2t} f(n) = \sum_{n=s+1}^t f(2n) + \sum_{n=s+1}^t f(2n-1)\quad</math> (splitting a sum into its odd and even parts, for odd indexes)
:<math>\biggl(\sum_{i=0}^{n} a_i\biggr) \biggl(\sum_{j=0}^{n} b_j\biggr)=\sum_{i=0}^n \sum_{j=0}^n a_ib_j \quad</math> ([[distributivity]])
: <math>\sum_{i=s}^m\sum_{j=t}^n {a_i}{c_j} = \biggl(\sum_{i=s}^m a_i\biggr) \biggl( \sum_{j=t}^n c_j \biggr)\quad</math> (distributivity allows factorization)
: <math>\sum_{n=s}^t \log_b f(n) = \log_b \prod_{n=s}^t f(n)\quad</math> (the [[logarithm]] of a product is the sum of the logarithms of the factors)
: <math>C^{\sum\limits_{n=s}^t f(n) } = \prod_{n=s}^t C^{f(n)}\quad</math> (the [[exponentiation|exponential]] of a sum is the product of the exponential of the summands)
: <math>\sum^{k}_{m = 0}\sum^{m}_{n = 0}f(m,n)=\sum^{k}_{m = 0}\sum^{k}_{n = m}f(n,m),\quad</math>for any function <math display="inline">f</math> from <math display="inline">\mathbb{Z}\times\mathbb{Z}</math>.

=== Powers and logarithm of arithmetic progressions ===
: <math>\sum_{i=1}^n c = nc\quad</math> for every {{mvar|c}} that does not depend on {{mvar|i}}
: <math>\sum_{i=0}^n i = \sum_{i=1}^n i = \frac{n(n+1)}{2}\qquad</math> (Sum of the simplest [[arithmetic progression]], consisting of the first ''n'' natural numbers.){{r|CRC|p=52}}
: <math>\sum_{i=1}^n (2i-1) = n^2\qquad</math> (Sum of first odd natural numbers)
: <math>\sum_{i=0}^{n} 2i = n(n+1)\qquad</math> (Sum of first even natural numbers)
: <math>\sum_{i=1}^{n} \log i = \log (n!)\qquad</math> (A sum of [[logarithm]]s is the logarithm of the product)
: <math>\sum_{i=0}^n i^2 = \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\qquad</math> (Sum of the first [[square number|squares]], see [[square pyramidal number]].) {{r|CRC|p=52}}
: <math>\sum_{i=0}^n i^3 = \biggl(\sum_{i=0}^n i \biggr)^2 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4}\qquad</math> ([[Nicomachus's theorem]]) {{r|CRC|p=52}}

More generally, one has [[Faulhaber's formula]] for <math>p>1</math>
: <math> \sum_{k=1}^n k^{p} = \frac{n^{p+1}}{p+1} + \frac{1}{2}n^p + \sum_{k=2}^p \binom p k \frac{B_k}{p-k+1}\,n^{p-k+1},</math>
where <math>B_k</math> denotes a [[Bernoulli number]], and <math>\binom p k</math> is a [[binomial coefficient]].

=== Summation index in exponents ===
In the following summations, {{mvar|a}} is assumed to be different from 1.

: <math>\sum_{i=0}^{n-1} a^i = \frac{1-a^n}{1-a}</math> (sum of a [[geometric progression]])
: <math>\sum_{i=0}^{n-1} \frac{1}{2^i} = 2-\frac{1}{2^{n-1}}</math> (special case for {{math|1=''a'' = 1/2}})
: <math>\sum_{i=0}^{n-1} i a^i =\frac{a-na^n+(n-1)a^{n+1}}{(1-a)^2}</math> ({{mvar|a}} times the derivative with respect to {{mvar|a}} of the geometric progression)
: <math>\begin {align}
\sum_{i= 0}^{n-1} \left(b + i d\right) a^i &= b \sum_{i= 0}^{n-1} a^i + d \sum_{i= 0}^{n-1} i a^i\\
 & = b \left(\frac{1-a^n}{1-a}\right) + d \left(\frac{a-na^n+(n-1)a^{n+1}}{(1-a)^2}\right)\\
 & = \frac{b(1-a^n) - (n - 1)d a^n}{1 - a}+\frac{da(1 - a^{n - 1})}{(1 - a)^2}
\end {align}</math>
:::(sum of an [[arithmetico–geometric sequence]])

=== Binomial coefficients and factorials ===
{{Main|Binomial coefficient#Sums of the binomial coefficients}}

There exist very many summation identities involving binomial coefficients (a whole chapter of ''[[Concrete Mathematics]]'' is devoted to just the basic techniques). Some of the most basic ones are the following.

====Involving the binomial theorem====
: <math>\sum_{i=0}^n {n \choose i}a^{n-i} b^i=(a + b)^n,</math> the [[binomial theorem]]
: <math>\sum_{i=0}^n {n \choose i} = 2^n,</math> the special case where {{math|1=''a'' = ''b'' = 1}}
: <math>\sum_{i=0}^n {n \choose i}p^i (1-p)^{n-i}=1</math>, the special case where {{math|1=''p'' = ''a'' = 1 − ''b''}}, which, for <math>0 \le p \le 1,</math> expresses the sum of the [[binomial distribution]]
: <math>\sum_{i=0}^{n} i{n \choose i} = n(2^{n-1}),</math> the value at {{math|1=''a'' = ''b'' = 1}} of the [[derivative]] with respect to {{mvar|a}} of the binomial theorem
: <math>\sum_{i=0}^n \frac{n \choose i}{i+1} = \frac{2^{n+1}-1}{n+1},</math> the value at {{math|1=''a'' = ''b'' = 1}} of the [[antiderivative]] with respect to {{mvar|a}} of the binomial theorem

==== Involving permutation numbers====
In the following summations, <math>{}_{n}P_{k}</math> is the number of [[k-permutation|{{math|''k''}}-permutations of {{math|''n''}}]].
: <math>\sum_{i=0}^{n} {}_{i}P_{k}{n \choose i} = {}_{n}P_{k}(2^{n-k})</math>
: <math>\sum_{i=1}^n {}_{i+k}P_{k+1} = \sum_{i=1}^n \prod_{j=0}^k (i+j) = \frac{(n+k+1)!}{(n-1)!(k+2)}</math>
: <math>\sum_{i=0}^{n} i!\cdot{n \choose i} = \sum_{i=0}^{n} {}_{n}P_{i} = \lfloor n! \cdot e \rfloor, \quad n \in \mathbb{Z}^+</math>, where  and <math>\lfloor x\rfloor</math> denotes the [[floor function]].

====Others====
: <math>\sum_{k=0}^{m} \binom{n+k}{n} = \binom{n+m+1}{n+1}</math>
: <math>\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}</math>
: <math>\sum_{i=0}^n i\cdot i! = (n+1)! - 1</math>
: <math>\sum_{i=0}^n {m+i-1 \choose i} = {m+n \choose n}</math>
:<math>\sum_{i=0}^n {n \choose i}^2 = {2n \choose n}</math>
:<math>\sum_{i=0}^n \frac{1}{i!} = \frac{\lfloor n!\; e \rfloor}{n!}</math>

===Harmonic numbers===

: <math>\sum_{i=1}^n \frac{1}{i} = H_n\quad</math> (the {{mvar|n}}th [[harmonic number]])
: <math>\sum_{i=1}^n \frac{1}{i^k} = H^k_n\quad</math> (a [[generalized harmonic number]])