Skip to content
Topos Uranos
English

Summations, progressions and induction

Summary

This lesson introduces summation notation and its properties (linearity, decomposition, shifting of the index and reversal of the order), and applies it to the computation of telescoping sums and of the sums of arithmetic and geometric progressions. It then studies strong induction and the well-ordering principle, proves that induction implies both, makes precise in what sense they are equivalent to it, and uses them to prove that every natural number greater than 11 is a product of primes.

Learning objectives

  1. Write and transform sums with summation notation, applying its properties of linearity, decomposition, shifting of the index and reversal of the order.
  2. Compute telescoping sums and use them to derive, and not merely verify, formulas for sums.
  3. Determine the general term and the sum of the first terms of an arithmetic or geometric progression, and apply them to solving problems.
  4. Prove statements by strong induction and by the well-ordering principle, derive both from the principle of induction, and explain with which additional facts well-ordering allows induction to be recovered.

Summation notation

In the lesson on the Peano axioms there appeared sums of many terms that follow a rule, such as 1+2+⋯+n1 + 2 + \cdots + n. The ellipsis leaves to the reader the task of guessing that rule; summation notation states it. If am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n are numbers, with m≤nm \leq n, one writes

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

and reads “the sum of aka_k for kk from mm to nn”. The letter kk is the index of the sum; mm and nn are its lower and upper limits, and aka_k is the general term. The sum has n−m+1n - m + 1 terms. The index is a dummy variable: the value of the sum does not depend on the letter used to name it, so that ∑k=1nk2\sum_{k=1}^{n} k^2 and ∑j=1nj2\sum_{j=1}^{n} j^2 are the same number. The index runs through natural numbers; the terms, by contrast, may be numbers of another kind. In this lesson there appear, besides natural numbers, integers with their negatives and fractions, which the next unit constructs: here they are anticipated, and only their elementary rules of calculation and of order are used (commutativity, associativity, distributivity, the rules of signs, subtraction and division by a nonzero number). The properties of summation that follow are proved with those rules, and therefore hold for terms of any of those kinds.

Like addition, multiplication and exponentiation in the lesson on the operations on natural numbers, summation admits a recursive definition that dispenses with the ellipsis: the sum of a single term is that term, and to add one more term one adds it to the previous result.

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

This definition starts at mm, whereas the recursion theorem, as it was stated, defines functions from 11 onwards. However, it suffices to shift the index: instead of the sum up to nn one defines the sum of the first qq terms starting from ama_m. With the initial value ama_m and the rule gq(x)=x+am+qg_q(x) = x + a_{m + q}, the recursion theorem gives a unique function FF from N\mathbb{N} to the numbers such that F(1)=amF(1) = a_m and F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} for every natural number qq. For n≥mn \geq m one then defines the sum up to nn as the value of FF at the number of its terms, n−m+1n - m + 1, which is a natural number because m<n+1m < n + 1:

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

With n=mn = m one obtains F(1)=amF(1) = a_m, and with q=n−m+1q = n - m + 1, since m+q=n+1m + q = n + 1, the equality F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} is exactly the second rule of the definition. Hence the recursive definition from mm determines a unique sum for each n≥mn \geq m, and if m=1m = 1 it coincides with the one that the recursion theorem gives directly, because then F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

With this notation, the formula proved by induction in the lesson on the Peano axioms, that of the sum of the first nn natural numbers, is written as follows:

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

The sum of the squares, ∑k=1nk2\sum_{k=1}^{n} k^2, is the next step, and this lesson will not confine itself to verifying it: the section on telescoping sums derives it without knowing it in advance.

Inductions on the upper limit of a sum start at the lower limit mm, which need not be 11. However, the principle of induction of the Peano axioms starts at 11; to start at another natural number, the following lemma is needed.

LemmaInduction from an arbitrary natural number

Let n0n_0 be a natural number. If a property holds for n0n_0 and, assuming that it holds for an arbitrary natural number k≥n0k \geq n_0, it also holds for k+1k + 1, then that property holds for all natural numbers n≥n0n \geq n_0. The idea is to renumber the natural numbers from n0n_0 onwards so as to return to the ordinary principle of induction. One uses the lemma from the lesson on the operations on natural numbers according to which every natural number different from 11 is a successor, and the monotonicity of addition. In the figure, n0=4n_0 = 4 and p=3p = 3: below each natural number from n0n_0 onwards appears its new number qq.

