Developing results: from special cases to theorems

A conjecture backed by a million cases is still only a conjecture. This lesson is about the step from evidence to proof, and from one proof to a body of results. Mathematicians rarely prove a theorem in one stroke. They prove special cases, notice which features of the special cases mattered, extract a lemma, find that the lemma proves more than they wanted, and eventually arrive at a theorem whose statement and proof look inevitable, even though the route to them was anything but. We follow this process through two examples: Amara's consecutive sums, and the circle regions from lesson 5.

Start with the easiest special case

Faced with the conjecture that \(r(n)\) equals the number of odd divisors of \(n\), Amara did not attack it head on. She first asked for the simplest statement she was sure was true: \(n\) has a representation with two or more terms exactly when \(n\) is not a power of 2. This is the case \(r(n) = 1\) of the conjecture, and it has the advantage that both directions can be handled separately.

Theorem 1. A positive integer \(n\) is a sum of two or more consecutive positive integers if and only if \(n\) is not a power of 2.

Proof. Suppose \(n = a + (a + 1) + \cdots + (a + k - 1)\) with \(k \ge 2\) and \(a \ge 1\). Then \(2n = k(2a + k - 1)\). The two factors have opposite parity, since their difference \(2a - 1\) is odd, and both exceed 1: \(k \ge 2\) and \(2a + k - 1 \ge k + 1 \ge 3\). So the odd one is an odd divisor of \(2n\) greater than 1, hence an odd divisor of \(n\) greater than 1, and \(n\) is not a power of 2.

Conversely, suppose \(n\) is not a power of 2, so \(n = 2^e d\) with \(d \ge 3\) odd. If \(d \le 2^{e+1}\), take \(k = d\) terms centered at \(n/d = 2^e\): the terms \(2^e - \frac{d - 1}{2}, \ldots, 2^e + \frac{d - 1}{2}\) are consecutive integers summing to \(d \cdot 2^e = n\), and the smallest is positive because \(\frac{d - 1}{2} < 2^e\). If \(d > 2^{e+1}\), take \(k = 2^{e+1}\) terms forming \(2^e\) pairs straddling \(d/2\): the terms \(\frac{d + 1}{2} - 2^e, \ldots, \frac{d - 1}{2} + 2^e\) number \(2^{e+1}\), pair up as \((\frac{d+1}{2} - j) + (\frac{d-1}{2} + j) = d\) for \(j = 1, \ldots, 2^e\), and so sum to \(2^e d = n\); the smallest is positive because \(d > 2^{e+1}\). In both cases \(k \ge 2\). \(\blacksquare\)

Look back at this proof. The first half used only the parity of the factorization. The second half constructed representations from an odd divisor \(d\), in two cases according to the size of \(d\) relative to \(2n/d = 2^{e+1}\). Nothing in the construction required \(d\) to be the whole odd part of \(n\): any odd divisor \(d\) of \(n\) works the same way, with \(n/d\) in place of \(2^e\). That observation is the bridge to the full theorem. A proof of a special case has told us how to prove the general case, which is the most common way that special cases help.

The general theorem

Theorem 2. For every positive integer \(n\), the number \(r(n)\) of representations of \(n\) as a sum of one or more consecutive positive integers equals the number of odd divisors of \(n\).

Proof. Let \(\mathcal{R}\) be the set of representations and \(\mathcal{D}\) the set of odd divisors of \(n\). Define \(\Phi : \mathcal{R} \to \mathcal{D}\) as follows. A representation with \(k\) terms starting at \(a\) satisfies \(2n = k m\) with \(m = 2a + k - 1\); exactly one of \(k, m\) is odd, and we let \(\Phi\) send the representation to that odd factor. It divides \(2n\) and is odd, so it divides \(n\).

Define \(\Psi : \mathcal{D} \to \mathcal{R}\). Given an odd divisor \(d\), let \(e = 2n/d\), which is even, and let \(\{k, m\} = \{d, e\}\) with \(k < m\) (they differ since one is odd and one even). Put \(a = (m - k + 1)/2\). Since \(m - k\) is odd and positive, \(a\) is a positive integer, and \(k(2a + k - 1) = km = 2n\), so the \(k\) consecutive integers from \(a\) sum to \(n\). Let \(\Psi(d)\) be this representation.

These maps are inverse to each other. Starting from a representation with parameters \((k, a)\), the factors \(k\) and \(m = 2a + k - 1\) satisfy \(k < m\) because \(a \ge 1\); \(\Phi\) picks the odd one, \(d\), and \(\Psi(d)\) recovers the pair \(\{k, m\}\), orders it to get the same \(k < m\) and the same \(a\). Starting from \(d\), \(\Psi(d)\) has factors \(\{k, m\} = \{d, 2n/d\}\), and \(\Phi\) picks the odd one, which is \(d\). So \(\Phi\) is a bijection and \(|\mathcal{R}| = |\mathcal{D}|\). \(\blacksquare\)

