I have a problem similar to:
Let S defined recursively by
(1) 5 ∈ S and
(2) if s ∈ S and t ∈ S, then st ∈ S. Let
A = {5^i| i ∈ Z+}.
prove that S ⊆ A by structural induction.
I've only done mathematical induction and I'm not sure I understand the differences.
To prove that $S \subseteq A$, you need to prove that for all $x$, $x \in S \Rightarrow x \in A$.
In structural induction, you are required to prove that the elements of a "structure" (in this case the set S) satisfies some property (in this case, that for all $x, $ $x \in S \Rightarrow x \in A$)
Basis:
$5 \in S$ and $5=5^1 \in A$
Recursive Step:
Assume that $s, t \in S \Rightarrow s, t \in A$
By the recursive definition of $S, st \in S$
Since $s, t \in A$, $s = 5^i$ and $t = 5^j$ for some i, j
So, $st =5^{i+j}$ which means $st \in A$
This proves that $S \subseteq A$.
In this problem, it happens that the "structure" is a set.
In this other problem, the "structure" happens to be a checkerboard:
Checkerboard with one gap can be covered by triominos?
Hope this helps.