Formula for an arithmetic series (Part 5)

In Precalculus, Discrete Mathematics or Real Analysis, an arithmetic series is often used as a student’s first example of a proof by mathematical induction. Recall, from Wikipedia:

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.

The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): prove that the statement holds for the first natural number $n$ . Usually, $n=0$ or $n=1$ .

The inductive step: prove that, if the statement holds for some natural number $n$ , then the statement holds for $n+1$ .

The hypothesis in the inductive step that the statement holds for some $n$ is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for $n+1$ .

As an inference rule, mathematical induction can be justified as follows. Having proven the base case and the inductive step, then any value can be obtained by performing the inductive step repeatedly. It may be helpful to think of the domino effect. Consider a half line of dominoes each standing on end, and extending infinitely to the right. Suppose that:

The first domino falls right.

If a (fixed but arbitrary) domino falls right, then its next neighbor also falls right.

With these assumptions one can conclude (using mathematical induction) that all of the dominoes will fall right.

Mathematical induction… works because $n$ is used to represent an arbitrary natural number. Then, using the inductive hypothesis, i.e. that $P(n)$ is true, show $P(k+1)$ is also true. This allows us to “carry” the fact that $P(0)$ is true to the fact that $P(1)$ is also true, and carry $P(1)$ to $P(2)$ , etc., thus proving $P(n)$ holds for every natural number $n$ .

When students first encounter mathematical induction (in either Precalculus, Discrete Mathematics, or Real Analysis), the theorems that students are asked to prove usually fall into four categories:

Calculating a series (examples below).
Statements concerning divisibility (for example, proving that $4$ is always a factor of $5^n-1$ ).
Finding a closed-form expression for a recursively defined sequence (for example, if $a_1 = 4$ and $a_n = 3a_{n-1}$ if $n \ge 2$ , proving that $a_n = 4 \times 3^{n-1}$ 0
Statements concerning inequality (for example, proving that $n! > 4^n$ if $n \ge 9$ 0

Here’s a common first example of mathematical induction applied to an arithmetic series. Notice that the statement of the theorem matches the form $\displaystyle \frac{n}{2}(a_1 + a_n)$ seen earlier in this series (pardon the pun) of posts.

Theorem. $1 + 2 + \dots + (n-1) + n = \displaystyle \frac{n(n+1)}{2}$

Proof. Induction on $n$ .

$n = 1$ : The left-hand is simply $1$ , while the right-hand side is $\displaystyle \frac{(1)(2)}{2}$ , which is also equal to $1$ . So the base case works.

$n$ : Assume that the statement holds true for the integer $n$ .

$n+1$ . If I replace $n$ by $n+1$ in the statement of the theorem, then the right-hand side becomes

$\displaystyle \frac{(n+1)[(n+1)+1]}{2} = \displaystyle \frac{(n+1)(n+2)}{2}$

I find it helpful to describe this to students as my target. In other words, as I manipulate the left-hand side, my ultimate goal is to end up with this target. Once I have done that, then I have completed the proof.

If I replace $n$ by $n+1$ in the statement of the theorem, then the left-hand side will now end on $n+1$ instead of $n$ :

$1 + 2 + \dots + (n-1) + n + (n+1)$

Notice that we’ve seen almost all of this before, except for the extra term $n+1$ . So we will substitute using the induction hypothesis, carrying the extra $n+1$ along for the ride.

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{n(n+1)}{2} + (n+1)$

Now our task is, by hook or by crook, using whatever algebraic tricks we can think of to convert this last expression into the target. Most students are completely comfortable doing this, although they typically multiply out the term $n(n+1)$ unnecessarily. Indeed, many early proofs by induction are simplified by factoring out terms whenever possible — in the example below, $(n+1)$ is factored on the last step — as opposed to multiplying them out. In my experience, proofs by induction often serve as a stringent test of students’ algebra skills as opposed to their skills in abstract reasoning.

In any event, here’s the end of the proof:

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{n(n+1)}{2} + (n+1)$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{n(n+1) + 2(n+1)}{2}$

$1 + 2 + \dots + (n-1) + n + (n+1) = \displaystyle \frac{(n+1)(n + 2)}{2}$

Mathematical induction can be used to verify formulas for series which are not arithmetic, like

$1^2 + 2^2 + \dots + (n-1)^2 + n^2 = \displaystyle \frac{n(n+1)(2n+1)}{6}$

$1^3 + 2^3 + \dots + (n-1)^3 + n^3 = \displaystyle \frac{n^2(n+1)^2}{4}$

However, the downside of a proof by induction lies in the word verify, as it’s necessary to actually know what’s going to work before proceeding with the proof.

In the next post, I’ll describe a method of obtaining these series that does not require mathematical induction.

One thought on “Formula for an arithmetic series (Part 5)”

Pingback: Arithmetic and Geometric Series: Index | Mean Green Math

Formula for an arithmetic series (Part 5)

Published by John Quintanilla

One thought on “Formula for an arithmetic series (Part 5)”

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by John Quintanilla

One thought on “Formula for an arithmetic series (Part 5)”

Leave a Reply Cancel reply