
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Formalizing Proofs for Mathematical Induction
Mathematical Inductions are one of the fundamental methods for proving statements or conjectures about natural numbers and sequences.
In this chapter, we will see the process of proving mathematical inductions, understand their structure and essentials through detailed examples.
Understanding Mathematical Induction
The concept of "Induction" is often used while trying to prove a statement that applies to all natural numbers or for numbers beyond a certain threshold.
Inductive proofs have two main parts −
- The base case, where the statement is verified for an initial value (like n = 1 or n = 28)
- The inductive step, where we consider that the statement holds for an arbitrary case n = k and show it must also hold for n = k + 1.
Let us understand these two steps in detail −
- Base Case − We start the proof at the base case. In this state, we set goal to prove the statement is true for a particular starting point (e.g., the smallest number or a minimum threshold).
- Inductive Step − Here we apply the "if-then" logic of the proof. We assume the statement is true for an arbitrary number k and then use this assumption to prove it for k + 1 as well.
When both parts are formed, we conclude that the statement is true for all numbers above the base case with the principle of induction.
Structure of an Inductive Proof
Let us understand the formal structure of an inductive proof, including how each part of the proof is built.
- State the Proposition − Define the proposition P(n) that we want to prove.
- Base Case − Show that P(n) is true for the initial case. And typically n = 1 or the starting point specified in the problem.
- Inductive Hypothesis − Assume P(k) holds for some arbitrary k ≥ 1.
- Prove P(k + 1) − Using P(k), it demonstrate that P(k + 1) must also be true.
- Conclusion − Finally conclude that by the principle of induction, the statement holds for all n ≥ the starting point.
Let us see these steps through examples for a better understanding.
Example 1: Sum of the First n Natural Numbers
One of the classic examples of mathematical induction is that proving the formula for the sum of the first n natural numbers −
$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: n \:=\: \frac{n(n \:+\: 1)}{2}}$$
Step-by-Step Proof
Define the Statement − Consider P(n) be the statement 1 + 2 + 3 + + n = n(n + 1)/2.
Base Case − For n = 1,
$$\mathrm{1 \:=\: \frac{1(1 \:+\: 1)}{2} \:=\: 1}$$
So, P(1) holds true.
Inductive Hypothesis − Next assume P(k) is true for some k ≥ 1; that is,
$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k \:=\: \frac{k(k \:+\: 1)}{2}}$$
Inductive Step − We need to show that P(k + 1) holds, so it means −
$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k \:+\: (k\:+\:1) \:=\: \frac{(k\:+\:1)(k\:+\:2)}{2}}$$
Start by adding (k + 1) to both sides of the inductive hypothesis −
$$\mathrm{(1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k) \:+\: (k \:+\: 1) \:=\: \frac{k(k \:+\: 1)}{2} \:+\: (k \:+\: 1)}$$
It will be (k + 1) from the right side −
$$\mathrm{\frac{k(k\:+\:1)\:+\: 2(k\:+\:1)}{2} \:=\: \frac{(k\:+\:1)(k\:+\:2)}{2}}$$
This proves P(k + 1) holds true.
Conclusion − So by induction, the formula is valid for all n ≥ 1.
Example 2: Multiple of 5 in Powers of 6
Let us use induction to show that 6n − 1 is always a multiple of 5 for all natural numbers n.
Statement Definition − Consider P(n) be the statement that 6n − 1 is a multiple of 5.
Base Case − For n = 1,
$$\mathrm{6^{1} \:-\: 1 \:=\: 5}$$
which is a multiple of 5. Thus, P(1) is true.
Inductive Hypothesis − Assume P(k) holds for some k ≥ 1; so that, 6k − 1 is a multiple of 5. This means 6k−1 = 5m for some integer mmm.
Inductive Step − We need to show that P(k + 1) holds, i.e., 6k+1 is a multiple of 5. So proceed as follows −
$$\mathrm{6^{k + 1}\:-\:1 \:=\: 6 \:\cdot\: 6^{k} \:-\: 1 \:=\: (5m \:+\: 1) \:\cdot\: 6 \:-\: 1 \:=\: 5(6m) \:+\: 5}$$
From here we can get 6k+1 − 1 = 5 × (6m + 1), which is clearly a multiple of 5.
Conclusion − By induction, 6n − 1 is a multiple of 5 for all n ∈ N.
Example 3: Inequality Using Induction
Another useful area for induction is proving inequalities. For example, consider we want to prove that n2 < 2n for all integers n ≥ 5.
Define the Statement − Let us consider P(n) represent the statement n2 < 2n.
Base Case − For n = 5,
$$\mathrm{5^{2} \:=\: 2^{5} \quad \text{and} \quad 2^{5} \:=\: 32}$$
So, 25 < 32 and P(5) is true.
Inductive Hypothesis − Assume P(k) is true for some k ≥ 5, this means k2 < 2k.
Inductive Step − Show that P(k + 1) holds, or
$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2^{k \:+\: 1}}$$
Expanding the left side −
$$\mathrm{(k \:+\: 1)^2 \:=\: k^2 \:+\: 2k \:+\: 1}$$
Using the inductive hypothesis, k2 < 2k, so
$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2^{k} \:+\: 2k \:+\: 1}$$
If we observe that carefully, for k ≥ 5, 2k ≥ 2k+1, we get
$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2 \:\times\: 2^{k} \:=\: 2^{k \:+\: 1}}$$
Thus, P(k + 1) is true.
Conclusion − By the induction, n2 < 2n holds for all integers n ≥ 5.
Why are Mathematical Inductions Used?
Mathematical inductions show us how to establish that a pattern continues indefinitely. It simplifies proof structure and helps verify statements involving sequences, for natural numbers without needing to check each number individually. This is known as the "domino effect". It is used for proving statements which is what makes induction so powerful.
Conclusion
In this chapter, we touched upon the concept of proofing by mathematical induction. Starting with the basic principles of the base case and inductive step, we explained in detail how to set up an inductive proof with clear examples.
Through proofs on sums, multiples, and inequalities, we demonstrated how induction offers a structured way to confirm patterns across an infinite set of cases.
Whether checking formulas or verifying properties of sequences, mathematical inductions are used to understand complex relationships by relying on a foundational pattern.