Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.6: Mathematical Induction - An Introduction

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

Mathematical induction can be used to prove that an identity is valid for all integers n1. Here is a typical example of such an identity: 1+2+3++n=n(n+1)2. More generally, we can use mathematical induction to prove that a propositional function P(n) is true for all integers na.

Principal of Mathematical Induction (PMI)

Given a propositional function P(n) defined for integers n, and a fixed integer a.

Then, if these two conditions are true

  1. P(a) is true.
  2. if P(k) is true for some integer ka, then P(k+1) is also true.

then the  P(n) is true for all integers na.

Outline for Mathematical Induction

To show that a propositional function P(n) is true for all integers na, follow these steps:

  • Base Step: Verify that P(a) is true.
  • Inductive Step: Show that if P(k) is true for some integer ka, then P(k+1) is also true.
    • Assume P(n) is true for an arbitrary integer, k with  ka.  This is the inductive hypothesis.
    • With this assumption (the inductive hypothesis), show P(k+1) is true.
  • Conclude, by the Principle of Mathematical Induction (PMI) that P(n) is true for all integers na.

The base step is also called the basis step or the anchor step or the initial step

The base step and the inductive step, together, prove that P(a)P(a+1)P(a+2). Therefore, P(n) is true for all integers na. Compare induction to falling dominoes. When the first domino falls, it knocks down the next domino. The second domino in turn knocks down the third domino. Eventually, all the dominoes will be knocked down. But it will not happen unless these conditions are met:

  • The first domino must fall to start the motion. If it does not fall, no chain reaction will occur. This is the base step.
  • The distance between adjacent dominoes must be set up correctly. Otherwise, a certain domino may fall down without knocking over the next. Then the chain reaction will stop, and will never be completed. Maintaining the right inter-domino distance ensures that P(k)P(k+1) for each integer ka.

To prove the implication P(k)P(k+1) in the inductive step, we need to carry out two steps: assuming that P(k) is true, then using it to prove P(k+1) is also true. So we can refine an induction proof into a 3-step procedure:

  • Verify that P(a) is true.
  • Assume that P(k) is true for some integer ka.
  • Show that P(k+1) is also true.

The second step, the assumption that P(k) is true, is referred to as the inductive hypothesis. This is how a mathematical induction proof may look:

The idea behind mathematical induction is rather simple. However, it must be delivered with precision.

  • Be sure to say “Assume P(n) holds for some integer ka.” Do not say “Assume it holds for all integers ka.” If we already know the result holds for all ka, then there is no need to prove anything at all.
  • Be sure to specify the requirement ka. This ensures that the chain reaction of the falling dominoes starts with the first one.
  • Do not say “let n=k” or “let n=k+1.” The point is, you are not assigning the value of k and k+1 to n. Rather, you are assuming that the statement is true when n equals k, and using it to show that the statement also holds when n equals k+1.

Some proofs by induction 

1+2+3++n

Example 3.6.1

Use mathematical induction to show proposition P(n):  1+2+3++n=n(n+1)2 for all integers n1.

Proof

Base Step:  consider n = 1

On the Left-Hand Side (LHS) we get 1.  On the Right-Hand Side ( RHS) we get 1(1+1)2=22=1.  Thus P(n) is true for n=1.

Inductive step: Assume P(n) is true for n=k,k1.  In other words, P(k) is true so our inductive hypothesis is 1+2+3++k=k(k+1)2.   

Consider the left-hand side of P(k+1).  1+2+3++(k+1)=1+2++k+(k+1),

we can regroup this as

1+2+3++(k+1)=[1+2++k]+(k+1),

so that 1+2++k can be replaced by k(k+1)2, by the inductive hypothesis.

Using the inductive hypothesis, we find

1+2+3++(k+1)=1+2+3++k+(k+1)=k(k+1)2+(k+1)=(k+1)(k2+1)=(k+1)k+22=(k+1)(k+2)2.

Therefore, the identity also holds when n=k+1.

Thus, by the Principle of Mathematical Induction (PMI), 1+2+3++n=n(n+1)2 for all integers n1.

We can use the summation notation (also called the sigma notation) to abbreviate a sum. For example, the sum in the last example can be written as

ni=1i.

The letter i is the index of summation. By putting i=1 under and n above, we declare that the sum starts with i=1, and ranges through i=2, i=3, and so on, until i=n. The quantity that follows describes the pattern of the terms that we are adding in the summation. Accordingly,

10i=1i2=12+22+32++102.

In general, the sum of the first n terms in a sequence {a1,a2,a3,} is denoted ni=1ai. Observe that

k+1i=1ai=(ki=1ai)+ak+1,

which provides the link between P(k+1) and P(k) in an induction proof.

 

ni=1i2

Example 3.6.2

Use mathematical induction to show that, for all integers n1, ni=1i2=12+22+32++n2=n(n+1)(2n+1)6.

Proof

Base Step: When n=1, the left-hand side reduces to 12=1, and the right-hand side becomes 1236=1; hence, the identity holds when n=1.
Inductive Step: Assume it holds when n=k for some integer k1; that is, assume for some integer k1 that ki=1i2=k(k+1)(2k+1)6 .
Consider n=k+1.  k+1i=1i2=12+22+32++k2+(k+1)2. From the inductive hypothesis, we find k+1i=1i2=ki=1i2+(k+1)2
=k(k+1)(2k+1)6+(k+1)2 
=k(k+1)(2k+1)+6(k+1)26
(k+1)[k(2k+1)+6(k+1)]6
(k+1)(2k2+7k+6)6
(k+1)(k+2)(2k+3)6
(k+1)(k+2)(2(k+1)+1)6.
Therefore, the identity also holds when n=k+1
Thus, by PMI for all integers n1, ni=1i2=12+22+32++n2=n(n+1)(2n+1)6.

