Mathematical Induction I: Proving Formulas

From one case to a general statement

Checking a few values can suggest a pattern, but does not by itself prove it for every integer. Mathematical induction gives a proof: we establish a starting case and show why the truth of any admissible case implies the truth of the next.

In this lesson we state the induction principle and give a complete proof of the formula for the sum of the first positive integers. This is one complete example from the induction topic; the other examples in the section are outside this lesson.

What P(n) means

$P(n)$ denotes a statement about an integer $n$ . Substituting a particular admissible integer gives a statement that can be true or false. The letter $P$ names the statement; it is not an extra factor.

Let $a$ be a fixed integer that marks the starting index. We want to establish $P(n)$ for every integer $n\ge a$ . In the step we use a different letter, $k$ , for an arbitrary integer $k\ge a$ ; it does not stand for a preselected numerical value.

Principle of mathematical induction

Let $P(n)$ be a statement defined for integers $n$ , and let $a$ be a fixed integer. If both conditions below hold, then $P(n)$ is true for every integer $n\ge a$ .

Base case: $P(a)$ is true.

Inductive step: for every integer $k\ge a$ , if $P(k)$ is true, then $P(k+1)$ is also true.

Both conditions are needed. The base supplies a starting point, and the general step reaches each successive case. A step without a starting point is not enough; checking several starting values without a general step is not enough either.

Here the principle is used as the foundation of the proof method. A formal derivation from other properties of the integers is outside this lesson.

Basis: What P(n) means

$P(n)$ denotes a statement about an integer $n$ . Substituting a particular admissible integer gives a statement that can be true or false. The letter $P$ names the statement; it is not an extra factor.

Let $a$ be a fixed integer that marks the starting index. We want to establish $P(n)$ for every integer $n\ge a$ . In the step we use a different letter, $k$ , for an arbitrary integer $k\ge a$ ; it does not stand for a preselected numerical value.

Go to this part of the lesson ↑

What the step allows us to assume

To prove the step, take an arbitrary integer $k\ge a$ and temporarily assume $P(k)$ . This is the induction hypothesis. Under that assumption we must derive $P(k+1)$ .

We do not assume the statement for all indices at once, and we do not assume $P(k+1)$ , which remains to be proved. We may write the next-case formula as a target, but may not use it as an established equality.

This is not circular reasoning: within the step we prove the conditional statement $P(k)\Rightarrow P(k+1)$ . A true base case and a proved general step together establish the result unconditionally for all admissible indices.

Basis: Principle of mathematical induction

Let $P(n)$ be a statement defined for integers $n$ , and let $a$ be a fixed integer. If both conditions below hold, then $P(n)$ is true for every integer $n\ge a$ .

Base case: $P(a)$ is true.

Inductive step: for every integer $k\ge a$ , if $P(k)$ is true, then $P(k+1)$ is also true.

Both conditions are needed. The base supplies a starting point, and the general step reaches each successive case. A step without a starting point is not enough; checking several starting values without a general step is not enough either.

Here the principle is used as the foundation of the proof method. A formal derivation from other properties of the integers is outside this lesson.

Go to this part of the lesson ↑

Separating the last term of a sum

In the notation below, $i$ is the summation index. For an integer $n\ge1$ , it runs through the values from $1$ to $n$ , including each $u_i$ once.

\sum_{i=1}^{n}u_i=u_1+u_2+\cdots+u_n.

For $n=1$ , the sum contains only $u_1$ . For an integer $k\ge1$ , moving from the sum through $k$ to the sum through $k+1$ adds exactly one new term:

\sum_{i=1}^{k+1}u_i=\left(\sum_{i=1}^{k}u_i\right)+u_{k+1}.

The parentheses contain the old sum. This is the part that the induction hypothesis can replace when it gives the value of that sum. The new term is outside that replacement.

Sum of the first n positive integers

For every integer $n\ge1$ ,

1+2+\cdots+n=\frac{n(n+1)}{2}.

We will prove this by induction. The complete proof follows below; references to supporting facts only clarify steps that are already explained.

1. The statement and starting index

Let $P(n)$ denote the following equality:

P(n):\quad \sum_{i=1}^{n}i=\frac{n(n+1)}{2}.

The terms being added are the indices themselves: $u_i=i$ . The required range starts at $n=1$ , so we use $a=1$ in the induction principle.

Basis: What P(n) means

$P(n)$ denotes a statement about an integer $n$ . Substituting a particular admissible integer gives a statement that can be true or false. The letter $P$ names the statement; it is not an extra factor.

Let $a$ be a fixed integer that marks the starting index. We want to establish $P(n)$ for every integer $n\ge a$ . In the step we use a different letter, $k$ , for an arbitrary integer $k\ge a$ ; it does not stand for a preselected numerical value.

Go to this part of the lesson ↑

