Let the set S be a set of positive integers defined recursively by Basis step: 1 is in S Recursive step: If n is in S, then 3n+2 is in S and n2 is in S. Show by structural induction that if n is in S, then n mod 4 is 1.

We have first to prove the property that 1 is in S, since 1 is the first element of the set. In this case, however, it is trivial to prove that 1 mod 4 is 1; still, it is very important to remark that the property is valid for the first (or starter) element of the set, otherwise it could go all wrong.

Now lets go to the inductive step: lets suppose that the property is valid for a certain number n, with n an element of S. We want to show that the property is valid for the first element generated by n: 3n+2.

Since the property is valid for n, then n mod 4 is 1. Now, the property of module respets multiplications, therefore, 3n mod 4 is 1*3 = 3, and it also well behaves with sums, thus 3n+2 mod 4 is 3+2 = 5, which mod 4 is 1. This means that 3n+2 mod 4 is 1, and as a result, 3n+2 also follows the property, as we wanted to see.

For induction, we proved that if n is an element of S, then n mod 4 is 1.