Induction and Sums

Why the Upper Limit Matters

In the previous tutorial, induction was used to prove inequalities by moving from one index to the next. For sums, that same move has a particularly direct meaning: the sum through $n+1$ consists of the sum through $n$, together with one new term. Recognizing that relationship is the main step in many inductive proofs involving finite sums.

A summation formula describes the value of a whole collection of terms using its endpoint. To prove such a formula, one verifies the first case and then checks that adding the next term changes the proposed expression by exactly the right amount. It is important to keep track of the index of that new term: when the upper limit changes from $n$ to $n+1$, the added term is the term with index $n+1$.

Definition (Finite sum). For integers $m\le n$, the notation $\sum_{k=m}^{n} a_k$ means the sum of the terms $a_m,a_{m+1},\ldots,a_n$. If the lower limit exceeds the upper limit, the sum is defined to be $0$. In particular, $\sum_{k=1}^{0} a_k=0$.

The letter $k$ is an index: it records which term is being added. The endpoint $n$, by contrast, determines how many terms are included. For example, $\sum_{k=1}^{3} k=1+2+3$, while $\sum_{k=0}^{3} k=0+1+2+3$. Changing the lower limit changes the terms in the sum, even when the upper limit stays fixed.

The empty-sum convention is useful in induction because it gives a natural value at an endpoint where there are no terms. When a formula starts at $n=0$ but sums from $k=1$, the base case is the empty sum. Other formulas start at $k=0$, in which case the sum at $n=0$ contains the single term with index $0$. The stated limits determine which base case applies.

The Basic Inductive Move for a Sum

For a sequence of terms $a_k$, the definition of a finite sum gives the endpoint relation

\sum_{k=m}^{n+1} a_k = \sum_{k=m}^{n} a_k+a_{n+1}, \qquad m\le n+1.

This identity is not a formula for the value of the sum; it is a way to split the final term from it. In an induction proof, the hypothesis usually gives a formula for the sum through $n$. The endpoint relation then adds $a_{n+1}$, and algebra should produce the proposed formula through $n+1$.

State the sum formula as $P(n)$.
Write down the exact index range and the claimed value of the sum.

Check the first index.
Evaluate the sum at the base case, respecting whether it is empty or has one or more terms.

Separate the new endpoint term.
Rewrite the sum through $n+1$ as the sum through $n$ plus the term with index $n+1$.

Substitute the inductive hypothesis.
Replace the sum through $n$ with its claimed expression, then simplify until the target at $n+1$ appears.

Conclude by induction.
Once the base case and inductive step are proved, invoke the Principle of Mathematical Induction.

The Sum of the First Positive Integers

A standard example is the sum of the positive integers up to $n$. The expression on the right is quadratic in $n$, even though each added term is linear in its index. The endpoint relation explains why the proposed expression has exactly the needed change from one index to the next.

Theorem (Sum of the First Positive Integers). For every $n\in\mathbb{N}_0$, $$ \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, $$ where the sum is empty and equals $0$ when $n=0$.

Proof. Let $P(n)$ be the displayed equality. At $n=0$, the left side is an empty sum and equals $0$, while the right side is $0(0+1)/2=0$. Thus $P(0)$ holds.

Now fix $n\in\mathbb{N}_0$ and assume $P(n)$, so that $\sum_{k=1}^{n}k=n(n+1)/2$. By adding the new endpoint term,

\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k+(n+1).

Apply the inductive hypothesis and simplify:

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

The last expression is the claimed formula with $n+1$ in place of $n$. Hence $P(n)$ implies $P(n+1)$. By the Principle of Mathematical Induction, the formula holds for every $n\in\mathbb{N}_0$. $\square$

Worked Example: Evaluating a Sum of Consecutive Integers

Evaluate $\sum_{k=1}^{18} k$. The theorem applies with $n=18$, so

\sum_{k=1}^{18} k = \frac{18(18+1)}{2} = \frac{18\cdot19}{2} = 9\cdot19 = 171.

The formula can be checked against the first few cases: at $n=1$, it gives $1(2)/2=1$; at $n=2$, it gives $2(3)/2=3=1+2$. These checks illustrate the formula, but the induction proof is what establishes it for every nonnegative integer.

A Geometric Sum

The same endpoint method applies when terms are powers rather than integers. For powers of $2$, adding the next term changes the sum by $2^{n+1}$. The formula below is proved independently by induction; its base case includes the term with index $0$.

Theorem (Finite Geometric Sum of Powers of Two). For every $n\in\mathbb{N}_0$, $$ \sum_{k=0}^{n}2^k=2^{n+1}-1. $$

Proof. At $n=0$, the left side is $2^0=1$, and the right side is $2^1-1=1$. Thus the base case holds. Suppose the formula is true for some $n\in\mathbb{N}_0$. By separating the new endpoint term and using the inductive hypothesis,

