Using mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes

Question

Use mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes.

I'm familiar with mathematical induction proofs, but I haven't encountered one like this. I'm not sure how to set up the base case.

I thought about letting $n$ = the number of leaf nodes, then showing by induction that $n \le 2^h$. This didn't seem right though, because all of the proofs I have done by induction have been in terms of one variable. Any hints?

Answer 1

I thought about letting $n =$ the number of leaf nodes, then showing by induction that $n≤2^h$. This didn't seem right though, because all of the proofs I have done by induction have been in terms of one variable.

Indeed, that does not seem right. Generally, the variable of induction is something you can grasp already, not something you are trying to understand (as the number of nodes here). The correct approach is to induct on $h$, starting with the base case $h=0$ and proceeding with the observation that adding another step can at most double the number of leaves.