hands-on exercise 3.6.1

It is time for you to write your own induction proof. Prove that 12+23+34++n(n+1)=n(n+1)(n+2)3 for all integers n1.

hands-on exercise 3.6.2

Use induction to prove that, for all positive integers n, 123+234++n(n+1)(n+2)=n(n+1)(n+2)(n+3)4.

hands-on exercise 3.6.3

Use induction to prove that, for all positive integers n, 1+41+42++4n=4n+113.

All three steps in an induction proof must be completed; otherwise, the proof may not be correct.

Example 3.6.3

Can we just use examples?

Never attempt to prove P(k)P(k+1) by examples alone. Consider P(n):n2+n+11 is prime. In the inductive step, we want to prove that P(k)P(k+1) for ANY k1. The following table verifies that it is true for 1k9: n123456789n2+n+111317233141536783101 Nonetheless, when n=10, n2+n+11=121 is composite. So P(9)P(10) is false. The inductive step breaks down when k=9.

Example 3.6.4

The base step is equally important. Consider proving P(n):3n+2=3q for some integer q for all nN. Assume P(k) is true for some integer k1; that is, assume 3k+2=3q for some integer q. Then 3(k+1)+2=3k+3+2=3+3q=3(1+q). Therefore, 3(k+1)+2 can be written in the same form. This proves that P(k+1) is also true. Does it follow that P(n) is true for all integers n1? We know that 3n+2 cannot be written as a multiple of 3. What is the problem?

Solution

The problem is: we need P(k) to be true for at least one value of k so as to start the sequence of implications P(1)P(2),P(2)P(3),P(3)P(4), The induction fails because we have not established the basis step. In fact, P(1) is false. Since the first domino does not fall, we cannot even start the chain reaction.

Remark

Thus far, we have learned how to use mathematical induction to prove identities. In general, we can use mathematical induction to prove a statement about n. This statement can take the form of an identity, an inequality, or simply a verbal statement about n. We shall learn more about mathematical induction in the next few sections.

Summary and Review

  • Mathematical induction can be used to prove that a statement about n is true for all integers na.
  • We have to complete three steps.
  • In the base step, verify the statement for n=a.
  • In the inductive hypothesis, assume that the statement holds when n=k for some integer ka.
  • In the inductive step, use the information gathered from the inductive hypothesis to prove that the statement also holds when n=k+1.
  • Be sure to complete all three steps.
  • Pay attention to the wording. At the beginning, follow the template closely. When you feel comfortable with the whole process, you can start venturing out on your own.

Exercises 

Exercise 3.6.1

Use induction to prove that 13+23+33++n3=n2(n+1)24 for all integers n1.

Exercise 3.6.2

Use induction to prove that the following identity holds for all integers n1: 1+3+5++(2n1)=n2.

 

Proof

Base Case: consider n=1.  2(1)1=1 and 12=1 so the LHS & RHS are both 1. This works for  n=1.

Inductive Step: Assume this works for some integer, k1. In other words, 1+3+5++(2k1)=k2. (Inductive Hypothesis)

Consider the case of  n=k+1.   1+3+5++(2k1)+(2(k+1)1)

 =k2+(2(k+1)1) by inductive hypothesis
=k2+2k+21=k2+2k+1=(k+1)2 by algebra

1+3+5++(2(k+1)1)=(k+1)2; assuming our proposition works for k it will also work for k+1.

By PMI, 1+3+5++(2n1)=n2 for all integers,  n1.

W5

Exercise 3.6.3

Use induction to show that 1+13+132++13n=32(113n+1) for all positive integers n.

Exercise 3.6.4

Use induction to establish the following identity for any integer n1: 13+9+(3)n=1(3)n+14.

Exercise 3.6.5

Use induction to show that, for any integer n1: ni=1ii!=(n+1)!1.

Exercise 3.6.6

Use induction to prove the following identity for integers n1: ni=11(2i1)(2i+1)=n2n+1.

Exercise 3.6.7

Prove 22n1 is divisible by 3, for all integers n0.

Proof

Base Case: consider n=0.  22(0)1=11=0.  0 is divisible by 3 because 0 = 0(3).

Inductive Step: Assume this works for some integer, k0. In other words, 22k1 is divisible by 3. (Inductive Hypothesis)

Since 22k1 is divisible by 3, there exists some integer, m such that 22k1=3m,  by definition of divides.

Consider the case of  n=k+1.  By algebra: 22(k+1)1=22k+21=22k221=22k41=22k(3+1)1=322k+22k1
=322k+3m by inductive hypothesis

=3(22k+m) by algebra

22(k+1)1=3(22k+m) and  (22k+m)Z since the integers are closed under addition and multiplication.  

So, 22(k+1)1 is divisible by 3 by the definition of divisible.

Thus assuming our proposition works for k it will also work for k+1.

By PMI,  22n1 is divisible by 3, for all integers n0.

W5

Exercise 3.6.8

Evaluate ni=11i(i+1) for a few values of n. What do you think the result should be? Use induction to prove your conjecture.

Exercise 3.6.9

Use induction to prove that ni=1(2i1)3=n2(2n21) whenever n is a positive integer.

Exercise 3.6.10

Use induction to show that, for any integer n1: 1222+32+(1)n1n2=(1)n1n(n+1)2.

Exercise 3.6.11

Use mathematical induction to show that ni=1i+4i(i+1)(i+2)=n(3n+7)2(n+1)(n+2) for all integers n1.

Exercise 3.6.12

Use mathematical induction to show that 3+ni=1(3+5i)=(n+1)(5n+6)2 for all integers n1.

Answer

No answer here at this time.

 


This page titled 3.6: Mathematical Induction - An Introduction is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?