Structural induction on a set of binary trees

Question

Here is a recursive definition for some set $T$ of non-empty binary trees.

• A single node is in $T$
• If $t_1$ and $t_2$ are in $T$, then the bigger tree with root $r$ connected to the roots of $t_1$ and $t_2$ is in $T$

Use structural induction to prove the following property of the elements of $T$: there are $m$ nodes that have two children and $m+1$ nodes that have no children.

Context: I am in a theory of computation class after taking 1.5 years off school and we are on (structural) induction proofs. I never really had trouble with weak/strong induction, but this one is harder for me to grasp, probably because it has recursive definitions and trees.

I really need help with these as I have a midterm soon and I can't do any of these homework problems. Can anyone please show me how they would do this? What would you do in order to guarantee full marks on a test?

Answer 1

Basis : the single node tree $t$ has $0$ nodes with two children, and $1$ node with no children.

Thus : $m=0$ and $m+1=1$.

---

Induction step : assume that $t_1$ is a tree with $m_1$ as in the hypoteses and $t_2$ a tree with $m_2$.

The new tree $t$ is formed adding root $r$ having as children the roots of $t_1$ and $t_2$.

We have to calculate "his" number $m_t$.

The new tree $t$ has one more node with two children (the root $r$).

Thus it has :

$m_1+m_2+1$ nodes with two children and this is the $m_t$ of the new tree $t$.

The number of nodes with no children is left unchanged, and is the sum of the numbers of $t_1$ and $t_2$, i.e. : $m_1+1$ and $m_2+1$.

Thus :

$m_1+1+m_2+1=(m_1+m_2+1)+1=m_t+1$.