G12 Chapter 2: Mathematical Induction

Chapter 2 Summary: Mathematical Induction

1. Introduction

Mathematical Induction is a powerful method of mathematical proof used to establish the validity of a statement, formula, or inequality for all natural numbers $n$ (or for a subset of integers starting from a specific base value).

2. The Principle of Mathematical Induction (PMI)

Let $P(n)$ be a statement or proposition concerning the natural number $n$, where $n \in \mathbb{N}$. To prove that $P(n)$ is true for all $n \geq n_0$, we must complete two critical steps:

• Base Step (Basis of Induction): Prove that the statement is true for the initial value, typically $n = 1$ (or $n = n_0$ if the domain starts at a higher integer). That is, show that $P(1)$ is true.
• Inductive Step: Prove that if the statement is assumed to be true for an arbitrary natural number $n = k$ (where $k \geq n_0$), then it must also be true for the next consecutive natural number $n = k + 1$.
  • Inductive Hypothesis: The assumption that $P(k)$ is true.
  • Goal: Show that $P(k) \implies P(k + 1)$.

If both steps are successfully established, then by the Principle of Mathematical Induction, $P(n)$ is true for all natural numbers $n \geq n_0$.

3. Common Application Types

Problems in Mathematical Induction generally fall into three major categories:

3.1 Summation Series

Proving formulas that define the sum of a sequence.

• Example 1: $1 + 3 + 5 + \dots + (2n - 1) = n^2$
• Example 2: $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$
• Example 5: $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$

3.2 Divisibility and Factors

Proving that an algebraic expression is divisible by a specific integer or contains a specific factor for all valid values of $n$.

• Example 3: Prove that $3^n - 1$ is a multiple of $2$.
• Example 6: Prove that $a - b$ is a factor of $a^n - b^n$.

3.3 Inequalities

Proving that one expression is strictly greater than or less than another within a specified domain. These problems frequently rely on conditional algebraic manipulations such as $k \geq n_0$.

• Example 7: Prove that $4n \lt 2^n$ for all natural numbers $n \geq 5$.

4. Key Strategy for the Inductive Step

The core mechanism of an induction proof relies on breaking down the expression for $P(k + 1)$ so that it reveals the expression for $P(k)$. Once isolated, the Inductive Hypothesis is substituted into the equation, and the remaining terms are simplified algebraically to match the target form of $P(k + 1)$.

===========================

Example 1

Use the mathematical induction principle to prove that $1 + 3 + 5 + \dots + (2n - 1) = n^2$, for all natural numbers $n$.

Solution

Click to view detailed Solution

Proof

Let $P(n)$ denote the statement $1 + 3 + 5 + \dots + (2n - 1) = n^2$.
(1) For $n = 1$, \[\begin{align*} \text{L.H.S.} &= 1, \\ \text{R.H.S.} &= 1^2 = 1. \end{align*}\] \[ \text{L.H.S.} = \text{R.H.S.} \] The statement is true for $n = 1$.
(2)Assume that the statement is true for $n = k$, that is \[ 1 + 3 + 5 + \dots + (2k - 1) = k^2. \] We will show that the statement is true for $n = k + 1$, that is we have to show that $1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] = (k + 1)^2$.
It is proved that \[\begin{align*} 1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] &= k^2 + [2(k + 1) - 1] \\ &= k^2 + 2k + 2 - 1 \\ &= k^2 + 2k + 1 \\ &= (k + 1)^2. \end{align*}\] Therefore, the statement is true for $n = k + 1$.
(3)Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
===========================

Example 2

Use the mathematical induction principle to prove that $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$, for all natural numbers $n$.

Solution

Click to view detailed Solution

Let $P(n)$ denote the statement $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$.

(1) For $n = 1$,

$\text{L.H.S.} = 1,$
$\text{R.H.S.} = \frac{1(1 + 1)}{2} = 1.$

$\text{L.H.S.} = \text{R.H.S.}$

The statement is true for $n = 1$.
(2) Assume that the statement is true for $n = k$, that is

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

We will show that the statement is true for $n = k + 1$, that is we have to show that $1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$.

It is proved that

\[ \begin{align*} 1 + 2 + 3 + \dots + k + (k + 1) &= \frac{k(k + 1)}{2} + (k + 1) \\ &= \frac{k^2 + k + 2k + 2}{2} \\ 1 + 2 + 3 + \dots + k + (k + 1) &= \frac{k^2 + 3k + 2}{2} \\ &= \frac{(k + 1)(k + 2)}{2}. \end{align*}\]

Therefore, the statement is true for $n = k + 1$.
(3) Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
===========================