Proof

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    If n0=1n_0 = 1, this is the principle of induction. If not, n0=p+1n_0 = p + 1 for some natural number pp, and we consider the property QQ that asserts PP for p+qp + q.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    The property QQ holds for 11, because Q(1)Q(1) is P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    If Q(q)Q(q) holds, since 1≤q1 \leq q, by the monotonicity of addition we have p+q≥p+1=n0p + q \geq p + 1 = n_0, and the given step applies to k=p+qk = p + q: Q(q+1)Q(q + 1) holds.

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    By the principle of induction, Q(q)Q(q) holds for every qq. Every n≥n0n \geq n_0 is of the form p+qp + q: if n=n0n = n_0, with q=1q = 1, and if n=n0+ln = n_0 + l, with q=1+lq = 1 + l.

Properties of summation

From the recursive definition the following properties are derived, by induction on the upper limit; they hold for arbitrary terms aka_k and bkb_k and for any number cc:

  1. Linearity: ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k and ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. In particular, adding a constant nn times is multiplying it by nn: ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Decomposition: if m≤p<nm \leq p < n, then ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Shifting of the index: for every natural number pp, ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Reversal of the order: ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
TheoremProperties of summation

For arbitrary terms aka_k and bkb_k and for any number cc, summation is linear, splits into two consecutive sums, and admits shifting of the index and reversal of the order, as stated in the preceding list. Each property is proved by induction on the upper limit, which starts at the lower limit thanks to the preceding lemma. Only the recursive definition and the properties of addition and multiplication are used; reversal also relies on decomposition and on shifting.

Proof

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Linearity. For n=mn = m, both sides equal am+bma_m + b_m. If it holds for nn, one applies the recursive definition, the induction hypothesis, and the associativity and commutativity of addition. In the same way, with distributivity, one proves that ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k, and that ∑k=1nc=nc\sum_{k=1}^{n} c = nc, because nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Decomposition, with pp fixed, by induction on nn from p+1p + 1 onwards. For n=p+1n = p + 1 it is the recursive definition, because the sum of a single term is that term.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    If decomposition holds for nn, the term an+1a_{n + 1} is added to both sides and the recursive definition is applied to each sum.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Shifting. For n=mn = m, both sides equal ama_m. If it holds for nn, since the upper limit (n+p)+1(n + p) + 1 is (n+1)+p(n + 1) + p, one applies the recursive definition and the induction hypothesis.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Reversal, by induction on nn. For n=1n = 1, both sides equal a1a_1. If it holds for nn, the first term of the reversed sum of n+1n + 1 terms is split off by decomposition, and the index is shifted by one unit, with j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    By the induction hypothesis, the last sum equals ∑k=1nak\sum_{k=1}^{n} a_k; by commutativity and the recursive definition, one obtains reversal for n+1n + 1.

Linearity makes it possible to reduce a complicated sum to known sums. The last two properties are changes of variable: shifting substitutes k=j−pk = j - p and runs through the same terms with another numbering, and reversal substitutes k=n+1−jk = n + 1 - j and runs through them from the last to the first. However, summation does not behave in the same way with multiplication: the sum of the products is not the product of the sums. An example with two terms and ak=bk=ka_k = b_k = k suffices:

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
PropositionThe sum of the first odd numbers

Prove that the sum of the first nn odd numbers is n2n^2. Linearity reduces the sum to two others already known, with no need for a new induction.

Proof

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    The odd number in position kk is 2k−12k - 1: the first is 11, the second 33, and the one in position nn is 2n−12n - 1. The required sum is written as follows.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    By linearity, the sum splits into two: twice the sum of the kk, minus the sum of nn ones.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    The first sum is that of the first nn natural numbers, n(n+1)2\frac{n(n + 1)}{2}, and the factor 22 cancels its denominator; the second adds up, nn times, the number 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    We expand the product; the terms nn and −n-n cancel.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    The figure shows why: each odd number is the difference of two consecutive squares, the gnomon that turns the square of side k−1k - 1 into the square of side kk.