A proper binary tree with n internal nodes has n+1 leaves.
Base case: A tree containing a single node has 0 internal nodes and 1 leaf.
Inductive step: If a proper binary tree with 0<=r<=k internal nodes
has r+1 leaves, then a proper binary tree with k+1 internal nodes has
k+2 leaves.
Proof: Consider a proper binary tree T with k+1 internal nodes, k>=0.
Since T is proper, it consists of a root plus two subtrees, each of
which is also a proper binary tree. Call the left subtree T1, and the
right subtree T2. T1 contains some number of internal nodes; call that
number x. The root of T is also an internal node. The remainder of the
internal nodes in T must be in T2, so T2 contains k+1-x-1 => k-x internal
nodes. By the inductive hypothesis, T1 contains x+1 leaves and T2
contains k-x+1 leaves. Since all of the leaves in T are in either T1
or T2, T must contain x+1+k-x+1 => k+2 leaves.
The number of leaves in any binary tree is one more than the number of
nodes with two children.
Base case: A binary tree consisting of a single node contains 0 nodes with
two children and 1 leaf.
Inductive step: If a binary tree containing k nodes with two children has k+1
leaves, then a binary tree containing k+1 nodes with two children has k+2 leaves.
Proof: Consider a binary tree T that has k nodes with two children, and by
the inductive hypothesis has k+1 leaves. There are two ways to grow
this tree: by adding a child to a leaf, or by adding a child to a
node that already has one child. If you add a child to a leaf, neither
the number of nodes with two children nor the number of leaves changes,
so the property still holds. If you add a child to a node that already
has one child, the number of nodes with two children increases by 1, to
k+1, and the number of leaves increases by 1, to k+2.