4.2: Proof by Using Mathematical Induction

Last updated
Save as PDF

Page ID: 112212

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

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

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

In this section, we will continue the discussion on mathematical induction. Mathematical induction is a specific logic that people use for making an assertion or proving the truth value of a proposition.

Example

If we know the first object in a sequence of objects is a circle and we also know that if any one of the objects in this sequence is a circle, then next object in the sequence is also a circle. Then we can claim that all the objects in this sequence are circles.

We don't use this logic in our daily life very often, so it may not sound very convincing. But, it is used quite often in discrete math and computer science for making an argument or proving a proposition.

Example

Use induction to show that 5ⁿ - 1 is divisible by 4 for all n $LaTeX: \ge$ 1

First, we should understand the question. Here, 5ⁿ - 1, n = 1, 2, 3, ..., n, n+1, ... is a sequence of numbers:

4, 24, 124, ...

What we want to prove is: "All the numbers in this sequence are divisible by 4". To use mathematical induction, we need to prove

The first number in the sequence is divisible by 4
If any one of the numbers in the sequence is divisible by 4, then the next number in the sequence will be divisible by 4

If we can prove above two propositions are true, then we have proved the proposition "All the numbers in the sequence are divisible by 4"

The logic we use here is exactly the same as we did in the previous example: If we tell people

The first object in the sequence is a circle
If any one of the objects in the sequence is a circle, then the next object in the sequence will be a circle

We actually tell people "All the objects in the sequence are circles"

Now, go back to our second example, let's prove following propositions:

The first number in the sequence is divisible by 4
If any one of the numbers in the sequence is divisible by 4, then the next number in the sequence will be divisible by 4

Since the first number in the sequence is 4, it is divisible by 4.

We can use 5ⁿ - 1 to represent any one of the numbers in this sequence because that is how the sequence is formed.

The second proposition says "If 5ⁿ - 1 is divisible by 4, then the next number in the sequence, which is 5ⁿ⁺¹ - 1 is also divisible by 4" We want to prove this proposition is true.

Proof.

5ⁿ⁺¹ - 1 = 5 $LaTeX: \cdot$ 5ⁿ - 1 = 4 $LaTeX: \cdot$ 5ⁿ + 5ⁿ - 1. According to our assumption, 5ⁿ - 1 is divisible by 4 and it is easy to see 4 $LaTeX: \cdot$ 5ⁿ is divisible by 4 , therefore, (4 $LaTeX: \cdot$ 5ⁿ) + (5ⁿ - 1) is divisible by 4, and 4 $LaTeX: \cdot$ 5ⁿ + 5ⁿ - 1 is 5ⁿ⁺¹ - 1. Proof is completed.

Example

Prove the predicate "n³+2n is a multiple of 3" is true for any positive integer n.

We will use the same logic we used in the previous examples to prove this predicate is true. Again, here we are talking about a sequence of numbers:

3, 12, 33, ...

What we want to do is to prove all the numbers in this sequence are multiple of 3 (all the numbers are divisible by 3). To use mathematical induction, we need to prove following two propositions:

The first number in the sequence is a multiple of 3
If any one of the number in the sequence is a multiple of 3, then the next number in the sequence is also a multiple of 3

It is obvious that the first number in the sequence is a multiple of 3.

Now, we let n³+2n to represent any one of the numbers in the sequence, then the next number in the sequence will be (n+1)³+2(n+1). The second proposition says: "If n³+2n is a multiple of 3, then (n+1)³+2(n+1) is also a multiple of 3"

We will need to fresh our algebra skills a little bit.

In algebra, (n+1)³ = n³ + 3n² +3n +1(You can check it out from your old algebra book or simply go to ChatGPT to find out).

Thus,

(n+1)³+2(n+1)

= n³ + 3n² + 3n + 1 + 2(n+1)

= n³ + 3n² + 3n + 1 + 2n + 2

= (n³ + 2n) + 3n² +3n + 3

= (n³ + 2n) + 3(n² +n + 1)

From the last expression, (n³ + 2n) is multiple of 3 (that is our assumption). Since (n² +n + 1) is an integer, 3(n² +n + 1) must be a multiple of 3. Therefore, (n³ + 2n) + 3(n² +n + 1) must be a multiple of 3 and that is (n+1)³+2(n+1). The proof is completed

The way we prove this predicate may seem a little bit difficult for you to understand. It is because it requires some algebraic skills which you may forgot. And the most difficult is the induction logic we used in the proving process. But, the logic we used in this proof is exactly the same as the logic we used in the previous examples.

Search

Text Color

Text Size

Margin Size

Font Type