Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.1: Proof by Induction

( \newcommand{\kernel}{\mathrm{null}\,}\)

Inductive reasoning is the process of drawing conclusions after examining particular observations. This reasoning is very useful when studying number patterns. In many situations, inductive reasoning strongly suggests that the statement is valid, however, we have no way to present whether the statement is true or false, for example, Goldbach conjecture. But, in this class, we will deal with problems that are more accessible and we can often apply mathematical induction to prove our guess based on particular observations. For example, when we predict a nth term for a given sequence of numbers, mathematics induction is useful to prove the statement, as it involves positive integers.

Process of Proof by Induction

There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:

Let p(n),nn0,n,n0Z+ be a statement. We would show that p(n) is true for all possible values of n.

  1. Show that p(n) is true for the smallest possible value of n: In our case p(n0). AND
  2. For Regular Induction: Assume that the statement is true for n=k, for some integer kn0. Show that the statement is true for n = k + 1.

OR

For Strong Induction: Assume that the statement p(r) is true for all integers r, where n0rk for some kn0. Show that p(k+1) is true.

If these steps are completed and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of nn0.

We shall use the following template for proof by induction:

Template for proof by induction

In order to prove a mathematical statement involving integers, we may use the following template:

Suppose p(n),nn0,n,n0Z+ be a statement.

For regular Induction:

  • Base Case: We need to show that p(n) is true for the smallest possible value of n: In our case show that p(n0) is true.
  • Induction Hypothesis: Assume that the statement p(n) is true for any positive integer n=k, for s kn0.
  • Inductive Step: Show that the statement p(n) is true for n=k+1..

For strong Induction:

  • Base Case: Show that p(n) is true for the smallest possible value of n: In our case p(n0).
  • Induction Hypothesis: Assume that the statement p(n) is true for all integers r, where n0rk for some kn0.
  • Inductive Step: Show that the statement p(n) is true for n=k+1..

If these steps are completed and the statement holds, by mathematical induction, we can conclude that the statement is true for all values of nn0.

Template for proof by Induction  (1).jpg

Example 3.1.1

Prove for .

Solution

Let . Then is true since clearly . Thus the statement is true for .

Assume that is true for some .

We will show that .

Consider .

Since and , we have .

Thus the statement is true for all .

By induction, for all .◻

Exercise 3.1.1

Prove that n<2n for nN.

Answer

Hint: k+1<2k(1+1).

Example 3.1.2

Prove that 1+2+...+n=n(n+1)2,nZ.

Solution:

Base step: Choose n=1. Then L.H.S =1. and R.H.S =(1)(1+1)2=1

Induction Assumption: Assume that 1+2+...+k=k(k+1)2, for kZ.

We shall show that 1+2+...+k+(k+1)=(k+1)[(k+1)+1]2=(k+1)(k+2)2

Consider 1+2+...+k+(k+1)

=k(k+1)2+(k+1)

=(k+1)(k2+11)

=(k+1)(k+22)

=(k+1)(k+2)2.

Thus, by induction we have 1+2+...+n=n(n+1)2,nZ.

We will explore examples that are related to number patterns in the next section.


This page titled 3.1: Proof by Induction is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?