`This is the Curse that keeps on Cursing!`

— Note, I actually like recursion.

In this part we'll start by establishing some mathematical notation commonly used to describe sums before implementing a recursive function for calculating (certain) definite sums in Python.

Initially we'll explore sums of the general form express using the delimited form of Sigma-notation before introducing the generalized form of Sigma-notation which will allow us to express more intricate sums without any extra work, and in general we'll be able to express ourselves more succintly using the generalized form than with the delimited form.

Ultimately we'll introduce the Kronecker Delta which we'll summarize using the ideas that Kenneth E. Iverson introduced in his programming language APL allowing us to be rather expressive with our sums.

Afterwards, in part 2, we'll start expressing these ideas using code using Python, where we will start out by looking at functions only do a certain sum between variable upper- and lower bounds before incrementally adding to our program until we can express some of the same sums that our mathematical notation has afforded us.

### Sums

Le signe $\sum^{i = \infty}_{i=0}$ indique que
l'on doit donne au nombre entier i toutes

ses vaeurs 1, 2, 3, ..., et prenda la
somme des termes.

-- J. Fourier, "Refroidissement séculaire du globe terrestre", *Bulletin des Sciences par la Société Philomathique de Paris* Vol. 3, 7 (1820), 58 – 70 [4]

If you are already quite familiar with the veritable cornucopia of jargon introduced in the preceeding paragraphs feel free to skip ahead to the code section if you are jonesing for some embedded gists.

#### Notation

We'll start at the beginning, consider the sum of the first $n$ natural numbers. That is,

$$1 + 2 + 3 + \cdots + (n-1) + n$$

Thankfully, the '$\cdots$' allow us to write out such a sum without first asserting what $n$ actually is. Basically, what the '$\cdots$' tells us is to complete the pattern established by the surrounding terms.

Sometimes we'd like to find the sum of a general sequence of numbers. Which is to say, not necessarily starting with the number one. Let $a_1, a_2, \ldots , a_n$ be any sequence of numbers, where each number $a_k, k \in \{1, n \} $ is defined somehow.

**Terminology:** We call each element $a_k$ a *term* in the sum.

We are now going to introduce the delimited form of the Sigma-notation which allows us to write the sum $a_1 + a_2 + \cdots + a_n$ more compactly by writing $\sum_{k=1}^{n} a_k$.

That is,

$$\sum_{k=1}^{n} a_k = a_1 + a_2 + \cdots + a_n$$

**Remark:** If $n$ is zero then the value of $\sum_{j=1}^{n} a_j$ is defined to be zero.

What the notation, which was introduced to the world by J. Fourier in 1820, is telling us is that the sum consists of those terms $a_k$ whose index $k$ is an integer where $1 \le k \le n$.

**Terminology:** We call the term after $\sum$ (in the previous example: $a_k$) the *summand*.

$\sum_{k=1}^{2.71828} a_k = a_1 + a_2$

_{1 A modified version of this exercise can be found in [2]}

We define the notation precisely using a recursive definition:

$$ \begin{aligned}
1) \sum_{i=1}^{1} a_i & = a_1 \\

2) \sum_{i=1}^{n} a_i & = \sum_{i=1}^{n-1} a_i + a_n \

\end{aligned} $$

Now we can readily express, as Friedrich Gauss once did at the young age of eight, the sum of the first $100$ natural numbers, i.e.

$$ \sum_{i=1}^{100} i = 1 + 2 + \cdots + 100 = \frac{100\cdot(100 + 1)}{2} = 5050 $$

But we might experience some qualms about expressing some slightly more intricate sums such as the sum of all odd numbers below a 100. As far as the delimited form goes we'd have to write

$$\sum_{k=0}^{49} (2k + 1)$$

which is only readibly available to us after thinking for a short stint. What we'd like is to be able to express the same sum with less work which is where the generalized form of the Sigma-notation comes into play. Expressing the same sum as before we'd write

$$ \sum_{\substack{1 \le k \le 100 \\ k\ odd}} k $$

This notation actually allows us to quite succintly express even more intricate sums. For an example, say we'd like to express the sum of all the primes within a certain bound. Doing so with the old, delimited form we'd have

$$ \sum_{k=n}^{\pi (N)} p_k $$

We can write the above sum equivalently, in the generalized form, like so:

$$\sum_{\substack{p \le N \\ p\ prime}} p $$

Which, hopefully, is readily understandable even by those not familiar with the prime counting function.

What this kind of notation allows for is sums of the sort

$$\sum_{P(k)} a_k $$

where $P$ is a property of the integer $k$.

For the final step I'll allow myself to be rather brief, as I said in the beginning of this article I'll introduce the Kronecker Delta.

However, rather than focusing on it's mathematical properties, we'll utilize Iverson's convention which boils down to enclosing a statement in brackets and letting that statement evaluate to $1$ if true and $0$ if false.

An example seems apt at this point,

$$\left[p\ \textrm{prime} \right] = \begin{cases}1 & , \textrm{if } p \textrm{ is a prime number} \\ 0 & , \textrm{if } p \textrm{ is not a prime number} \end{cases}$$

Thus we can write the sum

$$\sum_{k} a_k \left[P(k)\right] $$

with no constraints at all in regards to the index of summation.

Sources:

Ronald. L. Graham, Donald E. Knuth and Oren Patashnik, *Concrete Mathematics: A Foundation for Computer Science.* Addison-Wesley, 1989; second edition, 1994.

[2] Donald E. Knuth, *The Art of Computer programming*, Volume $1$: Fundamental Algorithms. Addison-Wesley, 1968; third edition, 1997.

[3] Michael Spivak, *Calculus*, Cambridge University Press, third edition, 2006.

[4] Joseph Fourier, "Refroidissement séculaire du globe terrestre", *Bulletin des Sciences par la Société Philomathique de Paris* Vol. 3, 7 (1820), 58 – 70