Basis: Separating the last term of a sum

In the notation below, $i$ is the summation index. For an integer $n\ge1$ , it runs through the values from $1$ to $n$ , including each $u_i$ once.

\sum_{i=1}^{n}u_i=u_1+u_2+\cdots+u_n.

For $n=1$ , the sum contains only $u_1$ . For an integer $k\ge1$ , moving from the sum through $k$ to the sum through $k+1$ adds exactly one new term:

\sum_{i=1}^{k+1}u_i=\left(\sum_{i=1}^{k}u_i\right)+u_{k+1}.

The parentheses contain the old sum. This is the part that the induction hypothesis can replace when it gives the value of that sum. The new term is outside that replacement.

Go to this part of the lesson ↑

2. Base case: n = 1

For $n=1$ , the left-hand side has just one term, $1$ . The right-hand side is also $1$ :

\frac{1(1+1)}{2}=\frac{2}{2}=1.

The two sides agree, so $P(1)$ is true. The base case has been proved independently of the induction hypothesis.

Basis: Separating the last term of a sum

In the notation below, $i$ is the summation index. For an integer $n\ge1$ , it runs through the values from $1$ to $n$ , including each $u_i$ once.

\sum_{i=1}^{n}u_i=u_1+u_2+\cdots+u_n.

For $n=1$ , the sum contains only $u_1$ . For an integer $k\ge1$ , moving from the sum through $k$ to the sum through $k+1$ adds exactly one new term:

\sum_{i=1}^{k+1}u_i=\left(\sum_{i=1}^{k}u_i\right)+u_{k+1}.

The parentheses contain the old sum. This is the part that the induction hypothesis can replace when it gives the value of that sum. The new term is outside that replacement.

Go to this part of the lesson ↑

Basis: Principle of mathematical induction

Let $P(n)$ be a statement defined for integers $n$ , and let $a$ be a fixed integer. If both conditions below hold, then $P(n)$ is true for every integer $n\ge a$ .

Base case: $P(a)$ is true.

Inductive step: for every integer $k\ge a$ , if $P(k)$ is true, then $P(k+1)$ is also true.

Both conditions are needed. The base supplies a starting point, and the general step reaches each successive case. A step without a starting point is not enough; checking several starting values without a general step is not enough either.

Here the principle is used as the foundation of the proof method. A formal derivation from other properties of the integers is outside this lesson.

Go to this part of the lesson ↑

3. Hypothesis for an arbitrary k

Let $k\ge1$ be an arbitrary integer. Assume that $P(k)$ is true, that is,

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

This hypothesis concerns exactly the first $k$ terms. We must now obtain the formula for the first $k+1$ terms.

Basis: What the step allows us to assume

To prove the step, take an arbitrary integer $k\ge a$ and temporarily assume $P(k)$ . This is the induction hypothesis. Under that assumption we must derive $P(k+1)$ .

We do not assume the statement for all indices at once, and we do not assume $P(k+1)$ , which remains to be proved. We may write the next-case formula as a target, but may not use it as an established equality.

This is not circular reasoning: within the step we prove the conditional statement $P(k)\Rightarrow P(k+1)$ . A true base case and a proved general step together establish the result unconditionally for all admissible indices.

Go to this part of the lesson ↑

4. The next-case target

Substitute $k+1$ for every $n$ in the original formula. The right-hand side becomes $\frac{(k+1)((k+1)+1)}{2}$ , or $\frac{(k+1)(k+2)}{2}$ . Our target is therefore:

P(k+1):\quad \sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2}.

This states the target; it is not a new assumption. We will start by transforming its left-hand side.

Basis: What the step allows us to assume

To prove the step, take an arbitrary integer $k\ge a$ and temporarily assume $P(k)$ . This is the induction hypothesis. Under that assumption we must derive $P(k+1)$ .

We do not assume the statement for all indices at once, and we do not assume $P(k+1)$ , which remains to be proved. We may write the next-case formula as a target, but may not use it as an established equality.

This is not circular reasoning: within the step we prove the conditional statement $P(k)\Rightarrow P(k+1)$ . A true base case and a proved general step together establish the result unconditionally for all admissible indices.

Go to this part of the lesson ↑

5. Separate the new term

\sum_{i=1}^{k+1}i=\left(\sum_{i=1}^{k}i\right)+(k+1).

The sum through $k+1$ contains all the old terms from $1$ through $k$ , followed by the new last term $k+1$ . We have only regrouped the same finite sum; we have not used the next-case formula.

Basis: Separating the last term of a sum

In the notation below, $i$ is the summation index. For an integer $n\ge1$ , it runs through the values from $1$ to $n$ , including each $u_i$ once.

\sum_{i=1}^{n}u_i=u_1+u_2+\cdots+u_n.