The bijection is explicit, so it does more than count. It tells us the number of terms in the representation attached to \(d\): it is \(d\) if \(d < 2n/d\), that is \(d^2 < 2n\), and \(2n/d\) otherwise. That immediately yields a refinement, which was the sharper conjecture in practice problem 3 of lesson 5.

Corollary 3. The number of representations of \(n\) with an odd number of terms equals the number of odd divisors \(d\) of \(n\) with \(d^2 < 2n\), and the number with an even number of terms equals the number with \(d^2 > 2n\).

Corollary 4 (the length spectrum). The integer \(n\) has a representation with exactly \(k\) terms if and only if either \(k\) is odd, \(k \mid n\) and \(k^2 < 2n\), or \(k\) is even, \(2n/k\) is an odd integer, and \(k^2 < 2n\).

Proof. In both cases the representation is \(\Psi(d)\) for the appropriate \(d\): for odd \(k\), \(d = k\) with \(k < 2n/k\); for even \(k\), \(d = 2n/k\) with \(k < d\). The condition \(k < 2n/k\) is \(k^2 < 2n\). \(\blacksquare\)

Corollary 4 is essentially what Pong calls the length spectrum. Observe that the condition \(k^2 < 2n\) is not the same inequality as the search bound \(k(k + 1) \le 2n\) used in lesson 1: for \(n = 5\) and \(k = 3\) the first holds and the second fails. Combined with the divisibility conditions, however, they select exactly the same lengths, because both express that the starting term is positive. For odd \(k\) dividing \(n\), write \(n = km\); then \(k < 2m\) means \(k \le 2m - 1\), and since \(k\) is odd this is \(k + 1 \le 2m\), that is \(k(k + 1) \le 2n\). A careful thesis notices such near-coincidences and states which form of the condition it uses and why.

Generalizing: allowing zero and negative terms

Once a theorem is proved, ask what happens when a hypothesis is changed. What if the consecutive integers may be zero or negative? Then \(5 = 2 + 3 = 5 = -1 + 0 + 1 + 2 + 3 = -4 - 3 - \cdots + 4 + 5\), and representations come in pairs. This is the observation T. E. Mason published in 1912.

Theorem 5. The number of ways to write \(n \ge 1\) as a sum of one or more consecutive integers, positive, zero or negative, is twice the number of odd divisors of \(n\).

Proof. A sum of consecutive integers from \(a\) to \(b\) with \(b \ge a\) and positive total must have \(b \ge 1\). If \(a \ge 1\) it is one of the \(r(n)\) positive representations. If \(a \le 0\), the terms \(a, a + 1, \ldots, -a\) sum to zero (they are \(-|a|, \ldots, |a|\)), and they are all present because the total is positive forces \(b > -a\). Removing them leaves the positive representation from \(1 - a\) to \(b\). Conversely, any positive representation from \(c \ge 1\) to \(b\) extends uniquely to the representation from \(1 - c\) to \(b\), with \(1 - c \le 0\). So the representations with \(a \le 0\) are in bijection with the positive ones, and the total is \(2r(n)\), which is twice the number of odd divisors by Theorem 2. \(\blacksquare\)

This generalization is easy once Theorem 2 is known, but notice what it shows: the factor 2 that appears when we count factorizations \(2n = km\) of opposite parity without the condition \(k < m\) has a combinatorial meaning. The unordered pairs \(\{k, m\}\) correspond to positive representations; ordered pairs correspond to representations over all integers.

The circle regions, proved

Return to the regions formed by chords joining \(n\) points on a circle in general position. The experimental count in lesson 5 used the claim that every chord and every crossing adds one region. Here is a proof of the formula by Euler's formula for planar graphs, which states that a connected plane graph with \(V\) vertices, \(E\) edges and \(F\) faces, including the unbounded face, satisfies \(V - E + F = 2\).

Theorem 6. Chords joining \(n \ge 1\) points on a circle, no three of which meet at an interior point, divide the disc into \(\binom{n}{4} + \binom{n}{2} + 1\) regions.

Proof. For \(n \le 1\) there is one region and the formula holds, so let \(n \ge 2\). Form a plane graph whose vertices are the \(n\) points and the interior crossing points. Every crossing is determined by a set of four of the points, since two chords cross inside the disc exactly when their four endpoints alternate around the circle, and each set of four points contributes exactly one crossing, between the two diagonals of the quadrilateral it spans. By general position distinct sets give distinct crossings. So \(V = n + \binom{n}{4}\).

Each chord is crossed by the chords whose endpoints separate its endpoints; summed over all chords, the number of crossings on chords counts each crossing twice, so the total is \(2\binom{n}{4}\). A chord crossed \(c\) times is divided into \(c + 1\) edges, so the chords contribute \(\binom{n}{2} + 2\binom{n}{4}\) edges. The circle itself is divided by the \(n\) points into \(n\) arcs. Thus \(E = n + \binom{n}{2} + 2\binom{n}{4}\). The graph is connected because the circle is. By Euler's formula,

