Thomas A. Alspaugh
A proof of P(x)
by structural induction
over the elements of a recursively defined set X
is analogous to those by mathematical and strong induction,
except:

its basis step proves P(x_{0})
for every element x_{0} in the basis set of X,
and

its inductive step proves that for every recursive rule
from
x_{1}, x_{2}, … , x_{n}
to x,
if
P(x_{1}), P(x_{2}), … , P(x_{n})
then P(x).
Every wellformed propositional logic formula
contains an equal number of left and right parentheses.
Basis steps:

T has an equal number (0) of left and right parentheses.

F has an equal number (0) of left and right parentheses.

a has an equal number (0) of left and right parentheses.

…

z has an equal number (0) of left and right parentheses.
Inductive steps:

If φ
has equal numbers of left and right parentheses,
then ¬φ
has the same equal numbers of left and right parentheses.

If φ_{1}
has equal numbers m of left and right parentheses,
and φ_{2}
has equal numbers n of left and right parentheses,
then φ_{1}∧φ_{2}
has equal numbers m+n of left and right parentheses.

If φ_{1}
has equal numbers m of left and right parentheses,
and φ_{2}
has equal numbers n of left and right parentheses,
then φ_{1}∨φ_{2}
has equal numbers m+n of left and right parentheses.

If φ
has equal numbers n of left and right parentheses,
then (φ)
has n+1 left and n+1 right parentheses,
an equal number of both.
As with mathematical
and strong induction proofs,
a structural inductive proof of P(x)
can be thought of
as a recipe for constructing a proof
for any specific element y of the set.
If y is an element of the set,
there is a sequence of rule applications
that begins from one or more elements of the basis set
and ends with y,
and the specific proof of P(y)
begins with the basis step(s)
for the basis elements that were used,
continues with the inductive steps for the rules that were used,
and concludes with P(y).
Another way of thinking of a structural inductive proof
is that it shows that the proposition is true for the basis elements,
and then shows that
all of the rules preserve the proposition
for all derived elements.