structural induction

A structural induction is an induction proof but based on mathematical structures (see inductive definition).

The proof structure of a structural induction is similar to a regular induction proof, except we can do induction on a structure itself. We start by proving the base case that $P(b)$ holds for some base element $b\in S$. Then, for the induction step, we generally prove that for a $k$-place constructor case $c$, when we have $x_1,\dots ,x_k\in S$ and $P(x_1,\dots ,x_k$ holds, then $P(c(x_1,\dots ,x_k))$ also hold.