Summation ($\sum$)

Summation is repeated addition, conventionally written with the symbol $\sum$.

The Euler-Maclaurin formula relates a sum to an integral, endpoint corrections, and terms involving Bernoulli numbers and endpoint derivatives. Truncating after finitely many derivative corrections gives a remainder term that must be controlled; this supports accurate estimates of long sums.

A sum whose resulting value is a prime number. This is a condition on the value, rather than a requirement that the summation index run over prime numbers. Counting subsets with a prime-valued sum can use subset sum counts followed by a primality filter on the possible totals.

A telescoping sum cancels intermediate sequence terms, leaving boundary terms. For a finite sequence of real numbers $a_0,\dots ,a_n$, the displayed identity follows because every $a_1,\dots ,a_{n-1}$ occurs once with each sign. Applying it to an infinite series also requires checking the limit of the boundary terms; finite cancellation alone does not prove that the series is a convergent series.^[ref]

For $n\ge 1$, expanding the finite sum givesNo monotone sequence assumption is required. Consider the original sequence $4,9,2,7,5$. Its successive finite differences are $5,-7,5,-2$, soThe large intermediate rise and fall disappear from the net change. This is useful whenever one knows successive changes rather than every absolute value: adding the changes reconstructs the final value from the initial one. It also checks a cumulative-update calculation without requiring all increments to be positive.

A finite difference $\Delta a_{k-1}=a_k-a_{k-1}$ measures one discrete change. The identity ${\sum }_{k=1}^n\Delta a_{k-1}=a_n-a_0$ is the discrete counterpart of the fundamental theorem of calculus: accumulation of changes returns the endpoint difference. The related summation by parts transfers a finite difference from one factor of a product to another, with explicit boundary terms.

For a meromorphic function $f$, the displayed telescoping sum identity holds wherever every summand is defined. If the two endpoint terms are finite at $w=w_0$, their difference gives a holomorphic continuation of the entire sum to $w_0$, even when individual summands have poles there. This continued value is a common-shift limit; it does not make an originally undefined sum of complex numbers well defined without an additional convention.

The proof is finite cancellation on the common domain of definition, followed by analytic continuation. For $f(w)=\tanh w$, a common shift away from the imaginary axis avoids its poles. Different independently chosen shifts of individual summands need not give the same limit, so specifying the common shift matters.

Sometimes a sum does not initially look like a difference of neighboring entries. A partial fraction decomposition can reveal the cancellation. For the original examplesubtract the two reciprocals:ThusFor $N=3$, direct addition gives $1/4+1/28+1/70=3/10$. For $N=6$, the six positive entries add to $6/19\approx 0.315789$. The partial sums approach $1/3$, and the exact series remainder isThis formula answers an accuracy question as well as a summation question. To make the remaining positive series remainder smaller than $0.001$, solve $1/[3(3N+1)]<1/1000$. The result is $9N+3>1000$, so the smallest permitted integer is $N=111$. At $N=110$, the error is $1/993>0.001$; at $N=111$, it is $1/1002<0.001$.

For a real sequence $(a_n)$, the partial sum of ${\sum }_{k=1}^{\infty }(a_k-a_{k-1})$ is exactly $a_n-a_0$. Consequently it is a convergent series if and only if $a_n$ has a finite limit $L$, and its sum is $L-a_0$. Cancellation takes place inside each finite partial sum; taking a limit is a separate step.^[ref]

The partial fraction telescoping example has $S_N=N/(3N+1)$ and therefore limit $1/3$. In contrast, let $a_n=(-1{)}^n$. Its first entry is $a_0=1$, so $S_N=(-1{)}^N-1$. The even partial sums are zero and the odd partial sums are negative two. Both finite cancellations are correct, but the sequence has no single limit, giving a divergent series.

It is also essential to keep the two contributions paired. For example, ${\sum }_{k=1}^{\infty }(1/k-1/(k+1))$ is a convergent series with sum one, as its finite partial sum is $1-1/(N+1)$. Writing it instead as ${\sum }_{k=1}^{\infty }1/k-{\sum }_{k=1}^{\infty }1/(k+1)$ asks to subtract two divergent series. The permitted finite cancellation does not define that separate subtraction. Working through partial sums keeps the indices aligned and the operation meaningful.

