Visualizing Summations from Concrete Mathematics

on

Visualizing Summations from Concrete Mathematics

Mathematical formulas are often much easier to understand when you can see them. A table of numbers tells you the values; a graph tells you the shape — whether something is growing slowly, quickly, linearly, or curving upward like a parabola. This post takes the summation formulas from Concrete Mathematics and brings them to life in Python, step by step.

The Summation We Are Visualizing

We will focus on the sum of the first \(n\) positive integers:

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

The right-hand side is the closed form — a direct formula that gives the answer without looping. For \(n = 10\): \(\frac{10 \times 11}{2} = 55\). Let's verify that with a table before writing any plotting code:

\(n\) Running total Closed form \(\frac{n(n+1)}{2}\) Match
111✓
233✓
366✓
41010✓
51515✓
62121✓
72828✓
83636✓
94545✓
105555✓

Computing Partial Sums with accumulate

A partial sum is the running total after adding each new term. The sequence of partial sums for \(\sum_{k=1}^{n} k\) is \(1, 3, 6, 10, 15, \ldots\) — each entry is the previous entry plus the next integer.

Python's itertools.accumulate does exactly this — it takes a sequence and produces the running totals one step at a time: 

from itertools import accumulate

def partial_sums(n: int) -> list[int]:
    return list(accumulate(range(1, n + 1)))

Let's unpack every piece:

range(1, n + 1) — produces the integers \(1, 2, 3, \ldots, n\). The n + 1 is needed because Python's range(a, b) excludes \(b\) itself.

accumulate(...) — takes the sequence and produces running totals. Given \([1, 2, 3, 4, 5]\), it produces \([1, 3, 6, 10, 15]\):

Input value added Running total after this step
11
2\(1 + 2 = 3\)
3\(3 + 3 = 6\)
4\(6 + 4 = 10\)
5\(10 + 5 = 15\)

list(...) — accumulate is a lazy iterator that produces values one at a time only when asked. Wrapping it in list() forces everything to be computed immediately and stored in a list we can reuse. 

print(partial_sums(10))
# [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

A Quick Introduction to Matplotlib

Matplotlib is the most widely used Python library for creating graphs and charts. Before looking at the plotting code, it helps to understand its two core objects, because they appear in every matplotlib program:

Object What it is Analogy
fig (Figure) The entire image — the outer container for everything A blank sheet of paper
ax (Axes) The actual chart area — axes, grid, plotted lines, labels The graph drawn on that paper

The line fig, ax = plt.subplots(figsize=(8, 5)) creates both at once. figsize=(8, 5) sets the image size to 8 inches wide by 5 inches tall — you can change those numbers to make it larger or smaller. Once you have ax, all drawing commands go through it:

Command What it does
ax.plot(x, y)Draws a line connecting the (x, y) data points
ax.set_title(...)Adds a title above the chart
ax.set_xlabel(...)Labels the horizontal axis
ax.set_ylabel(...)Labels the vertical axis
ax.legend()Shows the key explaining what each line is
ax.grid(True)Adds a background grid for easier reading
plt.tight_layout()Prevents labels from being cut off at the edges
plt.show()Renders and displays the finished graph

Plotting the Partial Sums

import matplotlib.pyplot as plt
from itertools import accumulate

n = 50
x      = list(range(1, n + 1))               # [1, 2, ..., 50]
y      = list(accumulate(range(1, n + 1)))    # partial sums
closed = [k * (k + 1) // 2 for k in x]       # closed form n(n+1)/2 at each n

fig, ax = plt.subplots(figsize=(8, 5))

ax.plot(x, y,      label="Partial sums",  linewidth=2)
ax.plot(x, closed, label="Closed form",   linewidth=1.5, linestyle="--")

ax.set_title("Growth of the Summation sum k from 1 to n")
ax.set_xlabel("n")
ax.set_ylabel("Sum")
ax.legend()
ax.grid(True)

plt.tight_layout()
plt.show()

Here is what the code produces. The solid line (partial sums computed step by step) and the dashed line (closed form \(\frac{n(n+1)}{2}\)) lie exactly on top of each other — confirming both approaches give identical results:

Graph showing the partial sums of k from 1 to 50. Both the step-by-step partial sums and the closed form curve upward together in a parabola shape.

Why the Curve Is Quadratic

The curve bends upward like a parabola rather than rising in a straight line. This is because the closed form \(\frac{n(n+1)}{2} \approx \frac{n^2}{2}\) for large \(n\) — it grows proportionally to \(n^2\), which is the definition of quadratic growth.

We can confirm this numerically by checking the ratio of the sum to \(n^2\). If the sum truly grows like \(\frac{n^2}{2}\), then \(\frac{\text{sum}}{n^2}\) should approach \(0.5\) as \(n\) gets large:

\(n\) \(\frac{n(n+1)}{2}\) \(n^2\) Ratio \(\frac{\text{sum}}{n^2}\)
515250.600
10551000.550
202104000.525
50127525000.510
1005050100000.505

The ratio converges toward \(0.5\) as \(n\) grows, confirming that the sum grows at exactly half the rate of \(n^2\) — in other words, \(\Theta(n^2)\) in Big-O notation.

Comparing Multiple Summations

The real payoff of visualization is comparing different summations side by side to see how their growth rates differ. Let's plot three at once:

Summation Closed form Growth rate
\(\sum_{k=1}^{n} 1\) \(n\) Linear — \(\Theta(n)\)
\(\sum_{k=1}^{n} k\) \(\frac{n(n+1)}{2}\) Quadratic — \(\Theta(n^2)\)
\(\sum_{k=1}^{n} k^2\) \(\frac{n(n+1)(2n+1)}{6}\) Cubic — \(\Theta(n^3)\) 
from itertools import accumulate
import matplotlib.pyplot as plt

n = 50
x = list(range(1, n + 1))

sum_ones  = list(accumulate(1    for k in x))  # adds 1 each step — grows linearly
sum_k     = list(accumulate(k    for k in x))  # adds k each step — grows quadratically
sum_k_sq  = list(accumulate(k**2 for k in x))  # adds k squared each step — grows cubically

fig, ax = plt.subplots(figsize=(8, 5))

ax.plot(x, sum_ones,  label="sum 1  — linear",    linewidth=2)
ax.plot(x, sum_k,     label="sum k  — quadratic",  linewidth=2)
ax.plot(x, sum_k_sq,  label="sum k squared — cubic", linewidth=2)

ax.set_title("Comparing Growth Rates of Three Summations")
ax.set_xlabel("n")
ax.set_ylabel("Cumulative sum")
ax.legend()
ax.grid(True)

plt.tight_layout()
plt.show()
Graph comparing three summations over n from 1 to 50. The linear sum rises gently, the quadratic curves upward, and the cubic climbs steeply away from the others.

The three curves pull apart dramatically as \(n\) grows. The linear sum rises gently, the quadratic bends upward, and the cubic climbs steeply. Seeing this visually makes the difference between \(O(n)\), \(O(n^2)\), and \(O(n^3)\) algorithms immediately tangible — what looks like a small difference in the formula has a large practical impact on performance.

If you enjoy practical Python exploration, you may also like: Python Requests vs urllib.

Comments

Post a Comment