Theorem Proving Techniques: Mathematical Induction

Definition

Mathematical induction is a proof technique used to establish that a proposition $P(n)$ is true for all natural numbers $n$ starting from a specified initial value, usually $n = 1$ or $n = 0$, by proving:

1. Base case

• : $P(n_0)$ is true for the first value $n_0$.

2. Inductive step

• : Assuming $P(k)$ is true for an arbitrary natural number $k \ge n_0$, prove that $P(k+1)$ is also true.

If both steps are verified, then $P(n)$ is true for all $n \ge n_0$.

A more general form, called strong induction, assumes that all statements $P(n_0), P(n_0+1), \dots, P(k)$ are true to prove $P(k+1)$.

---

Main Content

1. Principle of Mathematical Induction

Base case establishes the starting point

• : The first step is to prove that the proposition is true for the smallest relevant number. This anchors the entire argument. For example, if a formula is claimed for all $n \ge 1$, then we first verify it for $n=1$. Without a correct base case, the inductive chain has no starting point and the proof fails.

Inductive step proves the chain reaction

• : Here, we assume the statement is true for an arbitrary integer $k$ and then logically deduce that it must also be true for $k+1$. This step is not a guess; it must use valid algebraic or logical transformations. The role of the inductive hypothesis is to bridge the gap between one case and the next.

Conclusion extends truth to all natural numbers

• : Once both base case and inductive step are established, the proposition is true for every number from the starting point onward. This is because the truth flows from the base case to the next case, then to the next, and so on without interruption.

Example: Prove that
$$1+2+3+\cdots+n=\frac{n(n+1)}{2}$$ for all $n \ge 1$.

• Base case: For $n=1$, LHS = 1 and RHS = $\frac{1(2)}{2}=1$, true.

• Inductive hypothesis: Assume true for $n=k$: $$1+2+\cdots+k=\frac{k(k+1)}{2}$$

• Inductive step for $k+1$: $$1+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)$$ $$=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}$$ which matches the formula for $n=k+1$. Hence the statement is true for all $n \ge 1$.

---

2. Strong Induction and Its Usefulness

Uses all previous cases, not just the immediate one

• : In strong induction, to prove $P(k+1)$, we assume $P(n_0), P(n_0+1), \dots, P(k)$ are all true. This is useful when the next case depends on several earlier cases rather than only the immediately preceding one.

Especially suitable for recursive and divisibility problems

• : Many sequences and number-theoretic properties cannot be proved by simple induction alone because the proof of one step may require more than one earlier result. Strong induction is ideal for such situations.

Equivalent in power to simple induction

• : Although strong induction looks more powerful, it is logically equivalent to ordinary induction. The difference lies in convenience and the structure of the proof, not in what can ultimately be proved.

Example: Show that every integer $n \ge 2$ can be written as a product of primes.

• Base case: $n=2$, and 2 is prime.
• Inductive assumption: Assume every integer from 2 up to $k$ can be expressed as a product of primes.
• Inductive step: Consider $k+1$. If $k+1$ is prime, we are done. If it is composite, then $k+1 = ab$, where $2 \le a,b \le k$. By the inductive hypothesis, both $a$ and $b$ are products of primes, so $k+1$ is also a product of primes.

This proof naturally requires the assumption that all smaller cases are already known.

---

3. Common Forms, Techniques, and Typical Proof Patterns

Direct induction for formulas and identities

• : Induction is frequently used to prove summation formulas, inequalities, and algebraic identities. Typical structure: verify the base case, assume the formula for $k$, and simplify the $k+1$ expression until it matches the required form.

Structural and recursive reasoning in discrete mathematics

• : Induction is not limited to numbers. It is also used on recursively defined structures such as strings, trees, and formulas. In set theory and relations, it may be used to prove properties of recursively defined sets or transitive closures.

Avoiding common mistakes

• : A common error is assuming what must be proved without proper justification, or failing to clearly state the inductive hypothesis. Another mistake is proving only the base case and forgetting to show the step from $k$ to $k+1$. A correct proof must explicitly connect the hypothesis to the next case.

Example of an inequality: Prove that $2^n \ge n+1$ for all $n \ge 0$.

• Base case: $n=0$, $2^0=1 \ge 1$, true.
• Inductive hypothesis: Assume $2^k \ge k+1$.
• Inductive step: $$2^{k+1}=2\cdot 2^k \ge 2(k+1)=2k+2 \ge k+2$$ since $2k+2 \ge k+2$ for $k \ge 0$. Hence $2^{k+1} \ge (k+1)+1$.

This proves the statement.

---

Working / Process

1. State the proposition clearly and identify the starting value

Write the statement $P(n)$ precisely and determine whether the induction begins at $n=0$, $n=1$, or another natural number. This prevents ambiguity and ensures that the proof is aligned with the claim.

2. Prove the base case and then assume the inductive hypothesis

Verify the proposition for the first required value. Next, assume $P(k)$ is true for an arbitrary $k\ge n_0$. This assumption is temporary and is used only within the proof of the next step.

3. Use the hypothesis to prove the next case and conclude

Show that $P(k+1)$ follows logically from the assumption. Once this is done, conclude that the proposition is true for all values from the base onward. For strong induction, replace the single hypothesis by all previous cases up to $k$.

Simple visual pattern for induction:

P(n0)  ->  P(n0+1)  ->  P(n0+2)  ->  P(n0+3)  ->  ...
   base        step         step         step

This shows how truth propagates from one case to the next.

---

Advantages / Applications

Efficient proof of infinitely many cases

• : Induction allows one proof to establish infinitely many statements at once. Instead of checking every natural number separately, we prove the starting point and the repeating logical step.

Widely used in mathematics and computer science

• : It is applied in proving summation formulas, divisibility rules, inequalities, recursion properties, algorithm correctness, and the behavior of data structures such as linked lists, trees, and binary heaps.

Essential for recursive definitions and formal reasoning

• : Many objects in discrete mathematics are defined recursively, and induction is the natural tool for proving properties of such objects. It is also foundational in proofs involving the correctness of recursive algorithms and mathematical structures.

Examples of applications:

• Proving formulas like $1+2+\cdots+n=\frac{n(n+1)}{2}$
• Proving divisibility such as $7^n-1$ is divisible by 6 for all $n \ge 1$
• Proving algorithm correctness, for example, that recursive factorial or merge sort procedures work properly
• Proving properties of sets and relations defined recursively

---

Summary

• Mathematical induction proves statements for all natural numbers by using a base case and an inductive step.
• Strong induction is a useful variation where all earlier cases are assumed to prove the next one.
• It is a key theorem proving technique in discrete mathematics, especially for formulas, inequalities, recursive structures, and algorithm correctness.
• Mathematical induction, strong induction, base case, inductive hypothesis, inductive step, recursive proof