Question

Assume S is a recursivey defined set, defined by the following properties:

1 ∈ S

n ∈ S ---> 2n ∈ S

n ∈ S ---> 7n ∈ S

Use structural induction to prove that all members of S are numbers of the form 2^a7^b, with a and b being non-negative integers. Your proof must be concise.

Remember to avoid the following common mistakes on structural induction proofs:

-trying to force structural Induction into linear Induction. the inductive step is not about going from "n" to "n+1". you're tracing a logical chain reaction through a tree structure, not a line.

- treating the first generation descendants as part of the base case

-reexplaining the Logic of structural Induction inside the inductive step

-justifying the inductive hypothesis with the base case.

- assuming that the recursion rules defining the recursively defined sets are always applied in some specific sequence, or in combination with each other

-Confusing the definition of the Set S with what you are proving about S

-Confusing what you already know with what you want to verify in the base case

Answer 1