One of these faces is the unbounded region outside the circle, so the disc contains \(\binom{n}{4} + \binom{n}{2} + 1\) regions. \(\blacksquare\)

The proof explains the false pattern too. By the identity \(\sum_{j=0}^{4}\binom{n-1}{j} = \binom{n}{4} + \binom{n}{2} + 1\), which follows from Pascal's rule, the region count is the sum of the first five entries of row \(n - 1\) of Pascal's triangle. For \(n - 1 \le 4\) that is the entire row, which sums to \(2^{n-1}\); from \(n = 6\) the row has more than five entries and the count falls short of the power of two. The coincidence of the first five values is fully explained, which is the best possible outcome of looking back.

The hypothesis of general position matters. For six equally spaced points, the three long diagonals of the regular hexagon meet at the center, so three crossings merge into one, and the disc is divided into 30 regions rather than 31. A thesis should include such an example to show the reader why the hypothesis is there.

Checking the theorems by computation

Proved theorems still deserve computational checks, because the statement in the thesis may differ subtly from the statement proved, and because checks catch errors in indices and boundary cases. The program below verifies Theorems 2 and 5 and Corollaries 3 and 4 for all \(n \le 3000\), and checks the identity relating the region formula to Pascal's triangle.

from math import comb

def reps_positive(n):
    """list of (k, a): k consecutive positive integers from a summing to n"""
    out, k = [], 1
    while k * (k + 1) // 2 <= n:
        rest = n - k * (k - 1) // 2
        if rest % k == 0:
            out.append((k, rest // k))
        k += 1
    return out

def reps_all_integers(n):
    """pairs (a, b), a <= b integers with a + ... + b = n"""
    out = []
    for a in range(-n, n + 1):
        s = 0
        for b in range(a, n + 1):
            s += b
            if s == n:
                out.append((a, b))
            if s > n and b > 0:
                break
    return out

def odd_divisors(n):
    return [d for d in range(1, n + 1, 2) if n % d == 0]

ok = True
for n in range(1, 3001):
    R, D = reps_positive(n), odd_divisors(n)
    ok &= len(R) == len(D)                                             # Theorem 2
    ok &= sum(1 for k, a in R if k % 2) == sum(1 for d in D if d * d < 2 * n)   # Corollary 3
    lengths = {k for k, a in R}
    predicted = {k for k in range(1, 2 * n) if k * k < 2 * n and
                 ((k % 2 == 1 and n % k == 0) or (k % 2 == 0 and (2 * n) % k == 0 and (2 * n // k) % 2 == 1))}
    ok &= lengths == predicted                                          # Corollary 4
    if n <= 300:
        ok &= len(reps_all_integers(n)) == 2 * len(D)                   # Theorem 5
print("Theorems 2, 5 and Corollaries 3, 4 hold in the tested range:", ok)

print(all(sum(comb(n - 1, j) for j in range(5)) == comb(n, 4) + comb(n, 2) + 1 for n in range(1, 200)),
      "- region formula equals the sum of the first five entries of row n - 1")
print([comb(n, 4) + comb(n, 2) + 1 for n in range(1, 11)])

Theorems 2, 5 and Corollaries 3, 4 hold in the tested range: True
True - region formula equals the sum of the first five entries of row n - 1
[1, 2, 4, 8, 16, 31, 57, 99, 163, 256]

What makes a result worth stating

In a thesis, results are labeled by importance. A theorem is a main result. A proposition is a result of independent interest but less central. A lemma is a stepping stone used to prove other results; some lemmas, such as Zorn's lemma or Burnside's lemma, become famous in their own right. A corollary follows quickly from a theorem. Use these labels consistently: a reader skimming the thesis should be able to find the main results by looking for the word theorem.

Deciding how to package results is itself part of developing them. Amara's main result is Theorem 2, but its statement alone is classical. The thesis becomes hers through the arrangement: Theorem 1 as a warm-up whose proof suggests the general one; Theorem 2 with an explicit bijection; Corollaries 3 and 4 extracted from that bijection; Theorem 5 as a generalization explaining a factor of 2; and, in later chapters, her own variations. A clear progression of results, each motivated by the previous one, is what examiners mean when they praise a thesis for its understanding.

When the proof will not come

Sometimes the special cases are proved and the general case resists. Strategies then include: proving the result under an extra hypothesis and stating it as such; proving a weaker conclusion, such as an inequality instead of an equality; changing the method, for instance from a bijective proof to a generating-function proof; asking whether the statement is actually true by searching harder for counterexamples; and, finally, presenting it honestly as a conjecture supported by evidence, with partial results. A thesis that clearly separates what is proved from what is conjectured is far stronger than one that blurs the line.