For $n=1$ , the sum contains only $u_1$ . For an integer $k\ge1$ , moving from the sum through $k$ to the sum through $k+1$ adds exactly one new term:

\sum_{i=1}^{k+1}u_i=\left(\sum_{i=1}^{k}u_i\right)+u_{k+1}.

The parentheses contain the old sum. This is the part that the induction hypothesis can replace when it gives the value of that sum. The new term is outside that replacement.

Go to this part of the lesson ↑

6. Apply the hypothesis only to the old sum

\left(\sum_{i=1}^{k}i\right)+(k+1)=\frac{k(k+1)}{2}+(k+1).

By $P(k)$ , the parenthesized expression equals $\frac{k(k+1)}{2}$ . Equal quantities may replace one another within a sum. The new term $k+1$ remains unchanged; we do not replace the entire sum through $k+1$ by the formula we are still proving.

Basis: What the step allows us to assume

To prove the step, take an arbitrary integer $k\ge a$ and temporarily assume $P(k)$ . This is the induction hypothesis. Under that assumption we must derive $P(k+1)$ .

We do not assume the statement for all indices at once, and we do not assume $P(k+1)$ , which remains to be proved. We may write the next-case formula as a target, but may not use it as an established equality.

This is not circular reasoning: within the step we prove the conditional statement $P(k)\Rightarrow P(k+1)$ . A true base case and a proved general step together establish the result unconditionally for all admissible indices.

Go to this part of the lesson ↑

Basis: Hypothesis for an arbitrary k

Let $k\ge1$ be an arbitrary integer. Assume that $P(k)$ is true, that is,

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

This hypothesis concerns exactly the first $k$ terms. We must now obtain the formula for the first $k+1$ terms.

Go to this part of the lesson ↑

7. Use a common denominator

Write the second term with denominator $2$ . Multiplication by $\frac{2}{2}=1$ does not change its value:

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

Expand both numerators using the distributive law:

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

The denominators agree, so add the numerators and combine like terms: $k+2k=3k$ . This gives:

\frac{k^2+k}{2}+\frac{2k+2}{2}=\frac{k^2+3k+2}{2}.

8. Compare with the target right-hand side

The target contains $\frac{(k+1)(k+2)}{2}$ . Expand its numerator:

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

We transformed the left-hand side into $\frac{k^2+3k+2}{2}$ ; the right-hand side equals the same quantity. Hence the two sides are equal, and $P(k+1)$ follows under the hypothesis $P(k)$ . This completes the step.

Basis: The next-case target

Substitute $k+1$ for every $n$ in the original formula. The right-hand side becomes $\frac{(k+1)((k+1)+1)}{2}$ , or $\frac{(k+1)(k+2)}{2}$ . Our target is therefore:

P(k+1):\quad \sum_{i=1}^{k+1}i=\frac{(k+1)(k+2)}{2}.

This states the target; it is not a new assumption. We will start by transforming its left-hand side.

Go to this part of the lesson ↑

9. Conclusion by induction

We proved $P(1)$ . For an arbitrary integer $k\ge1$ , we also derived $P(k+1)$ from $P(k)$ , without assigning a special value to $k$ . Both conditions of the induction principle hold, so

\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\qquad(n\in\mathbb Z,\ n\ge1).

The hypothesis was used within the proof of the step. The final formula is established for every integer in the stated range, with no additional assumption.

Basis: Principle of mathematical induction

Let $P(n)$ be a statement defined for integers $n$ , and let $a$ be a fixed integer. If both conditions below hold, then $P(n)$ is true for every integer $n\ge a$ .

Base case: $P(a)$ is true.

Inductive step: for every integer $k\ge a$ , if $P(k)$ is true, then $P(k+1)$ is also true.

Both conditions are needed. The base supplies a starting point, and the general step reaches each successive case. A step without a starting point is not enough; checking several starting values without a general step is not enough either.

Here the principle is used as the foundation of the proof method. A formal derivation from other properties of the integers is outside this lesson.

Go to this part of the lesson ↑

Apply the method to another sum

The linked practice asks you either to order a proof for a different sum or to identify exactly what the hypothesis allows you to replace. Try it first. If you need a supporting fact, revisit the induction principle and the rule for separating the last term; the full exercise solution is opened by a separate action.

Mathematical induction: from the principle to a complete proof

From one case to a general statement

What P(n) means

Principle of mathematical induction

What the step allows us to assume

Separating the last term of a sum

Sum of the first n positive integers

1. The statement and starting index

2. Base case: n = 1

3. Hypothesis for an arbitrary k

4. The next-case target

5. Separate the new term

6. Apply the hypothesis only to the old sum

7. Use a common denominator

8. Compare with the target right-hand side

9. Conclusion by induction

Apply the method to another sum

Proof for a sum of even integers

Scope of the induction hypothesis