Method

Mathematical Induction

A proof by mathematical induction is a method used to prove statements that involve natural numbers. In a proof by mathematical induction, the first possible case is shown to be true. Next, the claim is assumed to be true for one arbitrary case. It is then shown that the claim remains true for the next possible case. For example, consider the following statement for the special series. 1+2+3 + ⋯ + n = n(n+1)/2 To prove this statement using mathematical induction, there are four steps to follow.

Show That the Statement Is True for n=1

The first step is to check whether the statement results in a true statement for n=1. When n=1, the left-hand side of the equation becomes 1. Substituting 1 for n into the right-hand side also gives 1. 1 = 1( 1+1)/2 ⇔ 1=1 ✓ Therefore, the statement is true for n=1.

Assume That the Statement Is True for Some Natural Number k

Assume that the statement is true for some natural number k. This assumption implies the following equation. 1+2+3+ ⋯+k = k(k+1)/2

Show That the Statement Is True for the Next Number k+1

To show that the statement is true for k+1, the equation written in the previous step will be manipulated using the Properties of Equality.

1+2+3+ ⋯+k = k(k+1)/2

AddEqn

LHS+( k+1)=RHS+( k+1)

1+2+3+ ⋯+k + ( k+1) = k(k+1)/2 + ( k+1)

▼

Simplify right-hand side

NumberToFrac

a = 2* a/2

1+2+3+ ⋯+k + (k+1)= k(k+1)/2 + 2(k+1)/2

AddFrac

Add fractions

1+2+3+ ⋯+k + (k+1)= k(k+1)+2(k+1)/2

FactorOut

Factor out (k+1)

1+2+3+ ⋯+k + (k+1)= (k+1)(k+2)/2

As it can be seen, the left-hand side is the sum of the first k+1 natural numbers, and the right-hand side is the expression obtained when substituting k+1 for n.

Draw Conclusion

Since the statement has been shown as true for n=1, n=k, and n=k+1, by the principle of mathematical induction, the statement holds true for all natural numbers n.

The assumption in the second step is called the induction hypothesis.

Recommended exercises