Strong and Weak Induction in Discrete Mathematics

---

---

We use the induction theory in discrete mathematics to prove statements or conjectures by capturing the patterns. There are two types of induction techniques: the weak induction and the strong induction. Both these techniques have their unique applications and both of them are used for the same ultimate goal, i.e. to demonstrate the truth of statements across a broad set of values by proving them true in a particular sequence.

In this article, we will elaborate both the methods (strong induction and weak induction), including when to apply which method, and also have a set of examples to see these induction principles in action.

Basic Structure of Weak and Strong Induction

For a better understanding on how weak and strong induction differ, we must start with the general approach that each of these methods apply.

Weak Induction

Weak induction starts by proving that a statement is true for a base case, typically the smallest number in the range, like n = 1.

Then, assume that if it holds for an arbitrary integer k, prove that this assumption leads to the statement holding true for k + 1 as well. This process is called the inductive step. This step confirms that, if the statement is true for one case, it will be true for the next one in sequence. This will form a chain reaction of truths.

Strong Induction

Strong induction relies on a broader hypothesis. In the inductive step, instead of assuming the statement holds for just k, we assume it holds for all values up to k. This approach can be particularly useful in proofs where each new case depends on multiple prior cases, not just the immediately preceding one.

• Base Case − Prove the statement for the initial number(s) in the range.
• Inductive Step − Assuming the statement holds for all integers up to k, prove it for k + 1.

Example of Weak Induction: Sum of Natural Numbers

Let us see one example of weak induction. Let us prove that a well-known formula for the sum of the first n natural numbers −

$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: n \:=\: \frac{n(n \:+\: 1)}{2}}$$

Define the Statement − Consider P(n) be the statement $\mathrm{1 + 2 + 3 + \cdots + n = \frac{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 this 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 of Strong Induction: Factorization of Natural Numbers

Let us see the strong induction in action. Assume we want to prove that any integer n ≥ 2 is either a prime number or can be expressed as a product of primes.

Step-by-Step Proof

Define the Statement − Let P(n) state that any integer n ≥ 2 is either prime or can be expressed as a product of primes.

Base Case − For n = 2, we have 2 itself as a prime number, so P(2) is true.

Inductive Hypothesis − Assume P(k) is true for all values 2 ≤ k ≤ n. So that means every integer within this range is either a prime or a product of primes.

Inductive Step − Prove that P(n + 1) holds.

If n + 1 is prime, then P(n + 1) is automatically true.

If n + 1 is composite, then n + 1 can be written as a product of two smaller integers, say m and p. And 2 ≤ m, p ≤ n. By the inductive hypothesis, both m and p are either primes or products of primes.

So we can say n + 1 itself is a product of primes.

Conclusion − By strong induction, we conclude that any integer n ≥ 2 is either prime or a product of primes.

Choosing between Strong and Weak Induction

We understood both the techniques for induction. Both forms are effective for proofs over natural numbers. There are certain conditions that make one preferable over the other:

• Use weak induction when each case relies directly on the preceding case. The simplicity of weak induction often makes it easier to apply.
• Use strong induction when each new case depends on multiple previous cases or on complex relationships among previous terms.

For example, if we think a problem involving sequences where each term is generated from a combination of several previous terms. The strong induction, with its assumption states the statement holds for all previous terms up to k, this is ideal for such cases. On the other hand, for proofs of arithmetic series, weak induction usually good.

Example: The Chocolate Bar Puzzle

Let us see the last example to demonstrate the strength of strong induction. Let us look at the following puzzle:

Problem − We have a chocolate bar formed with n squares. Each break divides the bar along rows or columns. Now prove that it takes exactly n – 1 breaks to reduce the bar to individual squares.

Step-by-Step Proof

Define the Statement − Assume P(n) be the statement that it takes n – 1 breaks to reduce an n-square chocolate bar to single squares.

Base Case − For n = 2, a single break reduces the bar to individual squares, so that P(2) is true.

Inductive Hypothesis − Assume P(k) holds for all values 2 ≤ k ≤ n. This shows that for any bar with up to n squares, it takes k − 1 breaks to reduce it to individual squares.

Inductive Step − Now prove that P(n + 1) holds.

For an (n + 1) square bar, we make a break, creating two smaller bars with squares a and b, where a + b = n + 1

By the inductive hypothesis, it takes a – 1 breaks to separate the a-square piece and b – 1 breaks to separate the b-square piece.

Altogether, this requires 1 + (a − 1) + (b − 1) = n breaks. This is proving P(n + 1) is true.

Conclusion − By strong induction, we can conclude that n – 1 breaks are required to separate an n-square bar into individual squares.

Conclusion

In this chapter, we explained the weak induction and the strong induction techniques in discrete mathematics. Starting with the basics, we explored the structure and applications of weak induction, with an example of summing natural numbers.

Thereafter, we moved on to strong induction, showing how it provides additional flexibility by assuming the truth of all previous cases up to k. Through examples like the factorization of natural numbers and the chocolate bar puzzle, we understood how strong induction offers a broader framework for more complex proofs.