21
$\begingroup$

I've been a programmer for ten years, and once upon a time I was pretty good at math. Those days are long gone. I'm taking some online classes and now I find myself needing to remember the math I learned in college and it has all gone bye-bye.

Specifically, I have a question about $\Sigma$ (Sigma):

In an $\Sigma$ equation, there is an N above the $\Sigma$, and an $i = 1$ (or some number) below. If someone could help my programmer mind - this looks like a for loop in programming. Is that essentially what is going on with everything inside the $()$ of the $\Sigma$? It simply computes all the values for each iteration from $i$ to N and then sums them all up?

$\endgroup$
12
  • 1
    $\begingroup$ Yes, this is what it means. $\endgroup$ Mar 12, 2016 at 14:42
  • 1
    $\begingroup$ Essentially, yes. Read more on wikipedia. There do exist other ways of using it besides starting with $i=start$ and cycling through all integer values from $start$ to $end$. For example the well known handshaking lemma in graph theory $\sum\limits_{v\in V}\deg(v)=2|E|$ which says that the sum of the degrees of the vertices in any graph must equal twice the number of edges. Here, we use an indexing set, $V$, and cycle over all elements, $v$, in that set. $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 14:44
  • 3
    $\begingroup$ @JustinBenfield $\prod$ \prod $\endgroup$
    – JMoravitz
    Mar 12, 2016 at 14:47
  • 1
    $\begingroup$ @JMoravitz: Some programming languages allow this form too. For example, in C++ you can say "for (auto v: V") if V is a container. $\endgroup$
    – TonyK
    Mar 12, 2016 at 15:23
  • 4
    $\begingroup$ @Archis: two mistakes: { should be (, and , should be ;. Very sloppy! $\endgroup$
    – TonyK
    Mar 12, 2016 at 15:59

6 Answers 6

14
$\begingroup$

Well yeah, sort of. But not really, IMO.

What most programming languages do is a awkward, mathematically speaking. An imperative for-loop increments a variable. That shouldn't really be possible: maths doesn't know time. If you define something once then it'll conceptually hold always, i.e. if you start out with $i = 0$ it's not possible to later have $i=3$.

What's really going on, mathematically, is that you write an abstraction, an expression for all $i$. Then you apply to that expression the higher-order operation “sum over all such $i$ in some range”. The variable $i$ never actually has any particular value, it's just a placeholder for “consider value here”.

There is a proper mathematical framework that can nicely express computations like a sum. It's called lambda calculus. In this, such an abstraction over some variable is called a lambda expression, written like* $$ \lambda i \mapsto \frac1{2^i} $$ More commonly, this kind of abstraction would be called a function and written $$ f : \mathbb{N}\to\mathbb{Q}, \quad f(i) = \frac{1}{2^i} $$ or, in programming languages, something like

double f(int i) {
  return 1.0 / 2**i;
}

Now, what a summation operator does is, it takes such a lambda function and yields a number equal to the function evaluated with all possible arguments in a range and summed up. For instance, $$ S = \sum_{i=0}^{5}\frac1{2^i} $$ is in a sense shorthand notation for something $$ S = \Sigma(0,5,f). $$ Note that I didn't write $f(i)$ but just $f$: this is not the result of applying $f$ to any particular $i$, but the function object $f$ itself. It is not a number but, well, a function.

It's not necessary to first give $f$ a name and then use it in the sum, I can also just put in the lambda expression: $$ S = \Sigma(0,5,\lambda i\mapsto 1/2^{i}). $$ I understand sums as a special way of writing this expression.

Now as for how to the summation operator can actually be implemented in a computer? Well: in an imperative language, a for-loop would certainly be a reasonably way to do it. Like,

double sumFromTo(int i0, int iend, function<double(int)> f) {
  int i;
  double result;
  for(i=0; i<=iend; ++i) {
    result += f(i);
  }
  return result;
}

But as I said, mathematically it doesn't really make sense to change the value of a variable. However, it is possible to define the equivalent of such a loop directly in lambda-calculus: through recursion. This requires some a bit weird definitions to use it in the original maths/logic setting, but can also be written in programming languages:

double sumFromTo_rec(int i, int iend, function<double(int)> f) {
  if (i<=iend)
    return f(i) + sumFromTo_rec(i+1, iend, f);
   else
    return 0;
}

Now, in the recursive call, i will have the value of i+1 from the outer call. So, am I doing mathematically unsound mutation here again? No actually! The i function argument is only an abstraction. In the inner function call, it's simply a different variable, which just happens to also be called i (but that's an irrelevant implementation detail).

You may well think this silly. If the computer can just re-use the same variable i by incrementing it, why should we bother with defining a new one? You'd be right in a way. sumFromTo_rec would in fact be inefficient in a language like C, because the computer would have to allocate an actual new integer on the stack in each function call.

However, quite practically speaking, mutating variables also opens up numerous possibilities for programming bugs. Functional programming language therefore eschew (or entirely forbid) this. These languages have come up with various optimisations like tail-calls to avoid the overhead of allocating new variables in every recursive call (so basically, you write clean mathematical semantics but under the hood the same memory is actually re-used, like it would be in an imperative language).

If you're a mathematically-interested programmer (or a computation-interested mathematician) I recommend you check out Haskell. It's a modern functional programming language with very clean semantics, yet great performance and good compatibility to “real world applications”. The above recursive summation would in Haskell look as simple as

sumFromTo i₀ iEnd f
    | i₀<=iEnd   = f i₀ + sumFromTo (i₀+1) iEnd f
    | otherwise  = 0

That's similar enough to how the rigorous recursive definition of $\sum$ in maths notation would look: $$ \sum_{i=i_0}^{i_{\text{end}}} f(i) = \begin{cases} f(i_0) + \sum_{i=i_0+1}^{i_{\text{end}}}f(i) & \text{if $i_0 < i_{\text{end}}$} \\ 0 & \text{otherwise} \end{cases} $$ Observe that $f(i)$ as such is never actually evaluated: it's always $f(i_0)$ (however, that variable has a different value in each recursion level). This is better reflected in a programming language than it is in the maths notation: the former really make a point of not applying $f$ to anything when you're talking about the function itself, rather then the result from applying that function to any particular argument.


*The classical standard notation in lambda calculus is actually $\lambda i.\ 1/{2^i}$, but I reckon the arrow makes it clearer what's going on than a dot. Most programming languages use an arrow symbol if they offer lambda functions, e.g. in Haskell you'd write

sumFromTo 0 6 (\i -> 1/2^i)

Unlike in maths, it's generally preferred in programming (except in Fortran and Matlab, which I don't consider very well-designed) to express the range with upper bound excluded. This turns out to be the most useful convention in practice; see what famous Dijkstra wrote on the matter.

