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?