Implementing Concrete Mathematics Summations in Python

on

Implementing Concrete Mathematics Summations in Python

One of the most satisfying things about mathematics is when a formula you've been staring at on paper suddenly becomes a few lines of working code. This post does exactly that — we take the summation notation from Concrete Mathematics and translate it directly into Python, step by step.

No prior calculus knowledge needed. If you're comfortable with basic algebra and have written a Python function before, you're good to go.

What Is a Summation?

A summation is just a compact way of writing "add a bunch of things up." Instead of writing \(1 + 2 + 3 + \cdots + n\), mathematicians use the capital Greek letter sigma \(\sum\) as a shorthand:

$$\sum_{k=1}^{n} k$$

Let's break down what every part of this notation means, because none of it should feel mysterious:

Part What it means
\(\sum\) "Add up everything that follows"
\(k=1\) (bottom) Start the counter \(k\) at 1
\(n\) (top) Stop when \(k\) reaches \(n\) (inclusive)
\(k\) (after \(\sum\)) The thing being added at each step — here, just \(k\) itself

So \(\sum_{k=1}^{n} k\) means: set \(k = 1\), add \(k\). Set \(k = 2\), add \(k\). Keep going until \(k = n\). For \(n = 5\) that gives \(1 + 2 + 3 + 4 + 5 = 15\).

The thing being added doesn't have to be \(k\) itself — it can be any expression involving \(k\). For example, \(\sum_{k=1}^{n} k^2\) adds up the squares: \(1 + 4 + 9 + 16 + 25 = 55\) for \(n = 5\).

Translating Summation Notation into Python

The great news is that Python's built-in sum() function maps almost directly onto summation notation. Let's build a general summation function that works for any expression. 

from typing import Callable

def summation(func: Callable[[int], float], start: int, end: int) -> float:
    """Compute the sum of func(k) for k from start to end, inclusive."""
    return sum(func(k) for k in range(start, end + 1))

Let's unpack every part of this, because there's more going on than it looks:

from typing import Callable — this imports a type hint called Callable, which lets us say "this argument should be a function." It doesn't change how the code runs — it's just documentation that helps you and your editor understand what the function expects.

func: Callable[[int], float] — func is the thing being summed at each step. It's a function that takes an integer \(k\) and returns a number. For example, lambda k: k just returns \(k\) itself, and lambda k: k**2 returns \(k^2\).

start: int, end: int — the lower and upper limits of the sum, corresponding to the bottom and top of the \(\sum\) sign.

range(start, end + 1) — Python's range(a, b) goes from \(a\) up to but not including \(b\). So we write end + 1 to make sure end itself is included — matching the inclusive upper limit in the summation notation.

func(k) for k in range(...) — this is a generator expression. It produces the values func(1), func(2), ..., func(end) one at a time, and sum() adds them all up.

Trying It Out

Let's compute \(\sum_{k=1}^{10} k = 1 + 2 + \cdots + 10\):

result = summation(lambda k: k, 1, 10)
print(result)

55

The lambda k: k is an anonymous function that just returns its input unchanged — it's the Python equivalent of "the thing being added is \(k\) itself." We pass it as the func argument, with start=1 and end=10.

Closed Forms — Why They Matter

The summation function above works perfectly, but it has a cost: for large \(n\), it loops through every single value of \(k\). If \(n = 1{,}000{,}000\), that's a million additions.

A closed form is a direct formula that gives you the answer in a single calculation, no matter how large \(n\) is. For the sum of integers, the closed form is:

$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$$

For \(n = 10\): \(\frac{10 \times 11}{2} = 55\). Same answer, zero looping.

In Python:

def closed_form(n: int) -> int:
    """Closed form for the sum of integers from 1 to n."""
    return n * (n + 1) // 2

print(closed_form(10))

55

The // is integer division — it divides and discards any remainder. Since either \(n\) or \(n+1\) is always even, \(n(n+1)\) is always divisible by 2, so // gives the exact answer here with no rounding.

Verifying That Both Approaches Agree

Whenever you have a closed form, it's good practice to verify it against the brute-force summation for small values. If they disagree anywhere, something is wrong. 

print("n | summation | closed_form | match?")
print("-" * 40)
for n in range(1, 11):
    s = summation(lambda k: k, 1, n)
    c = closed_form(n)
    print(f"{n:2} | {s:9} | {c:11} | {s == c}")

n | summation | closed_form | match?
----------------------------------------
 1 |         1 |           1 | True
 2 |         3 |           3 | True
 3 |         6 |           6 | True
 4 |        10 |          10 | True
 5 |        15 |          15 | True
 6 |        21 |          21 | True
 7 |        28 |          28 | True
 8 |        36 |          36 | True
 9 |        45 |          45 | True
10 |        55 |          55 | True

Every row matches. This kind of verification table is a simple but powerful habit — it catches mistakes in either the formula or the code before they cause problems later.

Going Further — Summing Other Expressions

Because our summation function accepts any func, it works for any expression you can write as a Python function. For example, the sum of squares:

$$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$$ 
# Brute-force version
sum_of_squares = summation(lambda k: k**2, 1, 5)
print(sum_of_squares)

# Closed form version
def closed_form_squares(n: int) -> int:
    """Closed form for the sum of squares from 1 to n."""
    return n * (n + 1) * (2 * n + 1) // 6

print(closed_form_squares(5))

55
55

Same result both ways. The closed form does it in one line of arithmetic; the summation function adds up \(1 + 4 + 9 + 16 + 25\) one at a time.

Why This Matters

Summations appear constantly in algorithm analysis. When you ask "how many steps does this loop take?", the answer is almost always a summation. Understanding how to compute them — and more importantly, how to replace a slow loop with a fast closed form — is one of the core skills in writing efficient code.

The general summation function we built here is also a useful debugging tool. Any time you derive a closed form mathematically, you can check it instantly against the brute-force version for small values before trusting it in production code.

If you want to strengthen your Python fundamentals for mathematical programming, you may also enjoy: Mastering Python Coding Practices: Learning from the Best.

Comments

Post a Comment