Strong Induction and Well-Ordering

Strong Induction and Well-ordering

Principle of strong induction

It is sometimes convenient to replace the induction hypothesis P (k) by the stronger assumption P (1), P (2), P (3), ... P (k) are true.

The resulting principle known as the principle of strong mathematical induction.

Step 1: Inductive base: To prove P (1) is true.

Step 2: Strong inductive hypothesis: Assume that P (n) is true for all integers 1 ≤ n ≤ k.

Step 3: Inductive step: To prove that P (k+1) is true on basis of the strong inductive hypothesis.

Example 1: Prove by mathematical induction that 6ⁿ⁺² + 7²ⁿ⁺¹ is divisible by 43 for each positive integers.

Solution: Let P (n): 6ⁿ⁺² + 7²ⁿ⁺¹ is divisible by 43.

Step 1: To prove P (1) is true.

6¹⁺² + 7²⁺¹ = 6³ + 7³ = 216+343 = 559 = (43) (13)

which is divisible by 43.

P (1) is true.

Step 2: Assume that P (k) is true.

(i.e.,) 6^k+2 + 7^{2k +1} = (43) (m) for some integer.

Step 3: To prove P (k+1) is true.

 (i.e.,) 6^(k+1)+2 + 7^{2(k + 1)+1} = 6^k+3 + 7^{2k +3}

= 6^k+3 + 7^2k+1 (7²)

= 6(6^k+2) + 7^2k+1 (7²)

= 6(6^k+2 + 7^2k+1) + (43) 7^2k+1

= 6 (43) (m) + 43 (7^2k+1)

= 43 [6m + 7^2k+1]

which is divisible by 43.

Hence P (k+1) is true whenever P (k) is true.

By the principle of mathematical induction P (n) is true for all positive integer n.

Example 2: Any positive integer n ≥ 2 is either a prime or a product of primes. To prove this we use the principle of strong mathematical induction. (OR)

State the Strong Induction (the second principle of mathematical induction). Prove that a positive integer greater than 1 is either a prime number or it can be written as product of prime numbers.                        [A.U M/J 2013]

Solution :

Let P (n): n ≥ 2 is either a prime or a product of primes.

Step 1: To prove P (2) is true.

2 = 2 is a prime.

Hence P (2) is true.

Step 2: Assume that the statement is true for 2 ≤ n ≤ k

Step 3: To prove P (k+1) is true.

For the integer k + 1, if k + 1 is a prime, the statement is true. If k +1 is not a prime, then k + 1 can be written as pq, for some 2 s ≤ p ≤ k and 2 ≤ q ≤ k.

According to the induction hypothesis, P is either a prime or a product of prime. Also, q is either a prime or a product of prime. Consequently, pq is a product of prime.

Example 3: Use strong induction to show that if you can run one mile or two miles, and if you can always run two more miles once you have run a specified number of miles, then you can run any number of miles.

Solution: Let p (n): The given statement.

Step 1: To prove p (1) is true.

In the given statement we can run one mile, so p (1) is true.

Step 2: Assume that we can run any number of miles from 1 to k.

Step 3: To prove p (k + 1) is true.

If k = 1, then we can run two miles.

If k > 1, then the inductive hypothesis tells us that we can run k-1 miles, so we can run (k-1) + 2 = k + 1 miles.

Hence p (k + 1) is true.

By the principle of mathematical induction p (n) is true.

Example 4: Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

Solution: We will prove this result using the principle of mathematical induction. Then we will present a proof using strong induction.

Let P (n) be the statement that postage of n cents can be formed using 4-cent and 5-cent stamps.

Step 1: We can form postage of 12, 13, 14 and 15 cents using three 4-cent stamps, two 4-cent stamps and one 5-cent stamp, one 4-cent stamp and two 5-cent stamps, and three 5-cent stamps, respecively. This shows tha P (12), P (13), P (14) and P (15) are true.

Step 2: The inductive hypothesis is the statement that P (j) is true for 12 ≤ j ≤k, where k is an integer with k ≥ 15. That is, we assume that we can form postage of j cents, where 12 ≤ j ≤k.

Step 3: To prove P (k+1) is true, that is, we can form postage of  k + 1 cents. Using the inductive hypothesis, we can assume that P (k-3) is true since k-3 ≥ 12, that is, we can form postage of k-3 cents using just 4-cent and 5-cent stamps. To form postage of k+ 1 cents, we need only add another 4-cent stamp to the stamps we used to form postage of k - 3 cents.

