Originally Posted by

**emakarov** We must be clear on what the induction statement P(k) is. It says that the pair *obtained at step k* has elements whose sum is a multiple of 5. My guess is that the intention of the problem's authors, who suggested using strong induction, was that *a single* pair is generated at each step. Now, the important point is that the pair obtained at step k is not necessarily formed from the pair obtained at step k - 1. In my first post, pair #3 is formed from (0,0), and pair #5 is formed from pair #3. Therefore, to prove P(k + 1) we need not only P(k), but all of P(0), ..., P(k).

This is beyond the scope of this question, but strong induction can be derived from the regular one, so this fact can ultimately be proved using regular induction. Also, it is important that if you generate pairs in such a way that *all* members of S are eventually enumerated, then there necessarily will be pairs that are formed from other pairs that go back more than one step.

Here there is some confusion about what P(k) is. If P(k) is as I described above, we generate a single pair at each step, so we can't say that both (a + 2, b + 3) and (a + 3, b + 2) are formed at step k + 1. To repeat this once more, in this case, step k + 1 may produce not (a + 2, b + 3), but an unrelated pair formed from some other pair several steps back.

If, on the other hand, we posit that step k generates 2^k pairs at once from 2^{k-1} pairs obtained in the previous step, then indeed we don't need strong induction. We must only describe precisely what pairs are generated at step k and formulate P(k) accordingly.

In structural induction, we don't talk about the step *number*. We must only show that if all pairs generated up to now satisfy some property, then the pairs generated by the application of the recursive step also satisfy the property.

I must admit that the distinction between regular and structural induction here seems a little fuzzy. Properly speaking, structural induction is applied not to recursively defined sets of simple objects (such as pairs of numbers), but to objects that have a recursive structure, such as trees, lists, syntactic expressions, etc. The the induction step consists of proving a property for some object assuming it holds of all sub-objects, e.g., it holds of a list provided it holds of the same list without the head.