Recursive Definitions and Structural Induction

Consider the following recursive definition of a set of a set of full binary trees:

$2$

Base Case: A single vertex is a full binary tree, and we call this vertex a root of that tree.

Recursive Case: If v is a single vertex and T$0$ and T$1$ are two FBT elements $($i$.$e$.$ two

full binary trees$)$ with roots respectively v$0$ and v$1,$ then thefollowing is a full binary tree with

root v: A vertex v with a left outgoing edge from v to the root of T$0$ and a right outgoing edge

from v to the root of T$1.$

More Tree$-$related Terminology: A vertex of a binary tree which has no outgoing edge is called

a leaf, and a vertex which does have outgoing edges is called an internal node.

Denote the set of full binary trees as FBT$,$ and do the following three things:

$1.$ Define recursively function L : FBT $$ N s$.$t$.$ L$($T$)$ is a number of leaves in T$.$

$2.$ Define recursively function I : FBT $$ N s$.$t$.$ I$($T$)$ is a number of intenal nodes in T$.$

$3.$ Use structural induction to prove that L$($T$)=$ I$($T$)+1$ for every T in FBT$.$