Examples of inductive property definitions:

The first two examples are based on the inductive definition of full binary tree, and the last two on the inductive definition of regular expressions in the Inductive Definition Examples file.

Height of a full binary tree:

for the base case

h (.) = 0

for the rule

h (T) = 1 + max (h(L), h(R))

number of nodes in a full binary tree:

for the base case

n (.) = 1

for the rule

n (T) = 1 + n(L) + n(R)

Number of characters in a regular expression:

for the base cases

n (empty set) = 0

n (empty str) = 1

n (char) = 1

for the rules

n ( (A) ) = 2 + n(A)

n ( A+B ) = 1 + n(A) + n(B)

n ( AB ) = n(A) + n(B)

n ( A* ) = 1 + n(A)

Depth of Regular Expression Parse Tree

for the base cases

d (empty set) = 1

d (empty str) = 1

d (char) = 2 // first is "char", second is the particular symbol

for the rules

d ( (A) ) = 1 + d (A)

d ( A+B ) = 1 + max (d(A), d(B))

d ( AB ) = 1 + max (d(A), d(B))

d ( A* ) = 1 + d (A)