[Math] Using Induction to prove complete binary trees

Question

Prove a complete binary tree has an odd number of vertices.

My attempt at the solution:

Basis step: A binary tree with a height of 0 is a single vertex. This would result in the tree having an odd number of vertices (1). Correct.

Inductive hypothesis: A complete binary tree with a height greater than 0 and less than k has an odd number of vertices.

Prove: A binary tree with a height of k+1 would have an odd number of vertices.

A complete binary tree with a height of k+1 will be made up of two complete binary trees k1 and k2. K1 and K2 are both complete binary trees meaning they have an odd number of vertices. They can be represented by (2m+1) and (2n+1). A tree with the hieght of k+1 can be represented by (2m+1) + (2n+1) plus 1 connecting vertice. Since (2m+1)+(2n+1) = (2m+2n+2) = 2(m+n+1) we can see that the number of vertices in k1+k2 is even. By adding the connecting vertex we get 2(m+n+1)+1. An odd number. Therefor a tree with the height of k+1 has an odd number of vertices.

Does this work, or have I made a mistake?

Answer 1

Looks good! Note that your inductive hypothesis should say "less than or equal to $k$" and not just "less than $k$". Also, I would perhaps reword the "connecting vertex" part. Start your induction step by saying something like:

Consider a complete binary tree $T$ with a height of $k + 1$. Notice that $T$ is made up of a root node $r$ with two subtrees $T_1$ and $T_2$, each of which are complete binary trees with a height of $k$. But then by the induction hypothesis, we know that...