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 SolutionProof
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 SolutionLet $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}$.
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$
Hint:$\begin{align*}
&= 2k^2(k+1)^2 + 8(k+1)^3 \\
&= 2(k+1)^2 \left[ k^2 + 4(k+1) \right] \\
&= 2(k+1)^2 [k^2 + 4k + 4] \\
&= 2(k+1)^2(k+2)^2
\end{align*}$
(d) $1\cdot 2+ 2\cdot 3+ 3\cdot 4+ \cdots + n( n+ 1) = \frac {n( n+ 1) ( n+ 2) }3$
Hint:$\begin{align*}
&= (k+1)(k+2) \left[ \frac{k}{3} + 1 \right] \\
&= (k+1)(k+2) \frac{k+3}{3} \\
&= \frac{(k+1)(k+2)(k+3)}{3}
\end{align*}$
(e) $\frac 12+ \frac 14+ \frac 18+ \cdots + \frac 1{2^n}= 1- \frac 1{2^n}$
Hint:$\begin{align*}
&= 1 - \frac{1}{2^{k}} + \frac{1}{2^{k+1}} \\
&= 1 - \frac{1}{2^{k+1}}
\end{align*}$
(f) $1+2+2^2++\cdots+2^{n-1}=2^n-1$
Hint:$\begin{align*}
&= 2 \cdot 2^k - 1 \\
&= 2^{k+1} - 1
\end{align*}$
(g) $\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+\cdots+\frac{1}{n(n+1)}=\frac{n}{n+1}.$$
Hint:$\begin{align*}
&= \frac{1}{k+1} \left[ k + \frac{1}{k+2} \right] \\
&= \frac{1}{k+1} \left[ \frac{k^2 + 2k + 1}{k+2} \right] \\
&= \frac{1}{k+1} \cdot \frac{(k+1)^2}{k+2} = \frac{k+1}{k+2}
\end{align*}$
======================
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 SolutionLet $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$.
===========================
Example 4
Prove that $(ab)^n = a^n b^n$ for every natural number $n$.Solution
Click to view detailed MM SolutionClick to view Text Book Solution
===========================
Example 5
Prove that $1 \cdot 3 + 2 \cdot 3^2 + 3 \cdot 3^3 + \dots + n \cdot 3^n = \frac{(2n - 1)3^{n+1} + 3}{4}$ for all natural numbers $n$ by the use of the mathematical induction principle.Solution
Click to view detailed MM SolutionClick to view Text Book Solution
===========================
Example 6
Use the mathematical induction principle to prove that $a - b$ is a factor of $a^n - b^n$ for all natural numbers $n$.Solution
Click to view detailed MM SolutionClick to view Text Book Solution
===========================
Example 7
Use the mathematical induction principle to prove that $4n \lt 2^n$ for all natural numbers $n \geq 5$.Solution
Click to view detailed MM SolutionClick to view Text Book Solution
===========================
Question 2
Prove that 3 is a factor of $4^n-1$ for all natural numbers $n$ by using the mathematical induction.Hint:$\begin{align*}
4^{k+1} - 1 &= 4 \cdot 4^k - 1 \\
&= 4(3m + 1) - 1 \\
&= 12m + 4 - 1 = 12m + 3 \\
&= 3(4m + 1)
\end{align*}$
Question 3
Prove that $n^3-n+3$ is divisible by 3 for all natural numbers $n$ by using the mathematical induction.Hint:$ \begin{align*}
(k+1)^3 - (k+1) + 3 &= (k^3 + 3k^2 + 3k + 1) - k - 1 + 3 \\
&= (k^3 - k + 3) + 3k^2 + 3k \\
&= 3m + 3(k^2 + k) \\
&= 3(m + k^2 + k)
\end{align*}$
Question 4
Prove that $3^2n-1$ is divisible by 8 for all natural numbers $n$ by using the mathematical induction.Hint:$ \begin{align*}
3^{2(k+1)} - 1 &= 3^{2k+2} - 1 = 9 \cdot 3^{2k} - 1 \\
&= 9(8m + 1) - 1 \\
&= 72m + 9 - 1 = 72m + 8 \\
&= 8(9m + 1)
\end{align*}$
Question 5
Prove that $(n+1)^2\lt 2n^2$ for all natural numbers $n\geq 3$ by using the mathematical induction.Hint:$\begin{align*}
(k+2)^2 &= k^2 + 4k + 4 \\
&= (k^2 + 2k + 1) + 2k + 3 \\
&= (k+1)^2 + 2k + 3 \\
&\lt 2k^2 + 2k + 3 \quad \text{(by induction hypothesis)}\\
&= (2k^2+2k+1) +2\\
&\lt(2k^2+2k+2k)+2: \quad(1\lt 2k\text{ for all } k\geq 3)\\
&=2(k+1)^2
\end{align*}$
Question 6
Prove that $(2n+7)\lt (n+3)^2$ for all natural numbers $n$ by using the mathematical induction.Hint:$\begin{align*}
\text{L.H.S.} = 2k + 9 &= (2k + 7) + 2 \\
&\lt (k+3)^2 + 2 \quad \text{(by induction hypothesis)} \\
&= k^2 + 6k + 9 + 2 = k^2 + 6k + 11
\end{align*}$
Question 7
Prove that $x^2n-y^{2n}$ is divisible by $x+y$ for all natural numbers $n$ by using the mathematical induction.Hint:$\begin{align*}
x^{2(k+1)} - y^{2(k+1)} &= x^{2k+2} - y^{2k+2} \\
&= x^2 \cdot x^{2k} - y^2 \cdot y^{2k} \\
&= x^2 \cdot x^{2k} - x^2 \cdot y^{2k} + x^2 \cdot y^{2k} - y^2 \cdot y^{2k} \\
&= x^2(x^{2k} - y^{2k}) + y^{2k}(x^2 - y^2) \\
&= x^2 \cdot [ (x+y)M ] + y^{2k} \cdot [ (x+y)(x-y) ] \\
&= (x+y) \left[ x^2 M + y^{2k}(x-y) \right]
\end{align*}$
إرسال تعليق