That is, we have shown that if the inductive hypothesis is true, then P (k+1) is also true. This completes the inductive step.

Example 5: Which amount of money can be found using just two-dollar bills and five-dollar bills? Prove your answer using strong induction. Solution: We can form all amounts except $ 1 and $ 3.

Let P (n): We can form n dollars using just 2 dollar and 5 dollar bills.

(i.e.,) P (n) is true for all n ≥ 5 (It is clear that $1 and $3 cannot be formed and that $2 and $4 can be formed)

Step 1: 5 = 5 and 6 = 2 + 2 + 2

Step 2: Assume the inductive hypothesis, that P (j) is true for all k with 5 ≤ j ≤k, where k is an arbitrary integer greater than or equal to 6.

Step 3: To prove P (k + 1) is true.

k-1 ≥ 5, we know that P (k-1) is true, that is that we can form k - 1 dollars.

Add another 2-dollar bill and we have formed k + 1 dollars.

The well-ordering property

Every non-empty set of non-negative integers has a least element. The well-ordering property can often be used directly in proofs.

Example 6 Show that strong induction is a valid method of proof by showing that it follows from the well-ordering property.

Solution: Let P (n): Given statement.

Assume that the well-ordering property holds.

Suppose that P (1) is true and that the conditional statement

[P (1) ^ P (2) ^ ... →  P(n)] →  P(n+1) is true for every positive integer n.

Let S be the set of positive integers n for which P (n) is false.

We will show S = ϕ

Assume that S ≠ ϕ

Then by the well-ordering property there is a least integer m in S.

We know that m cannot be 1 because P (1) is true.

If n = m is the least integer such that P (n) is false,

P(1), P(2), ... P(m-1) are true, and m-1≥ 1.

Because [P(1) ^ P(2) ^ ... ^ P(m-1)] → P (m) is true it follows that P (m) must also be true, which is a contradiction.

Hence S = ϕ.

Example 7: Use well-ordering property to prove the division algorithm. "If a is an integer and d is a positive integer, then there are unique dq + r. integers q and r with 0 ≤ r < d and a = dq + r.

Solution: Let P be the set of positive integers of the form a - dq, where q is an integer.

This is non empty because - dq, can be made as large as desired.

By the well ordering property, P has a least element r = a – dq₀.

The integer r is positive.

It is also the case that r < d.

If it were not, then there would be a smaller positive element in P, namely

a - d (q₀+ 1).

To see this, suppose r ≥ d.

Because a = dq₀ + r

a - d (q₀ + 1) = (a – dq₀) - d = r - d ≥ 0.

Consequently there are integers q and r with 0 ≤ r <d then proving q and r are unique we get the result.

EXERCISE 2.2

1. Suppose we can reach the first and second rungs of an infinite ladder, and we know that if we can reach a rung, then we can reach two rungs higher. Can we prove that we can reach every rung using the principle of mathematical induction? Can we prove that we can reach every rung using strong induction.

2. Show that if n is integer greater than 1, then n can be written as the product of primes.   

3. A simple polygon with n sides, where n is an integer with n ≥ 3, can be triangulated into n - 2 triangles. Prove by induction hypothesis.

4. In a round-robin tournament every player plays every other player exactly once and each match has a winner and a loser. We say that the players P₁, P₂, … P_m form a cycle if P₁ beats P₂, P₂ beats P₃, …P_m-1 beats P_m, and P_m beats P₁. Use the well ordering principle to show that if there is a cycle of length m (m≥ 3) among the players in a round-robin tournament, there must be a cycle of three of these players.

5. Use strong induction to show that if a simple polygon with atleast four sides is triangulated, then atleast two of the triangles in the triangulation have two sides of the triangles in the triangulation have two sides that border the exterior of polygon.

6. Show that the well-ordering property can be proved when the principle of mathematical induction is taken as an axiom.

7. Show that the principle of mathematical induction and strong induction are equivalent, that is, each can be shown to be valid from the other.

8. Show that if a₁, a₂ …. a_n are n distinct real numbers, exactly n-1 multiplications are used to compute the product of these n numbers no matter how parentheses are inserted into their product.