$\endgroup$
4
  • $\begingroup$ Very clear! Can you write the explicit definition of the "$\sum$" function (i.e. the assigning mechanism behinds) in mathematical expression? And it modern mathematics, the essence of the "$\sum$" function is always considered by lambda calculus? $\endgroup$
    – Eric
    Aug 29, 2016 at 5:50
  • $\begingroup$ So is there truly NO so-called variables in mathematics? Why can't mathematics adopt this "vary" idea? What is the flaws and disasters when we do so? Thanks! $\endgroup$
    – Eric
    Aug 29, 2016 at 6:03
  • $\begingroup$ And, to study lambda calculus and Y-combinators and so on, which book you recommend? Thanks! $\endgroup$
    – Eric
    Aug 29, 2016 at 6:10
  • $\begingroup$ @Eric: mathematics can adapt this “vary idea”. A quite obvious, but hardly useful way to do it is to not consider a single value, but a whole history of values. This history as a whole never changes, you just consider different points in it! An often better approach is to focus on the state changes between the single steps. Values of “state change type” can be chained together with purely functional terms, using concepts from category theory (the mapping “types of constant values → types of state-change values” is a monad). $\endgroup$ Aug 29, 2016 at 12:26
7
$\begingroup$

Yes, sort of. By (recursive) definition, $$\sum_{i=0}^0 a_i := a_0 $$ and $$\sum_{i=0}^n a_i :=\sum_{i=0}^{n-1} a_i + a_n $$ or, sloppily, $$\sum_{i=0}^n a_i :=a_0 + a_1+ \dots +a_n$$

$\endgroup$
5
$\begingroup$

In Mathematica I frequently switch between the Sum and the Table commands like in these examples:

Example 1:

$\sum\limits_{n=1}^{n=1} 1 = 1 = 1 $

$\sum\limits_{n=1}^{n=2} 1 = 2 = 1+1 $

$\sum\limits_{n=1}^{n=3} 1 = 3 = 1+1+1 $

$\sum\limits_{n=1}^{n=4} 1 = 4 = 1+1+1+1 $

$\sum\limits_{n=1}^{n=5} 1 = 5 = 1+1+1+1+1 $

Sum[1,{n,1,5}]

which outputs: 5

compared to:

Table[1,{n,1,5}]

which outputs: {1,1,1,1,1}

Example 2:

$\sum\limits_{n=1}^{n=1} n = 1 = 1 $

$\sum\limits_{n=1}^{n=2} n = 3 = 1+2$

$\sum\limits_{n=1}^{n=3} n = 6 = 1+2+3$

$\sum\limits_{n=1}^{n=4} n = 10 = 1+2+3+4$

$\sum\limits_{n=1}^{n=5} n = 15 = 1+2+3+4+5$

Sum[n,{n,1,5}]

which outputs: 15

compared to:

Table[n,{n,1,5}]

which outputs: {1,2,3,4,5}

Example 3:

