P(n) must be a property of n, i.e., it must be true or false for each particular natural number n. However, there is no n after the colon, so your property does not depend on n. On the other hand, there are undefined variables a and b.Using strong induction I have that:
Let P(n): 5 | a + b, where (a, b)
Do you assume P(j) for some or for all j between 0 and k?Inductive step: Assume P(j),
Consider P(k + 1)
That's one possibility, but the recursion step forms two new pairs. So, at each step you could also form (a + 3, b + 2) from (a, b), not necessarily (a + 2, b + 3). In fact, the process of generating new pairs branches at each step and the order in which pairs are generated is not determined.I have the first five elements of S as follows:
(0,0), (2,3), (4,6), (6,9) and (8,12)
I believe this is the reason for strong induction. For example, one could generate pairs as follows:
Here pair #3 is formed from (0,0), and pair #5 is formed from pair #3, i.e., a pair may be formed from another one that does not immediately precede it.
So, let P(n) be "if (a, b) is the pair generated after n applications of the recursive step, then 5 | a + b." In the induction step, one has to show that for all k,
P(0), ..., P(k) imply P(k + 1).
Fix some k and assume P(0), ..., P(k). Let (a, b) be the pair generated after the (k + 1)st step. Then there exists a j < k + 1 such that (a', b') is the pair generated after j steps and (a, b) is obtained by the recursion step from (a', b'). Therefore, (a, b) is (a' + 2, b' + 3) or (a, b) is (a' + 3, b' + 2). By P(j), which is a part of the induction hypothesis, 5 | a' + b', so 5 | a + b in both cases.
In the structural induction, on the other hand, one does not need to go back more than one step. You consider a binary tree whose root is (0,0) and each internal node (a, b) has two children (a + 2, b + 3) and (a + 3, b + 2). At each step, one can add two new leaves to some existing leaf. The induction hypothesis is that the sum of each node (which is a pair) in the tree is a multiple of 5. After forming two more leaves, it is clear that this property is preserved.