A sum combines a finite or infinite sequence of terms by repeated addition. The symbol $\sum$ denotes summation over an index.

An empty sum has no terms and is defined to be zero, the identity element for addition. This keeps the rule for combining sums valid when one index set is empty. In a Galton-Watson process, an empty generation contributes an empty sum of offspring counts, so the next generation is empty too. The corresponding convention for multiplication is the empty product, which equals one.

The weighted arithmetic mean combines values according to how much each contributes to the quantity being summarized. For a finite list of real numbers $x_i$ and nonnegative weights $w_i$ with $W={\sum }_i{w}_i>0$, defineZero weights ignore an entry; at least one weight must be positive. Multiplying every weight by the same positive number leaves the result unchanged. Writing $p_i=w_i/W$ makes the weighted mean a convex combination, since $p_i\ge 0$ and ${\sum }_i{p}_i=1$. It therefore lies between the smallest and largest input values. ^[ref]

For example, give the values $90$ and $60$ weights $2$ and $8$:The larger weight pulls the result closer to $60$. The balancing identityexplains a geometric interpretation: if the weights were masses placed at positions $x_i$, the weighted mean would be their center of mass. Here $8(66-60)=2(90-66)=48$, so the two sides balance even though their distances from the mean differ.

Weights need an interpretation. They can represent numbers of observations, masses, or probabilities in a finite probability distribution. These meanings lead to the same formula, while answering different questions. For instance, combining means of groups uses group sizes as weights to recover the mean over individual observations. For a function $f$ and nonnegative weight function $w$, the analogous integral is $\int wf/\int w$, provided $wf$ is integrable and the total weight $\int w$ is positive and finite.

Suppose disjoint nonempty groups have sizes $n_j$ and arithmetic means ${\bar{x}}_j$. The arithmetic mean of all observations isEach group contributes the sum $n_j{\bar{x}}_j$; add those totals before dividing by the overall count. This is exactly a weighted mean of group means with weights equal to group sizes. ^[ref]

Take a synthetic example with two observations equal to $90$ and eight equal to $60$. The two group means are $90$ and $60$, and the combined mean is $66$. Giving the two groups equal weights instead produces $(90+60)/2=75$, which summarizes the two group means with equal influence. To summarize all ten individuals with equal influence, use their group counts.

The group means and counts determine the combined arithmetic mean, but do not generally determine the combined variance. Variation within the groups is additional information.

For a finite list of real numbers $x_i$ and nonnegative weights of positive total $W$, the weighted mean uniquely minimizes the weighted sum of squared deviationsExpanding around ${\bar{x}}_w$ and using ${\sum }_i{w}_i(x_i-{\bar{x}}_w)=0$ givesEvery displacement from the weighted mean increases the objective. This is the simplest one-parameter weighted least squares problem: represent all entries by one common value.

For the weighted values $90$ and $60$ with weights $2$ and $8$,Thus $S(66)=1440$, while $S(75)=2250$. The minimum is defined by this squared-error criterion; a different loss can select a different summary, such as a median under unweighted absolute deviations.

For a nonempty finite list of real numbers $x_1,\dots ,x_n$, the arithmetic mean isIt is the weighted mean with equal weights, giving each observation equal influence. For $(2,4,9)$, the sum is $15$ and the arithmetic mean is $5$. Replacing every value by $5$ retains the same total. The residuals $-3,-1,4$ sum to zero, so the mean is also the balancing point of these equally weighted observations.

The arithmetic mean minimizes the sum of squared deviations by the weighted mean minimizes squared deviations identity with all weights one. A large input can consequently have a substantial effect: replacing $9$ by $90$ changes the mean to $32$, while the median remains $4$. The choice of summary depends on what aspect of the data matters.

The harmonic mean of a nonempty finite list of positive real numbers is the multiplicative inverse of the arithmetic mean of their inverses:For two inputs, $H=2x_1{x}_2/(x_1+x_2)$. Replacing each input by $H$ preserves the sum of inverses, making it useful when a fixed amount divided by a rate determines a cost or duration. This positive-input definition avoids division by zero; negative inputs need not retain the usual averaging or ordering properties. ^[ref].