Exercise 2.1

Question 1

Prove the following by using the principle of mathematical induction for all natural numbers $n:$
(a) $1+ 3+ 3^{2}+ \cdots + 3^{n- 1}= \frac {3^{n}- 1}2$

Click to view Solution

Let $P(n)$ denote the statement: \[ 1 + 3 + 3^2 + \dots + 3^{n-1} = \frac{3^n - 1}{2} \]
For $n=1$: \[ \text{L.H.S.} = 3^{1-1} = 3^0 = 1 \] \[ \text{R.H.S.} = \frac{3^1 - 1}{2} = \frac{2}{2} = 1 \] Since $\text{L.H.S.} = \text{R.H.S.}$, $P(1)$ is true.
Assume $P(k)$ is true for some $k \in \mathbb{N}$, i.e., \[ 1 + 3 + 3^2 + \dots + 3^{k-1} = \frac{3^k - 1}{2} \] We need to prove $P(k+1)$, i.e., \[ 1 + 3 + 3^2 + \dots + 3^{k-1} + 3^k = \frac{3^{k+1} - 1}{2} \] Starting from the left-hand side: \[\begin{align*} (1 + 3 + 3^2 + \dots + 3^{k-1}) + 3^k &= \frac{3^k - 1}{2} + 3^k \quad \text{(by inductive hypothesis)} \\ &= \frac{3^k - 1 + 2 \cdot 3^k}{2} \\ &= \frac{3 \cdot 3^k - 1}{2} \\ &= \frac{3^{k+1} - 1}{2} \end{align*}\] Thus, $P(k+1)$ is true.
Hence, by the principle of mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}$.

=====================
(b) $1^3+2^3+3^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2$

Click to view Solution

Let $P(n)$ denote the given statement.
1. For $n=1$: \[ \text{L.H.S.} = 1^3 = 1 \] \[ \text{R.H.S.} = \left(\frac{1(1+1)}{2}\right)^2 = 1^2 = 1 \] Thus, $P(1)$ is true.
2.Assume $P(k)$ is true: \[ 1^3 + 2^3 + \dots + k^3 = \left(\frac{k(k+1)}{2}\right)^2 \]
3. Show $P(k+1)$ is true: \[\begin{align*} (1^3 + 2^3 + \dots + k^3) &+ (k+1)^3 \\ &= \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 \\ &= \frac{k^2(k+1)^2}{4} + (k+1)^3 \\ &= (k+1)^2 \left[ \frac{k^2}{4} + (k+1) \right] \\ &= (k+1)^2 \left[ \frac{k^2 + 4k + 4}{4} \right] \\ &= (k+1)^2 \frac{(k+2)^2}{4} = \left(\frac{(k+1)(k+2)}{2}\right)^2 \end{align*}\] Thus, $P(k+1)$ is true.
Hence, by the principle of mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}$.

(c) $2^3+ 4^3+ 6^3+ \cdots + ( 2n) ^3= 2n^2( n+ 1) ^2$
(d) $1\cdot 2+ 2\cdot 3+ 3\cdot 4+ \cdots + n( n+ 1) = \frac {n( n+ 1) ( n+ 2) }3$
(e) $\frac 12+ \frac 14+ \frac 18+ \cdots + \frac 1{2^n}= 1- \frac 1{2^n}$
(f) $1+2+2^2++\cdots+2^{n-1}=2^n-1$
(g) $\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+\cdots+\frac{1}{n(n+1)}=\frac{n}{n+1}.$$
======================

Example 3

Use the mathematical induction principle to prove that $3^n - 1$ is a multiple of $2$ for all natural numbers $n$.

Solution

Click to view detailed Solution
Let $P(n)$ denote the statement $3^n - 1$ is a multiple of $2$.
1.For $n = 1$, $3^1 - 1 = 2$ which is a multiple of $2$.
The statement is true for $n = 1$.
2.Assume that the statement is true for $n = k$, that is \[ 3^k - 1 \text{ is a multiple of } 2. \] We will show that the statement is true for $n = k + 1$, that is we have to show that $3^{k+1} - 1$ is a multiple of $2$.
It is proved that $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 2 \cdot 3^k + 3^k - 1$.
Since $2 \cdot 3^k$ is a multiple of $2$ and $3^k - 1$ is a multiple of $2$, we can say that $2 \cdot 3^k + 3^k - 1$ is also a multiple of $2$. So, $3^{k+1} - 1$ is also a multiple of $2$.
Therefore, the statement is true for $n = k + 1$.
3.Hence, by principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n$.
===========================