\sum_{k=0}^{n+1}2^k = \sum_{k=0}^{n}2^k+2^{n+1} = (2^{n+1}-1)+2^{n+1} = 2\cdot2^{n+1}-1 = 2^{n+2}-1.

This is the claimed formula at $n+1$. The base case and inductive step prove the result for every $n\in\mathbb{N}_0$. $\square$

Worked Example: A Geometric Sum Through a Fixed Endpoint

Evaluate $\sum_{k=0}^{7}2^k$. Substituting $n=7$ into the proved formula gives

\sum_{k=0}^{7}2^k = 2^{7+1}-1 = 2^8-1 = 256-1 = 255.

The indexing matters: this sum has eight terms, from $2^0$ through $2^7$. As a direct check, the terms are $1,2,4,8,16,32,64,128$, and their sum is $255$. The formula uses $n+1$ in the exponent because the last term has exponent $n$, while the total is one less than the next power.

A Sum of Squares

A more algebraically involved example is the sum of the squares of the first $n$ positive integers. The inductive step still has the same structure: add the new term $(n+1)^2$, then verify that the proposed expression changes by exactly that amount. The expansion should be shown explicitly; an unexplained simplification can conceal an indexing or algebra error.

Worked Example: Proving a Formula for the Sum of Squares

We prove for every $n\in\mathbb{N}_0$ that

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

At $n=0$, the sum is empty and equals $0$, and the right side is $0(1)(1)/6=0$. Assume the formula holds at an arbitrary $n\in\mathbb{N}_0$. The endpoint relation and the inductive hypothesis give

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

Factor out $n+1$ and combine the terms:

\frac{n(n+1)(2n+1)}{6}+(n+1)^2 = \frac{(n+1)\bigl(n(2n+1)+6(n+1)\bigr)}{6} = \frac{(n+1)(2n^2+7n+6)}{6}.

Since $2n^2+7n+6=(n+2)(2n+3)$, this becomes

\sum_{k=1}^{n+1}k^2 = \frac{(n+1)(n+2)(2n+3)}{6},

which is the proposed formula with $n+1$ substituted for $n$. Induction proves the formula for every $n\in\mathbb{N}_0$. For a numerical check, at $n=3$ the formula gives $3\cdot4\cdot7/6=14$, and the sum is $1^2+2^2+3^2=1+4+9=14$.

Telescoping Sums and an Indexing Pitfall

Not every sum is best handled by finding a closed formula through induction. Sometimes adjacent terms cancel after the summand is rewritten as a difference. The telescoping-sum theorem established earlier in this course says that if $a_k=b_{k+1}-b_k$, then summing from $k=m$ to $n$ leaves $b_{n+1}-b_m$. The following example applies that result directly.

Worked Example: A Telescoping Fraction Sum

For an integer $n\ge1$, evaluate $\sum_{k=1}^{n}\frac{1}{k(k+1)}$. For each $k\ge1$,

\frac{1}{k}-\frac{1}{k+1} = \frac{k+1-k}{k(k+1)} = \frac{1}{k(k+1)}.

Thus the summand has the form $b_{k+1}-b_k$ with $b_k=-1/k$, or equivalently the sum can be written as $\sum_{k=1}^{n}(1/k-1/(k+1))$. The terms cancel consecutively:

\sum_{k=1}^{n}\frac{1}{k(k+1)} = \left(1-\frac12\right) +\left(\frac12-\frac13\right) +\cdots +\left(\frac1n-\frac{1}{n+1}\right) = 1-\frac{1}{n+1} = \frac{n}{n+1}.

For example, at $n=3$ the original sum is $1/2+1/6+1/12=6/12+2/12+1/12=9/12=3/4$, which agrees with $n/(n+1)=3/4$. This check also makes clear why the final surviving denominator is $n+1$, not $n$.

The examples use two complementary techniques. Induction is useful when a proposed expression for a sum can be updated by adding one endpoint term. Telescoping is useful when the summand is a difference whose intermediate terms cancel. In either approach, the limits should be read carefully: a shifted endpoint changes which terms appear, and an omitted or extra endpoint changes the value.

Key takeaway. When the upper limit increases from $n$ to $n+1$, the sum gains precisely the term with index $n+1$. In an inductive proof, add that term to the formula at $n$ and simplify until the claimed expression at $n+1$ is obtained. Check the base case against the actual limits, including the empty-sum convention.

Check Your Understanding

Use the endpoint relation and the examples above to answer the following questions.

What term is added when a sum with upper limit $n$ is changed to one with upper limit $n+1$?
Why is $\sum_{k=1}^{0}k$ equal to $0$, while $\sum_{k=0}^{0}2^k$ equals $1$?
In the induction proof for $\sum_{k=0}^{n}2^k$, where does the exponent $n+2$ come from in the next case?
What algebraic identity allows the sum-of-squares induction step to factor into $(n+2)(2n+3)$?
Rewrite $1/(k(k+1))$ as a difference of two fractions, and state the value of the resulting sum from $k=1$ to $n$.

What You'll Learn