Example of a Proof by Strong Induction
Proposition If n ∈ N, then 12 | (n4 − n2).
Proof. We will prove lthis with strong induction.
(1) First note that the statement is true for the first six positive integers:
For n = 1, 12 divides 14 −12 = 0.
For n = 2, 12 divides 24 −22 = 12.
For n = 3, 12 divides 32 −32 = 72.
For n = 4, 12 divides 44 −42 = 240.
For n = 5, 12 divides 54 −52 = 600.
For n = 6, 12 divides 64 −62 = 1260.
(2) For k ≥ 6, assume 12 | (m4 − m2) for 1 ≤ m ≤ k (i.e., S1, S2 ,..., Sk are true).
We must show Sk+1 is true, that is, 12 |(k +1)4 −(k +1)2.
Now, Sk−5being true means 12 |(k −5)4 −(k −5)2. To simplify, put k −5 = l so
12 | (l4 - l2 )meaning (l4 - l2 )=12a for a ∈ Z, and k +1 = l +6 . Then:
(k +1)4 −(k +1)2 = (l+6)4 −(l+6)2
= l4 +24l3 +216l2 +864l+1296−(l2 +12l+36)
= (l4 −l3)+24l3 +216l2 +852l+1260
= 12a+24l3 +216l2 +852l+1260
= 12¡a+2l3 +18l2 +71l+105.
Because (a+2l3 +18l2 +71l+105) ∈ Z, we get 12 |(k+1)4−(k+1)2.
Explanation of the proof:
To prove the proposition "If n ∈ N, then 12 | (n4 − n2)" using strong induction, the proof is presented as follows:
(1) Base case: Show that the statement is true for the first six positive integers.
The base case demonstrates that the proposition holds for small values of n.
For n = 1, we have 12 divides 14 − 12 = 0.
For n = 2, we have 12 divides 24 − 22 = 12.
For n = 3, we have 12 divides 34 − 32 = 72.
For n = 4, we have 12 divides 44 − 42 = 240.
For n = 5, we have 12 divides 54 − 52 = 600.
For n = 6, we have 12 divides 64 − 62 = 1260.
(2) Inductive step: Assume the proposition is true for all positive integers from 1 to k, where k ≥ 6.
In the inductive step, the assumption is that the proposition holds for all positive integers from 1 to k. We will show that the proposition is true for k + 1.
To prove the proposition for k + 1, consider the following steps:
Step 1: Use the assumption from the inductive hypothesis.
Assume that 12 | (m4 − m2) for 1 ≤ m ≤ k, which means S1, S2, ..., Sk are true.
Step 2: Express (k + 1)4 − (k + 1)2 in terms of the inductive hypothesis.
Now, consider the expression (k + 1)4 − (k + 1)2. We can rewrite k + 1 as (k − 5) + 6, where 6 is chosen because the base case showed the proposition holds for k = 6. So, we set k − 5 = l, giving us k + 1 = l + 6.
Step 3: Simplify the expression using the inductive hypothesis.
Now, rewrite the expression as follows:
(k + 1)4 − (k + 1)2 = (l + 6)4 − (l + 6)2
= l4 + 24l3 + 216l2 + 864l + 1296 − (l2 + 12l + 36)
= (l4− l3) + 24l3 + 216l2 + 852l + 1260
Step 4: Factor out 12 from the expression.
We observe that l4 −l3 is divisible by 12 due to the inductive hypothesis. Let (l4 − l3) = 12a for some a ∈ Z.
So, the expression becomes:
(k + 1)4 − (k + 1)2 = 12a + 24l4 + 216l3 + 852l + 1260
Step 5: Further simplification.
We can factor out 12 from the remaining terms, which will leave us with a multiple of 12:
(k + 1)4 − (k + 1)2 = 12(a + 2l4 + 18l3 + 71l + 105)
Since (a + 2l3 + 18l2 + 71l + 105) ∈ Z, we conclude that 12 | (k + 1)4 − (k + 1)2.
This completes the inductive step, showing that the proposition is true for all positive integers. Thus, we have proven that if n ∈ N, then 12 | (n4 − n2).