$\sum\limits_{n=1}^{n=1} \frac{n(n+1)}{2} = 1 = 1$

$\sum\limits_{n=1}^{n=2} \frac{n(n+1)}{2} = 4 = 1+3$

$\sum\limits_{n=1}^{n=3} \frac{n(n+1)}{2} = 10 = 1+3+6$

$\sum\limits_{n=1}^{n=4} \frac{n(n+1)}{2} = 20 = 1+3+6+10$

$\sum\limits_{n=1}^{n=5} \frac{n(n+1)}{2} = 35 = 1+3+6+10+15$

Sum[n*(n+1)/2,{n,1,5}]

which outputs: 35

compared to:

Table[n*(n+1)/2,{n,1,5}]

which outputs: {1, 3, 6, 10, 15}

I don't know if it is a good answer to your question though.

$\endgroup$
3
$\begingroup$

Yes, indeed.

For example:

$$\sum_{i = 1}^n\frac{x_i}{n}$$

is generally considered the average (mean) of a series $\{x_1, x_2, x_3, x_4, ... x_i\}$.

That would translate to a foreach over an array that divides all the values by the array.length, and sums them all up.

Hope this helped!

$\endgroup$
4
  • 1
    $\begingroup$ You mean $\sum_{i = 1}^n\frac{x_i}{n}$, not $\sum_{i = 0}^n\frac{x_i}{n}$. (Although $\frac{1}{n}\sum_{i = 1}^n x_i$ is more natural.) $\endgroup$
    – TonyK
    Mar 12, 2016 at 15:27
  • $\begingroup$ @TonyK Thanks for that correction! Fixed. $\endgroup$
    – naiveai
    Mar 12, 2016 at 16:10
  • $\begingroup$ Actually, as written this translates to a foreach that takes each number, divides it by $n$, and adds these all together. What you've described (where the numbers are summed, and then the sum is divided by the number) would be $\frac{\sum_{i=1}^n x_i}{n}$. $\endgroup$
    – Tom Church
    Mar 18, 2016 at 14:47
  • $\begingroup$ Which is the same thing! (I think... lemme just correct it) $\endgroup$
    – naiveai
    Mar 18, 2016 at 17:07
2
$\begingroup$

Definitely yes.

The mathematician would write it like this:

$\sum\limits_{i=m}^n f(i)$

And the programmer would write it like this:

result = 0
for (i=m; i<=n; i++) {
    result += f(i)
}

You can think of m as the start index and n as the end index.

$\endgroup$
5
  • 1
    $\begingroup$ It would actually be for (i=m; i<=n; ++k) to match the sum $\sum_{i=m}^n$ (which includes $n$). Anyway, as I argued above, this is problematic: a mathematical sum has no direction. In a C-like language, f could in principle alter some global state so you'd get a different result depending of which direction the loop goes. And, how would you express a sum like $\sum_{i=-\infty}^\infty f(i)$? $\endgroup$ Aug 27, 2016 at 11:23
  • $\begingroup$ I would argue that just because a computer couldn't deliver a result when executing the code doesn't mean that you couldn't express this thing in a programming language. The only problem I see would be that we don't have infinite amounts of memory and thus probably no one has implemented a symbol for infinity yet. $\endgroup$
    – Forivin
    Aug 29, 2016 at 5:30
  • $\begingroup$ i <= n should be the continue criterion. $\endgroup$
    – Frenzy Li
    Aug 29, 2016 at 5:36
  • $\begingroup$ If you think about it, the code doesn't even really represent what the computer will be doing because it would get compiled and optimized. So I would really look at it as a whole. $\endgroup$
    – Forivin
    Aug 29, 2016 at 5:38
  • $\begingroup$ FTR, I just noticed I made the same <= vs < mistake in my original answer... $\endgroup$ Aug 29, 2016 at 12:19
1
$\begingroup$

The $\Sigma$ symbol allows to represent sums with a variable number of terms. Alternatively we can write

$$\sum_{i=1}^N a_i=a_1+a_2+\cdots a_N,$$ but the LHS is more compact. There are similar notations for the product $\prod_{i=1}^N$, logical conjunction $\bigwedge_{i=1}^N$, disjunction $\bigvee_{i=1}^N$, set intersection $\bigcap_{i=1}^N$, union $\bigcup_{i=1}^N$...

There is a slight difference with for-loop statements found in the procedural programming languages: there is no order of evaluation. This is made possible by the fact that there is no "side effect" when "evaluating" the terms.

The notation with $i=1$ and $N$ indeed denotes the discrete range $[1,N]$, and $N<1$ normally implies a zero sum.

In some cases, other "looping" conditions are used, such as

$$\sum_{i=1,\text{ prime }i}^N$$ or $$\sum_{i\in P}$$

$\endgroup$
1
  • 1
    $\begingroup$ Silent downvoters aren't my friends. $\endgroup$
    – user65203
    Dec 4, 2016 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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