Prove by structural induction that in a binary tree of height h$,$ the number of nodes $($not just leaves$)$ is at MOST:

Draw at least $3$ example binary trees of different heights that have the maximum possible number of nodes. Make a table of the height vs$.$ node count.

State the base case CLEARLY.

Prove$/$show the base case.

State the inductive hypothesis clearly. What will you assume, and what will you prove?

Prove the inductive hypothesis.