Ok, so here is my question.
For a binary tree B,
count of nodes is nodeCount(B)
count of leaves is leafCount(B)
count of half nodes is halfnodeCount(B) (Half nodes are nodes that have just one child).
P(B) is given by nodeCount(B) = 2 x leafCount(B) + halfnodeCount(B) - 1
Using mathematical induction, prove that P(B) holds for all binary trees.
I was able to prove the base case, when the tree has just one node, and no leaves or half nodes.
That is, nodeCount(B) = 1, leafCount(B) = 1, halfnodeCount(B) = 0
2 x leafCount(B) + halfnodeCount(B) - 1
= (2 x 1) + 0 - 1
= 2 + 0 - 1
= 1
= nodeCount(B)
Now I need to assume that P(B) is true for a tree B of k nodes, then prove that P(B) also holds for B with k+1 nodes.
Please help, I am not sure how to go about this.
Moving what I put in comments to an answer (answering “how to go about this?” without providing a complete proof):
You can use regular induction for this. You proved that $P(1)$ holds, so you need to prove that $P(k) \implies P(k+1)$ when $k\ge 1$.
Let $B$ be a tree with $k+1$ nodes.
$B$ has at least one leaf, so choose one ($v$) and remove it to obtain $B'$.
Consider these two cases:
Case 1: The removed leaf $v$ was an only child. Case 2: The removed leaf $v$ had a sibling.
Case 1: In the smaller tree $B'$, $v$’s parent is now a leaf, because $v$ was an only child. Therefore leafCount($B$) = leafCount($B'$). (Removing $v$ removed one leaf but created one new leaf.) Also, in $B$ $v$’s parent was a half-node and is no longer, so halfnodeCount($B'$) = halfnodeCount}($B$) - 1.
Therefore $2\times$leafCount($B$) + halfnodeCount($B$) - 1 = 2 leafCount($B'$) + (halfnodeCount($B'$)+1) - 1 = $k+1$ (which is what was to be shown).
Case 2: See if you can do this similarly.