Travel two legs of equal length $d$ at positive speeds $v_1,v_2$, with no stops. Their travel times are $d/v_1$ and $d/v_2$, so the average speed isFor two $60\mathrm{km}$ legs at $30$ and $60km/h$, the times are two hours and one hour. The average speed is $120/3=40km/h$. The same speeds maintained for one hour each instead cover $90\mathrm{km}$ in two hours, giving the arithmetic mean $45km/h$. A slower equal-distance leg occupies more time, so the data being averaged must include what is held equal. This is total distance traveled divided by elapsed time; a return journey can have zero average velocity while keeping a positive average speed. ^[ref].

The arithmetic-geometric mean inequality applied to the inverses gives $H\le G$; together with $G\le A$ it yields the comparison in geometric mean. For two inputs the arithmetic–harmonic gap has the exact formFor $30$ and $60$ the gap is five. With one positive input held fixed and another approaching zero, the harmonic mean approaches zero too: a very slow fixed-distance leg dominates the travel time. Unequal leg lengths instead require a weighted harmonic mean.

For positive real numbers $x_i$ and nonnegative weights with ${\sum }_i{w}_i=1$, the weighted harmonic mean isEqual weights give the harmonic mean, while a zero weight excludes that input. For travel at positive constant speeds $v_i$ over positive leg lengths $d_i$, the weights are fractions of total distance:For $30\mathrm{km}$ at $30km/h$ and $90\mathrm{km}$ at $60km/h$, the weights are $1/4,3/4$, elapsed time is $5/2$ hours, and the average speed is $48km/h$. Weighting the speeds by their time fractions instead gives the same result as a weighted arithmetic mean: $(2/5)30+(3/5)60=48$. The two weight systems describe the same journey in different coordinates and must not be interchanged. ^[ref].

A prefix sum stores the accumulated sum through a specified position in a finite sequence or array. For inputs $a_1,\dots ,a_n$, include the empty sum $P_0=0$ and setFor the original input $(4,-2,5,-1,3,-4)$, the prefix array including $P_0$ is $(0,4,2,7,6,9,5)$. A negative entry makes the accumulated sum decrease; a prefix sum does not have to be monotone. Conversely, the original entry is recovered by subtraction: $a_m=P_m-P_{m-1}$.

The useful cancellation is that any contiguous block has sumBoth prefixes include the entries before $\ell$; subtracting cancels those entries. In the example, the sum from positions two through four is $-2+5-1=2$, recovered as $P_4-P_1=6-4$. The arithmetic mean of that block is $2/3$, obtained by dividing its sum by its length. Prefix sums therefore make many repeated questions about an unchanged array cheap: reuse accumulated totals instead of resumming every block.

The sequential recurrence builds all $n+1$ prefixes in $O(n)$ time complexity and storage; each block query needs two reads and one subtraction, hence $O(1)$ time complexity. These counts assume constant-cost arithmetic and access to array entries. If one input changes, all later stored prefixes change, so this simple representation is most useful when queries outnumber updates. For integer inputs, sufficient numeric capacity must be retained; with floating-point arithmetic, subtracting large nearby prefixes can lose relative accuracy for a small block total. The exact mathematical identity does not eliminate representation error.

The apparently sequential recurrence also motivates a prefix scan: associativity permits a tree of partial calculations that yields all accumulated results in parallel. Guy E. Blelloch's 1990 technical report systematically develops this operation and its applications; its authored chapter version explains the two tree sweeps used to obtain all prefixes. ^[ref]. ^[ref].

A prefix scan computes successive accumulated results for an associative operation $\oplus$ while keeping input order fixed. A scan based on addition produces prefix sums; one based on matrix multiplication produces successive ordered matrix products. Associativity allows regrouping, while commutativity is unnecessary because the order stays fixed. If an initial empty prefix is included, its value is the identity element for the chosen operation.

The ability to compute accumulated results does not by itself allow subtraction of two prefixes. For example, two accumulated minima cannot reveal a block minimum: the lists $(1,7,8)$ and $(1,2,3)$ both have successive minima $(1,1,1)$, but the minimum of positions two through three is seven for one and two for the other. Prefix sums support block recovery because addition has additive inverses; an arbitrary associative operation need not have that property.