Strong induction vs. structural induction?
Let S be the subset of the set of ordered pairs of integers defined recursively by:
Recursive step: If , then and .
List the elements of S produced by the first five applications of the recursive definition.
Use strong induction on the number of applications of the recursive step of the definition to show that 5 | a + b when .
Use structural induction to show that 5 | a + b when .
I have the first five elements of S as follows:
(0,0), (2,3), (4,6), (6,9) and (8,12)
Using strong induction I have that:
Let P(n): 5 | a + b, where (a, b)
Basis step: P(0): 0/5 = 0, P(1): 5/5 = 1, P(2): 10/5 = 2, P(3): 15/5 = 3, P(4): 20/5 = 4
Inductive step: Assume P(j),
Consider P(k + 1): By the inductive hypothesis we know P(k) to be true. From the definition of P(n) we have that the next recursive application will yield P(k + 1): (a + 3, b + 2), when P(k): (a, b).
5 | 5, thus if 5 | (a + b) then 5 | (a + b + 5). Q.E.D.
However (if what I did there is even correct at all) how do I prove the same thing using structural induction?